Characterizing diverse link patterns in complex networks: theory and applications
2013-08
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Characterizing diverse link patterns in complex networks: theory and applications
Authors
Published Date
2013-08
Publisher
Type
Thesis or Dissertation
Abstract
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.
Keywords
Description
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.
Related to
Replaces
License
Collections
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Li, Yanhua. (2013). Characterizing diverse link patterns in complex networks: theory and applications. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/158760.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.