University of Houston

Complex networks are ubiquitous – from social and information systems to biological and technological systems. Such networks are platforms for interactions, communication and collaboration between nodes. Studying and analyzing the observable network interactions are therefore crucial to understand the hidden complex network behaviors.

However, with pervasive use of the Internet and various advances in technology, networks under study today are not only substantially larger than those in the past, but sometimes exist in a decentralized form. Along with network scale, the volume of interaction data also present a serious challenge to network analyzing and data mining techniques. This dissertation focuses on developing inference solutions for complex networks from different domains and apply them to solve practical networking problems.

In the first part of the dissertation, we propose bICA, a new inference algorithm that is specialized for communication networks that can be formulated as a bipartite graph. Then we apply bICA and its variations to solve a wide range of networking problems: from optimal monitoring and primary user separation on wireless networks to multicast network tree topology inference. Evaluation results show that the methodology is not only innovative, but is also more effective than previous approaches.

In the second part, we extend out study to online social networking domain, where the network is not only massive but also dynamic. Specifically, we study the information diffusion between nodes on social networks. We found a very interesting and counterintuitive model of influence spread on Twitter, which change some of the basic assumptions that many researchers made in the past. We also investigate the problem of inferring the most influential entities. Experiments using both large-scale social networks and synthetically generated networks demonstrate superior performance of the proposed algorithm.