Source-linked AI summary
Characterizing the community structure of complex networks
Andrea Lancichinetti, Mikko Kivela, Jari Saramaki, Santo Fortunato
TL;DR
Although community detection has been studied extensively, the structural properties of communities in real networks remain insufficiently understood. This paper systematically analyzes communities across large network categories using two fundamentally different detection methods. It finds class-specific structural signatures that are consistent within network categories and robust to the detection method.
Problem
The paper addresses the limited understanding of the fundamental properties of communities in real networks despite extensive work on community detection.
Method
The authors perform an extensive statistical analysis of communities in large real networks across five categories and cross-check results with Infomap and Label Propagation.
Results
Networks within the same class display similar community signatures, while classes differ in community densities, path-length behavior, and node embeddedness; these patterns are verified by two detection methods.
Takeaways & Limitations
The identified community signatures can serve as network fingerprints for classifying systems and informing more accurate network models.
Abstract
from arXiv · showhide
Community structure is one of the key properties of complex networks and plays a crucial role in their topology and function. While an impressive amount of work has been done on the issue of community detection, very little attention has been so far devoted to the investigation of communities in real networks. We present a systematic empirical analysis of the statistical properties of communities in large information, communication, technological, biological, and social networks. We find that the mesoscopic organization of networks of the same category is remarkably similar. This is reflected in several characteristics of community structure, which can be used as ``fingerprints'' of specific network categories. While community size distributions are always broad, certain categories of networks consist mainly of tree-like communities, while others have denser modules. Average path lengths within communities initially grow logarithmically with community size, but the growth saturates or slows down for communities larger than a characteristic size. This behaviour is related to the presence of hubs within communities, whose roles differ across categories. Also the community embeddedness of nodes, measured in terms of the fraction of links within their communities, has a characteristic distribution for each category. Our findings are verified by the use of two fundamentally different community detection methods.
I. INTRODUCTION
Complex-network communities are important mesoscopic structures, but research has focused more on detecting them than on understanding their properties in real networks. This paper addresses that gap by systematically characterizing communities across network classes and examining whether their features are class-specific and method-independent.
- Communities group nodes with many within-group links and comparatively few links between groups, forming a common mesoscopic organization across diverse systems.
- Studying communities can reveal coarse network organization, clarify mechanisms of network dynamics, and expose relationships associated with system function.
- Community detection has attracted extensive methodological research, but no universally accepted method exists because the concept of community is ill-defined.
- The fundamental structural properties of communities in real networks remain largely unknown, motivating this paper’s empirical investigation.
- The paper finds that networks in the same class share distinctive community features, while different classes differ, independently of the detection method used.
II. DATA AND METHODS
The study analyzes large network datasets from five categories and compares community structure using complementary detection methods. It focuses on broad community-size distributions while assembling data suitable for statistical analysis across communities of varying sizes.
- The datasets contain approximately 10^5–10^6 nodes, except protein-interaction networks, whose largest available datasets contain about 10^4 nodes.
- The analysis covers five network categories: communication, Internet, information, biological, and social networks.
- The collection includes email and discussion-page communication networks, Internet maps, citation, co-purchasing and Web graphs, protein-interaction networks, and online friendship or trust networks.
- Infomap and Label Propagation are used as contrasting, fast community-detection methods to cross-check whether conclusions depend on the algorithm.
- Figure 1 shows broad community-size distributions, with data points averaged within logarithmic bins of module size s.
III. RESULTS
Community structure varies systematically across network classes, with distinctive size, density, path-length, hub-dominance, and embeddedness patterns. These category-specific fingerprints are visible across the analyzed real networks.
- Community sizes: Community sizes span several orders of magnitude, and distributions within the same network class have broadly similar shapes.Biological networks show the largest cross-dataset differences, likely reflecting noise from their smaller size.
- Community topology: Communication and Internet communities are close to tree-like, whereas information and social communities are denser; biological communities become denser as size increases.Communication-network scaled density is roughly size-independent, while information and social networks show increasing scaled density with community size.
- Path lengths: For communities larger than about 10 nodes, average shortest paths grow more slowly or plateau after an initial logarithmic regime.The stabilization is attributed to high-degree hubs that keep geodesic paths short within macrocommunities.
- Path lengths: Communication communities have distances near 2 for s > 10, while sparse Internet communities show merged-star structures and information communities can contain dense cliques.These patterns connect low path lengths to dominant hubs in communication and Internet communities, contrasting with denser information-network modules.
- Hub structure: Hub dominance remains high in communication communities, decreases with size in Internet, biological, and social networks, and can involve multiple near-universal connectors in Web communities.In social networks, large communities have few or no dominant hubs.
- Node embeddedness: More than 50% of nodes are typically entirely internal to their communities, while embeddedness distributions differ systematically across network classes.Communication and Internet profiles peak near kin/k ∼0.5; information networks rise toward a plateau around kin/k ∼0.4.
IV. DISCUSSION AND CONCLUSIONS
Communities show structural characteristics that are similar within network classes but differ across classes. These class-specific signatures remain consistent across two fundamentally different detection methods, while method choice and partitioning impose important scope limits.
- Communities in networks of the same class display similar structural characteristics, despite broad variation within some classes.
- Community sizes are broad across all studied systems, while link densities depend strongly on network class.
- Average shortest paths initially grow logarithmically with community size, then slow or saturate for communities larger than approximately 10 nodes.The pattern distinguishes microcommunities from macrocommunities and, together with link density, reflects differing hub dominance.
- High-degree nodes dominate communities more strongly in communication and Internet networks than in social networks.
- The resulting community signatures could classify other systems, identify new network classes, and improve network models’ descriptions and evolution predictions.
- Partition-based methods overlook nodes participating in multiple communities, while methods requiring locally dense modules may exclude tree- or star-like communities.Nevertheless, detected communities remain network subgraphs whose statistical properties reflect mesoscopic organization.
Appendix A: Data sets: basic statistics
The appendix describes degree, clustering, and degree-correlation patterns across the analyzed networks. Degree distributions span several orders of magnitude, while clustering and assortativity reveal broad similarities and category-specific differences.
- Degree distributions span several orders of magnitude across all analyzed networks.
- Clustering coefficients generally decrease rapidly with degree, except in Web graphs where dense subgraphs and cliques sustain high clustering near degree 100.
- Communication networks, the Internet, and Web graphs are clearly disassortative in average nearest-neighbor degree.
- Other networks are moderately disassortative or show no particular degree correlation, while LiveJournal is assortative at intermediate degrees.
Appendix B: The community detection methods
The study uses two partition-based community detection approaches with different principles. Infomap encodes random-walk behavior, whereas modified label propagation spreads neighborhood labels while limiting excessive cluster growth.
- The analysis explains two community detection algorithms and uses them as fundamentally different partition-based approaches.
- Infomap seeks partitions that shorten a random walker’s description by exploiting prolonged movement within dense modules.
- Label propagation assigns each node the most frequent neighboring label iteratively until convergence.
- The analyzed Label Propagation variant introduces a hop score that decreases as labels spread, improving partition quality and limiting oversized clusters.
Appendix C: Main results from the Label Propagation Method
The appendix repeats the main community analysis with Label Propagation to test whether the findings depend on the detection method. The resulting characteristics are consistent with those obtained using Infomap.
- The main Infomap analysis was repeated with Label Propagation to test whether the results reflect network organization rather than method choice.
- Label Propagation produces community-size distributions, link-density patterns, and average-shortest-path characteristics corresponding to the main analysis.
- The Label Propagation results are consistent with those obtained using Infomap.
Appendix D: Further Statistics on Community Properties
Appendix D examines additional module statistics using Infomap and the Label Propagation Method, showing that community link densities vary with module size and network category. It also defines internal clustering and reports category-specific clustering patterns.
- Methods: Infomap and the Label Propagation Method are used to display the appendix’s module statistics.The figures report results from Infomap in the upper panel and Label Propagation Method in the lower panel.
- Link density: Community link-density distributions contain both dense and sparse modules across all systems.The appendix examines the full probability distribution of community link density ρ rather than only average values.
- Link density: Only social and information networks retain dense modules when communities smaller than 3 nodes and then smaller than 10 nodes are excluded.The filtering conditions are s > 3 and s > 10, respectively; the reported persistence of dense modules applies to fairly large modules.
- Internal clustering: Internal clustering is computed within each community as links among a node’s neighbors divided by the maximum possible number of such links.Nodes with degree below two are omitted because their clustering coefficient is undefined, and “internal” restricts the calculation to community subgraphs.
- Internal clustering: Communication systems and the Internet can reach fairly high average internal clustering in large communities.The passage contrasts this pattern with the corresponding behavior of other network categories, though the supplied text truncates that comparison.
Appendix E: Further Statistics of Node Properties
Appendix E examines node properties relative to their communities using Infomap and the Label Propagation Method. Degree filtering smooths embeddedness distributions because low-degree nodes quantize the internal-neighbor fraction and account for many fully embedded nodes, except in information networks.
- Methods: Node-community properties are compared using Infomap and the Label Propagation Method.Infomap results appear in the upper panel and Label Propagation Method results in the lower panel.
- Community embeddedness: For nodes with k > 3 or k > 10, embeddedness curves are flatter and smoother than full distributions.The fraction considered is kin/k, the fraction of a node’s neighbors belonging to its community.
- Community embeddedness: Low-degree nodes create peaks because kin/k is quantized; for degree two, possible values are 0, 0.5, or 1.Degree filtering therefore removes fluctuations associated mainly with low-degree nodes.
- Community embeddedness: Many fully embedded nodes have low degree, except that information networks do not show the same lower rightmost points after filtering.The rightmost filtered-curve points lie much lower than the corresponding full-curve points in most categories.