Interactions on Complex Networks: Inference Algorithms and Applications

Abstract

Complex networks are ubiquitous – from social and information systems to biological and technological systems. Such networks are platforms for interaction, communication, and collaboration among distributed entities. Studying and analyzing observable network interactions are therefore crucial to understand the hidden complex network properties. However, with pervasive adoption of the Internet and technology advancements, networks under study today are not only substantially larger than those in the past, but are often highly distributed over large geographical areas. Along with this massive scale, the volume of interaction data also presents a serious challenge to network analysis and data mining techniques. This dissertation focuses on developing inference solutions to complex networks from different domains and applying them in solving practical problems in information and social sciences. In the first part of the dissertation, we propose Binary Independent Component Analysis with OR Mixtures (bICA), an inference algorithm specialized for communication networks that can be formulated as a bipartite graph. Then we apply bICA and its variants to solve a wide range of networking problems, ranging from optimal monitoring and primary user separation in wireless networks to multicast network tree topology inference. Evaluation results show that the methodology is not only more accurate than previous approaches, but also more robust against measurement noise. In the second part, we extend our study to the online social networking domain, where the networks are both massive and dynamic. We conduct an extensive analysis on Twitter and associated influence ranking services. Several interesting discoveries have been made, which challenge some of the basic assumptions that many researchers made in the past. We also investigate the problem of finding the set of most influential entities on social networks given a limited budget. Experiments conducted on both large-scale social networks and synthetically generated networks demonstrate the effectiveness of the proposed solution.