Book contents
- Frontmatter
- Dedication
- Contents
- Preface
- Introduction
- Epigraph
- 1 Graphs and Graph Theory
- 2 Centrality Measures
- 3 Random Graphs
- 4 Small-World Networks
- 5 Generalised Random Graphs
- 6 Models of Growing Graphs
- 7 Degree Correlations
- 8 Cycles and Motifs
- 9 Community Structure
- 10 Weighted Networks
- Appendices
- References
- Author Index
- Index
9 - Community Structure
Published online by Cambridge University Press: 11 October 2017
- Frontmatter
- Dedication
- Contents
- Preface
- Introduction
- Epigraph
- 1 Graphs and Graph Theory
- 2 Centrality Measures
- 3 Random Graphs
- 4 Small-World Networks
- 5 Generalised Random Graphs
- 6 Models of Growing Graphs
- 7 Degree Correlations
- 8 Cycles and Motifs
- 9 Community Structure
- 10 Weighted Networks
- Appendices
- References
- Author Index
- Index
Summary
Real-world networks present interesting mesoscopic structures, meaning that they carry important information also at an intermediate scale: a scale that is larger than that of the single nodes, but smaller than that of the whole network. In fact, their nodes are often organised into communities, i.e. clusters of nodes such that nodes within the same cluster are more tightly connected than nodes belonging to two different clusters. In such cases we say that the networks have a community structure. The most important point is that nodes in the same network cluster usually share common features. For instance, we will see that communities in the Zachary's karate club network coincide with real social groupings, communities in brain networks identify areas of the brain with different functions, while tightly connected groups of nodes in theWorldWideWeb correspond to pages on common topics. This is the reason why, by finding the communities of a network, we can learn a lot about the way the network works. In this chapter we will consider various methods to find communities, starting with two traditional approaches, namely spectral partitioning and hierarchical clustering, and then focusing on more recent methods specifically introduced by network scientists to find community structure in networks.We will present the Girvan– Newman approach that is based on the removal of the high-centrality edges, and then we will define a quality function, the so-called modularity, that quantifies the quality of a given partition of the nodes of the network.We will show that communities can be extracted directly by optimising the modularity over the set of possible graph partitions. Finally, we will discuss the label-propagation algorithm, a local and fast method to detect communities which can be used for very large graphs. The study of network community structure is now considered a research field by itself, and is an area of network science that is still rapidly expanding in different directions, with important contributions also from computer scientists and software engineers. Needless to say, it is very difficult to keep pace with the most recent approaches and algorithms. The choice of the topics of this chapter is therefore mainly didactic, and we have included in Section 9.8 a few pointers to some of the most advanced methods for community detection.
- Type
- Chapter
- Information
- Complex NetworksPrinciples, Methods and Applications, pp. 332 - 373Publisher: Cambridge University PressPrint publication year: 2017