Complex networks, including the Internet, wireless and cellular networks, and online social networks, are becoming indispensable parts of our daily lives. Various seemingly unrelated applications arising from these networks can be formulated as random walks, which enable us to reveal important network structural information, e.g., importance of nodes as in the Page-Rank algorithm, or to study ways to efficiently explore complex networks. However, how random walks perform and behave significantly depends on the underlying link patterns, which in turn have a great impact in understanding and solving problems in various 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. In another application, online social networks (OSNs) such as Slashdot and Epinions represent relationships between users as links with positive or negative weights, which correspond to trust and distrust relations. These networks are referred to as signed networks, where those signed links generate new challenges in understanding and studying the random walk properties on such networks. In this talk, I present my work on developing theories of random walk (and graph spectrum) for studying and characterizing various crucial graph properties, such as the edge directionality in directed graphs and the edge polarity in signed graphs. I do so by emphasizing on applications to estimating transmission costs in wireless networks, and understanding social influence propagation patterns on online social networks with both friend and foe relationships.
 

Yanhua Li is a Ph.D. candidate in Computer Science at the University of Minnesota, Twin Cities. He obtained his first Ph.D. in Electrical Engineering from Beijing University of Posts and Telecommunications in 2009. His broad research interests are in analyzing and understanding various complex networks in many contexts. His specific interests include spectral graph theory, online social behavior modeling and analysis, large-scale complex network sampling, measurement, and mining, and high performance networking protocol design. His work has been published and accepted by top conferences and journals in both data mining and networking areas, such as WSDM, IMC, INFOCOM, ICDCS, Internet Mathematics, IEEE/ACM ToN, IEEE TVT, etc. He has one filed US patent.