Given a history of detected malware attacks, can we predict the number of malware infections in a country? Can we do this for different malware and countries? This is an important question which has numerous implications for cyber security, right from designing better anti-virus software, to designing and implementing targeted patches to more accurately measuring the economic impact of breaches. This problem is compounded by the fact that, as externals, we can only detect a fraction of actual malware infections. In this paper we address this problem using data from Symantec covering more than 1.4 million hosts and 50 malware spread across 2 years and multiple countries. We first carefully design domain-based features from both malware and machine-hosts perspectives. Secondly, inspired by epidemiological and information diffusion models, we design a novel temporal non-linear model for malware spread and detection. Finally we present ESM, an ensemble-based approach which combines both these methods to construct a more accurate algorithm. Using extensive experiments spanning multiple malware and countries, we show that ESM can effectively predict malware infection ratios over time (both the actual number and trend) upto 4 times better compared to several baselines on various metrics. Furthermore, ESM's performance is stable and robust even when the number of detected infections is low.

Given a social network, can we quickly 'zoom-out' of the graph? Is there a smaller equivalent representation of the graph that preserves its propagation characteristics? Can we group nodes together based on their influence properties? These are important problems with applications to influence analysis, epidemiology and viral marketing applications.

Though centrality of vertices in social networks has been extensively studied, all past efforts assume that centrality of a vertex solely depends on the structural properties of graphs. However, with the emergence of online "semantic" social networks where vertices have properties (e.g. gender, age, and other demographic data) and edges are labeled with relationships (e.g. friend, follows) and weights (measuring the strength of a relationship), it is essential that we take semantics into account when measuring centrality. Moreover, the centrality of a vertex should be tied to a diffusive property in the network - a Twitter vertex may have high centrality w.r.t. jazz, but low centrality w.r.t. Republican politics. In this paper, we propose a new notion of diffusion centrality (DC) in which semantic aspects of the graph, as well as a diffusion model of how a diffusive property p is spreading, are used to characterize the centrality of vertices. We present a hyper graph based algorithm to compute DC and report on a prototype implementation and experiments showing how we can compute DCs (using real YouTube data) on social networks in a reasonable amount of time. We compare DC with classical centrality measures like degree, closeness, betweenness, eigenvector and stress centrality and show that in all cases, DC produces higher quality results. DC is also often faster to compute than both betweenness, closeness and stress centrality, but slower than degree and eigenvector centrality.

STUN is an extension of social networks in which the edges are characterized by spatio-temporal annotations, as well as uncertainty allowing us to express not only relationships between vertices, but when and where these relationships were true, and how certain we are that the relationships hold. We propose a STUN query language that consists of sub graphs with spatio-temporal constraints and uncertainty requirements. We then develop an index structure to store STUN graphs, together with an algorithm to answer such queries. We describe experiments with a real-world YouTube social network data set and show that our algorithm performs well on graphs with over a million edges.

It has been known for some time that in terror networks, money laundering networks, and criminal networks, "important" players want to stay "off" the radar. They need sufficient centrality (according to traditional measures) to be well connected with the rest of their network, but need to blend in with the crowd. In this paper, we propose the concept of covertness centrality (CC). The covertness centrality of a vertex v consists of two parts: how "common" v is w.r.t. a set C of centrality measures, and how well v can "communicate" with a user-specified set of vertices. The more "common" v is, the more able it is to stay hidden in a crowd. Given C, we first propose some general properties we would like a common-ness measure to satisfy. We then develop a probabilistic model of common-ness that a vertex has w.r.t. C (specifying, intuitively, how many other vertices are like it according to all centrality measures in C). Covertness centrality of vertex v is then defined as a linear combination of common-ness and the ability of v to communicate with a user-specified set of other vertices. We develop a prototype implementation of CC and report on experiments we have conducted with it on several real-world data sets.