Community structure of large networks

Placeholder Show Content


One of the main organizing principles in real-world networks is that of network communities, which are sets of nodes that share common properties, functions, or roles. Communities in networks often overlap as nodes can belong to multiple communities at once. Identifying such overlapping network communities is crucial for an understanding of social, technological, and biological networks. In this thesis, we develop a family of accurate and scalable community detection methods and apply them to large networks. We begin by challenging the conventional view that defines network communities as densely connected clusters of nodes. We show that the conventional view leads to an unrealistic structure of community overlaps. We present a new conceptual model of network communities, which reliably captures the overall structure of a network as well as accurately models community overlaps. Based on our model, we develop accurate algorithms for detecting overlapping communities that scale to networks an order of magnitude larger than what was possible before. Our approach leads to novel insights that unify two fundamental organizing principles of networks: modular communities and the commonly observed core-periphery structure. In particular, our results show that dense network cores stem from the overlaps between many communities. As the final part of the thesis, we present several extensions of our models such that we can detect communities with a bipartite connectivity structure and we combine the node attributes and the network structure for community detection.


Type of resource text
Form electronic; electronic resource; remote
Extent 1 online resource.
Publication date 2014
Issuance monographic
Language English


Associated with Yang, Jaewon
Associated with Stanford University, Department of Electrical Engineering.
Primary advisor Garcia-Molina, Hector
Primary advisor Leskovec, Jurij
Thesis advisor Garcia-Molina, Hector
Thesis advisor Leskovec, Jurij
Thesis advisor Guibas, Leonidas J
Advisor Guibas, Leonidas J


Genre Theses

Bibliographic information

Statement of responsibility Jaewon Yang.
Note Submitted to the Department of Electrical Engineering.
Thesis Thesis (Ph.D.)--Stanford University, 2014.
Location electronic resource

Access conditions

© 2014 by Jaewon Yang
This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).

Also listed in

Loading usage metrics...