Disentangling the network: understanding the interplay of topology and dynamics in network analysis

2012-07-17Understanding the complex interplay of topology and dynamics in complex networks is necessary to answer a variety of questions, including who are the important people in a social network, what are the authoritative pages on the world wide web, who to quarantine to minimize the spread of an epidemic, what are the functional modules in a protein-protein network, and even how the world trade network affects the robustness of the global economy. To address these questions, we build predictive network models that take dynamic interactions into account. Our mathematical models are grounded empirically on data from online social networks on sites such as Digg, Twitter and Facebook. ❧ We claim that network structure is the product of both topology and dynamics. We propose a generalized interaction model that describes a range of dynamic processes, or interactions, taking place in complex networks, from random walks to epidemic spread. Traditionally, network analysis methods, including those used to identify central nodes and communities in the network, either ignore or make implicit assumptions about network interactions. We show, however, that different interactions lead to different views of network structure, and empirically verify this insight using real-world data from online social networks. ❧ A wide spectrum of heterogeneous activity spanning from information diffusion to spamming has been observed in online social networks. We have designed a simple, scalable and robust, information theoretic framework to automatically classify different types of activities. Of these, we are especially interested in information spread. We have developed a mathematical framework to quantitatively measure how information spreads on networks, and showed that standard epidemic models fail to describe the spread of information in real-world networks. ❧ Our work is a step towards the ultimate goal of building theoretically justified, empirically grounded network models that improve the prediction of future behavior, aid information discovery and outbreak control, and help in designing network policies for our connected world