Characterizing diverse link patterns in complex networks: theory and applications

University of Minnesota Ph.D. dissertation. August 2013. Major: Computer Science. Advisor: Prof. Zhi-Li Zhang. 1 computer file (PDF); x, 137 pages, appendix A.Complex networks, including the Internet, wireless and cellular networks, and on-line social networks, are becoming indispensable parts of our daily lives. These networks arising from a wide range of applications can be represented and studied as graphs, and the underlying link patterns play an important role in understanding and solving problems in such applications. For example, due to the unreliable and asymmetric wireless channel, ad hoc wireless networks can be viewed as directed graphs, and the link directions contain crucial information about the possibility and efficiency of routing over such networks. Moreover, many online social networks, such as Twitter and Google+, can be viewed as directed graphs with uni-directional "following" relations among users, and the link directions contain crucial information about how users form social communities. In another application, online social networks such as Slashdot and Epinions represent relationships between users as links with positive or negative weights, which correspond to friend and foe relations. These networks are referred to as signed networks, where those signed links generate new challenges in understanding and studying the underlying network properties. In this dissertation, I present my work on developing theories for studying and characterizing various crucial properties and application challenges in undirected, directed, and signed complex networks. First of all, we develop and extend random walk theory and the intrinsically related spectral graph theory for undirected graphs to directed graphs. Then, we explore application challenges raised by various link patterns. To be precise, we introduce a novel social community detection algorithm for social networks with both uni- and bi-directional links. In undirected communication networks, we establish the routing continuum theory that spans from short path routing to "potential" based all-path routing, based on the connection between routing and network flow optimization problems. Moreover, we investigate the social influence diffusion dynamics and influence maximization in social networks with both friend and foe relations