Community detection in networks: A user guide

Santo FortunatoDarko Hric

article2016arXiv2,093 citations

Clarifies the foundations of network community detection by evaluating the strengths and limitations of popular clustering algorithms, dispelling widespread methodological misconceptions, and providing practical criteria for performance validation.

Listen

Community detection in networks—also known as graph clustering—is a foundational challenge across modern data science, social network analysis, biological modeling, and technological infrastructure. Identifying functional groups or modules within interconnected systems is critical for understanding organizational architecture, detecting information spreading, and discovering latent relationships. However, progress across the discipline has historically been hindered because community detection is mathematically ill-defined: there is no single, universally accepted definition of what constitutes a network community, leading to conflicting methodologies, flawed evaluation benchmarks, and poor algorithmic performance in practical deployments.

This article provides a critical, comprehensive evaluation of the core theoretical foundations, validation practices, and computational algorithms in network community detection. It systematically evaluates classic and modern definitions of network modularity, exposes structural and methodological biases within popular techniques, and clarifies the relationship between topological graph structures and external ground-truth metadata to guide practitioners toward reliable methods.

To conduct this evaluation, the authors combine extensive theoretical analysis, statistical mechanics modeling, information-theoretic derivations, and empirical benchmarks. The credibility of the work rests on rigorous evaluations using established generative models—such as the planted l-partition framework, standard and degree-corrected Stochastic Block Models (SBMs), and heterogeneous Lancichinetti-Fortunato-Radicchi (LFR) benchmarks—alongside empirical comparative testing across diverse real-world social, biological, technological, and information networks spanning thousands to millions of nodes.

The findings reveal critical insights for network analysis. First, the article establishes that traditional, intuitive definitions based solely on counting internal versus external connections fail in realistic settings; communities are fundamentally probabilistic constructs governed by preferential attachment probabilities. Second, in sparse networks, random noise creates fundamental detectability thresholds: below specific connectivity limits, no algorithm can identify underlying communities better than random guessing, regardless of computational power. Third, popular optimization heuristics—most notably Newman-Girvan modularity maximization—suffer from severe intrinsic biases, including an unavoidable resolution limit that arbitrarily merges small, well-defined clusters and fragments large ones, while producing vast landscapes of degenerate, conflicting high-scoring partitions. Fourth, external network annotations and metadata do not naturally align with topological communities; treating metadata as strict ground truth introduces severe validation errors. Finally, edge clustering offers no systematic performance advantage over vertex clustering when searching for overlapping communities, while consensus clustering and model-selection-based statistical inference provide far more robust structural recovery.

These findings have direct operational and strategic implications for organizations utilizing network clustering for business intelligence, cybersecurity, system design, and biological modeling. Relying on default tools like standard modularity maximization (e.g., standard Louvain executions) introduces significant risk of misidentifying core modules, wasting analytical effort on resolution artifacts, and drawing false conclusions from misaligned metadata. Decisions based on unvalidated network partitions can lead to incorrect resource allocation, flawed product recommendations, and misunderstood organizational dynamics.

Practitioners should immediately transition away from unconstrained modularity maximization and instead deploy principled statistical inference techniques, such as degree-corrected hierarchical Stochastic Block Models or flow-based dynamics methods like Infomap. When algorithms are stochastic, teams should utilize consensus clustering to aggregate multiple runs into a stable consensus partition. Furthermore, network metadata should not be forced as a ground truth target; instead, analysts should adopt unified models that measure the statistical correlation between structural topology and node attributes to infer missing data or validate findings.

These conclusions are presented with high confidence based on exact statistical and information-theoretic proofs. However, readers should note that computational trade-offs remain: high-precision statistical inference models and spectral non-backtracking matrix calculations scale superlinearly and can become computationally expensive on extremely large graphs. In such massive, sparse deployments, practitioners must carefully balance analytical precision against computational limits.

Aalto University Indiana University community detection network architecture probability Vertices Communities Community

arXiv: 1608.00163

Paper: Community detection in graphs, Santo Fortunato (2009). Reading this foundational survey on community detection provides the essential algorithmic taxonomy and historical context assumed by the user guide.
Paper: Defining and evaluating network communities based on ground-truth, Jaewon Yang et al. (2012). Understanding how ground-truth communities are defined from real-world network data clarifies the evaluation challenges highlighted in the user guide.
Paper: Stochastic blockmodels and community structure in networks, Brian Karrer et al. (2010). Mastering degree-corrected stochastic blockmodels prepares the reader for the user guide's discussion of statistical inference methods that account for hub nodes.
Paper: A tutorial on spectral clustering, Ulrike von Luxburg (2007). Reviewing spectral clustering principles and graph Laplacians establishes the mathematical foundation required for the graph-partitioning section of the guide.

Paper: From Louvain to Leiden: guaranteeing well-connected communities, Vincent Traag et al. (2018). This paper directly extends the guide's coverage of modularity optimization by introducing the Leiden algorithm to fix connectivity defects found in Louvain.
Paper: Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks, Wei-Lin Chiang et al. (2019). Building on the community detection concepts in the guide, this work applies graph partitioning to scale up training for deep graph convolutional networks.
Paper: Hierarchical graph representation learning with differentiable pooling, Rex Ying et al. (2018). Extending the hierarchical community concepts from the guide, this paper introduces differentiable pooling to learn multi-level graph representations end-to-end.
Paper: Semi-Supervised Classification with Graph Convolutional Networks, Thomas N. Kipf et al. (2017). This book chapter continues the topological analysis from the guide by formulating semi-supervised node classification via graph convolutional networks.

Cover for Community detection in networks: A user guide

Abstract

Community detection in networks is one of the most popular topics of modern network science. Communities, or clusters, are usually groups of vertices having higher probability of being connected to each other than to members of other groups, though other patterns are possible. Identifying communities is an ill-defined problem. There are no universal protocols on the fundamental ingredients, like the definition of community itself, nor on other crucial issues, like the validation of algorithms and the comparison of their performances. This has generated a number of confusions and misconceptions, which undermine the progress in the field. We offer a guided tour through the main aspects of the problem. We also point out strengths and weaknesses of popular methods, and give directions to their use.

Topics

community detection network architecture probability validation

Keywords

Vertices Communities Community One Network Clusters Networks Edges Structure Number

I Introduction
II What are communities?
II.1 Variables
II.2 Classic view
II.3 Modern view
III Validation
III.1 Artificial benchmarks
III.2 Partition similarity measures
III.3 Detectability
III.4 Structure versus metadata
III.5 Community structure in real networks
IV Methods
IV.1 How many clusters?
IV.2 Consensus clustering
IV.3 Spectral methods
IV.4 Overlapping communities: Vertex or Edge clustering?
IV.5 Methods based on statistical inference
IV.6 Methods based on optimisation
IV.7 Methods based on dynamics
IV.8 Dynamic clustering
IV.9 Significance
IV.10 Which method then?
V Software
VI Outlook
References

Knowls

Knowl 1 — Detectability Threshold in Sparse Assortative Stochastic Block Models
theoretical result
In sparse networks generated by the symmetric planted $l$ -partition or stochastic block model (SBM) with $q$ equal-sized groups of size $n/q$ , intra-group edge probability $p_{\text{in}}$ , inter-group edge probability $p_{\text{out}} < p_{\text{in}}$ , and fixed expected internal degree $\langle k_{\text{in}} \rangle = n p_{\text{in}}/q$ and external degree $\langle k_{\text{out}} \rangle = n p_{\text{out}} (q-1)/q$ , no algorithm can detect the planted partition better than random assignment if:

$\langle k_{\text{in}} \rangle - \frac{\langle k_{\text{out}} \rangle}{q-1} \le \sqrt{\langle k_{\text{in}} \rangle + \langle k_{\text{out}} \rangle}$

Equivalently, the community structure is theoretically detectable in the limit of infinite network size ( $n \to \infty$ ) if and only if:

$\langle k_{\text{in}} \rangle > \frac{\langle k_{\text{out}} \rangle}{q-1} + \frac{1}{2} \left( 1 + \sqrt{1 + \frac{4 q \langle k_{\text{out}} \rangle}{q - 1}} \right)$

When $\langle k_{\text{in}} \rangle$ falls below this threshold, the probability of correctly classifying a vertex is no better than random guessing ( $1/q$ ), even though the ground-truth model has $p_{\text{in}} > p_{\text{out}}$ . This undetectable phase is caused by random fluctuations in sparse graphs and does not occur in dense graphs where $p_{\text{in}}$ and $p_{\text{out}}$ remain constant as $n \to \infty$ .
Knowl 2 — Resolution Limit and Scale Bias of Modularity Maximization
limitation
The Newman-Girvan modularity $Q$ evaluates the quality of a network partition into communities $C$ :

$Q = \frac{1}{2m} \sum_{ij} \left( A_{ij} - \frac{k_i k_j}{2m} \right) \delta(C_i, C_j) = \sum_C \left[ \frac{l_C}{m} - \left( \frac{k_C}{2m} \right)^2 \right]$

where $A$ is the adjacency matrix, $m$ is the total edge count, $k_i$ is the degree of vertex $i$ , $l_C$ is the number of internal edges in community $C$ , and $k_C = \sum_{i \in C} k_i$ is the total degree (volume) of $C$ .

Modularity maximization suffers from an intrinsic resolution limit: under the configuration null model, the expected number of edges between two subgraphs $A$ and $B$ with total degrees $k_A$ and $k_B$ is $k_A k_B / (2m)$ . When $k_A, k_B \sim \sqrt{m}$ or smaller, this expected edge count drops below 1. Consequently, even a single connecting edge between $A$ and $B$ makes merging them yield a higher modularity value than keeping them separated, regardless of their internal cohesiveness.

Conversely, modularity penalizes subgraphs with volumes much larger than $\sqrt{m}$ , splitting cohesive large communities into smaller fragments. Multi-resolution variations using a tuning parameter $\gamma$ shift the global characteristic scale but cannot simultaneously prevent the merging of small clusters and the splitting of large clusters when community sizes are heterogeneous.
Knowl 3 — Probabilistic Definitions of Strong and Weak Communities
definition
Traditional graph-based community definitions rely on counting internal and external edges (for example, a strong community requiring internal degree $k_i^{\text{int}} > k_i^{\text{ext}}$ for every vertex $i$ ). These definitions fail when communities have disparate sizes, because a vertex in a small community can have a larger number of connections to a much larger community even when its per-node edge probability with internal members is substantially higher.

In the probabilistic formulation, communities are defined via underlying edge connection probabilities:
- Strong Community: A subgraph in which every member vertex has a strictly higher probability of being connected to each vertex inside the subgraph than to any vertex outside of it.
- Weak Community: A subgraph in which the average edge probability of each member vertex with other members of its group strictly exceeds its average edge probability with vertices of any other group.
Knowl 4 — Iterative Consensus Clustering Algorithm
algorithm
Consensus clustering combines multiple partitions generated by a non-deterministic clustering algorithm into a single, robust partition that filters out algorithmic noise and overcomes optimization degeneracies.
Input: Graph $G=(V, E)$ with $n$ vertices, clustering algorithm $\mathcal{A}$ , number of partition replicas $n_P$ , threshold $\tau \in [0, 1]$
Output: Consensus partition $\mathcal{P}^*$
Execute $\mathcal{A}$ on $G$ independently $n_P$ times to yield partitions $\mathcal{P}_1, \dots, \mathcal{P}_{n_P}$
loop:
    Compute consensus matrix $D \in \mathbb{R}^{n \times n}$ where $D_{ij}$ is the fraction of partitions in which vertices $i$ and $j$ belong to the same cluster
    for each pair of vertices $(i, j)$ do:
        if $D_{ij} < \tau$ then
             $D_{ij} \leftarrow 0$
    Execute $\mathcal{A}$ on the weighted graph defined by $D$ for $n_P$ runs to obtain partitions $\mathcal{P}'_1, \dots, \mathcal{P}'_{n_P}$
    if all $\mathcal{P}'_1, \dots, \mathcal{P}'_{n_P}$ are identical then
        return $\mathcal{P}'_1$
    else:
         $\{\mathcal{P}_1, \dots, \mathcal{P}_{n_P}\} \leftarrow \{\mathcal{P}'_1, \dots, \mathcal{P}'_{n_P}\}$
Knowl 5 — Inferring Cluster Count via Non-Backtracking and Flow Matrix Spectra
model/method
The number of communities $q$ in a network can be estimated from the spectra of the $2m \times 2m$ non-backtracking matrix $B$ or the degree-normalized flow matrix $F$ , defined on directed edges $i \to j$ and $r \to s$ :

$B_{i\to j, \, r\to s} = \delta_{is}(1 - \delta_{jr})$

$F_{i\to j, \, r\to s} = \frac{\delta_{is}(1 - \delta_{jr})}{k_i - 1}$

where $k_i$ is the degree of vertex $i$ and $\delta$ is the Kronecker delta.

Unlike the adjacency or graph Laplacian matrices, whose spectra in sparse networks are distorted by high-degree hubs, the bulk of complex eigenvalues of $B$ and $F$ is confined within a circle centered at the origin (radius $\sqrt{c}$ for $B$ , where $c$ is the leading eigenvalue, and $\sqrt{\langle k/(k-1) \rangle / \langle k \rangle} \le 1$ for $F$ ). The number of real eigenvalues located outside this circular bulk provides an accurate estimate of the number of clusters $q$ down to the information-theoretic detectability threshold.
Knowl 6 — Degree-Corrected Stochastic Block Models and Hierarchical Description Length
model/method
To perform community detection via statistical inference while accounting for degree heterogeneity, the Degree-Corrected Stochastic Block Model (DCSBM) maximizes the unnormalized log-likelihood for a partition $g$ into $q$ groups:

$L_{\text{DC}}(G|g) = \sum_{r,s=1}^q e_{rs} \log \left( \frac{e_{rs}}{e_r e_s} \right)$

where $e_{rs}$ is the number of edges connecting group $r$ to group $s$ , and $e_r = \sum_s e_{rs}$ is the total degree of vertices in group $r$ .

Direct maximization of $L_{\text{DC}}(G|g)$ over all possible partitions leads to overfitting, yielding the trivial partition where each node is its own cluster ( $q=n$ ). Regularization is achieved by minimizing the total description length $\Sigma$ , which measures the total information necessary to describe both the fitted model parameters and the data given the model. While standard flat SBM description length minimization has a resolution limit where minimum resolvable block size scales as $\sqrt{n}$ , a nested hierarchical formulation of stochastic block models reduces the resolution limit to $\log n$ .
Knowl 7 — Map Equation and Infomap for Flow-Based Clustering
model/method
The map equation formulates community detection as the problem of finding the optimal compression of a random walk trajectory on a network. The objective is to minimize the description length of an infinite random walk by exploiting modular organization:
1. Vertices within the same community share a reusable set of codewords (analogous to local street names).
2. Entering or exiting a community requires an explicit boundary codeword identifying the community (analogous to city names).
The description length $L(\mathsf{M})$ for a partition $\mathsf{M}$ combines the Shannon entropy of inter-module transitions with the area-weighted Shannon entropies of intra-module steps, weighted by the stationary visit rates of the random walk. The Infomap algorithm searches for the partition that minimizes $L(\mathsf{M})$ , naturally capturing dynamic flow bottlenecks and directional constraints on directed networks.
Knowl 8 — Spurious Community Detection and Significance Testing Against Null Models
limitation
Sparse random graphs without built-in group structure (such as Erdős-Rényi graphs or configuration models) exhibit local density fluctuations. Optimization algorithms (e.g., modularity maximization) partition these purely random graphs into apparent clusters with high nominal quality scores.

To ensure identified clusters are not artifacts of random fluctuations, candidate clusterings must be evaluated against null models:
- $p$ -value Evaluation: Calculating whether cluster properties (e.g., internal edge density) deviate significantly ( $p < 0.05$ ) from ensembles generated by the configuration model preserving the degree distribution.
- $z$ -score of Quality Function: Evaluating $z = (Q_{\text{max}} - \langle Q_{\text{rand}} \rangle) / \sigma_Q^{\text{rand}}$ , where $\langle Q_{\text{rand}} \rangle$ and $\sigma_Q^{\text{rand}}$ are the mean and standard deviation of maximum modularity over randomized graphs (taking into account non-Gaussian distributions).
- Perturbation Robustness: Introducing edge rewiring or bootstrap resampling to assess the stability of the partition against noise.
Knowl 9 — Mismatch Between Topological Communities and Metadata Annotations
empirical result
Systematic empirical comparisons across large-scale social, technological, and information networks reveal that structural partitions identified by community detection algorithms generally show low Normalized Mutual Information (NMI) with metadata-derived groups (such as user interests, departments, or product categories).

While small networks (e.g., Zachary's karate club) exhibit close alignment between metadata and topological structure, metadata in large real networks is typically noisy, non-exhaustive, and represents overlapping functional attributes rather than topological edge concentrations. Consequently, vertex metadata should not be treated as a definitive ground-truth benchmark for topological clustering algorithms. Generative models that couple network structure and metadata (e.g., multilayer SBMs) are required to test whether annotations correlate with structural divisions.
Knowl 10 — Normalized Mutual Information Bias vs. Variation of Information Metric
model/method
When comparing a detected partition $\mathcal{Y}$ against a reference partition $\mathcal{X}$ with joint distribution $P(x, y) = n_{xy}/n$ , two information-theoretic measures are widely used:
- Normalized Mutual Information (NMI): $I_{\text{norm}}(\mathcal{X}, \mathcal{Y}) = \frac{2 I(X, Y)}{H(X) + H(Y)}$ where $I(X, Y)$ is mutual information and $H(X), H(Y)$ are Shannon entropies. NMI is sensitive to the number of clusters $q_Y$ in the detected partition, systematically yielding higher scores for over-refined partitions with large $q_Y$ , which distorts algorithm comparisons.
- Variation of Information (VI): $V(\mathcal{X}, \mathcal{Y}) = H(X|Y) + H(Y|X)$ VI defines a true metric in the space of partitions, satisfying non-negativity, symmetry, and the triangle inequality. VI is strictly local: differences in one region of the graph contribute to the distance independently of how the remainder of the graph is partitioned, with maximum value bounded by $\log n$ .
Knowl 11 — Network Community Profile and Core-Periphery Architecture of Real Networks
empirical result
The Network Community Profile (NCP) measures the minimum conductance $C_C = k_C^{\text{ext}} / k_C$ across subgraphs of size $k$ as a function of $k$ , where $k_C^{\text{ext}}$ is the external degree and $k_C$ is the total volume of community $C$ .

In many large real-world social and information networks, the NCP follows a characteristic U-shaped profile: minimum conductance decreases with community size up to roughly $k \approx 100$ vertices, and then increases monotonically for larger subgraphs. This demonstrates that the best separated, highest-quality communities are small peripheral subgraphs (whiskers) attached to the network by few links, whereas larger communities are less cohesive and blend into a dense core without clear separation.
Knowl 12 — Comparative Performance of Line Graph Edge Clustering vs. Vertex Clustering
empirical result
Clustering edges via the line graph $L(G)$ —where vertices of $L(G)$ represent edges of $G$ , connected when they share a node in $G$ —has been proposed as an approach to detect overlapping and hierarchical communities simultaneously.

Empirical testing on annotated real-world networks and synthetic benchmarks using algorithms like OSLOM shows that edge clustering on line graphs does not outperform vertex clustering in recovering ground-truth overlapping partitions. In line graphs, original high-degree hub vertices are transformed into large cliques that distort community boundaries. Furthermore, empirical analyses indicate that real overlapping regions are frequently denser in edges than non-overlapping regions (dense overlaps), which contradicts the sparse boundary overlap assumption underlying standard line graph representations.

Coverage note — Omitted introductory historical summaries of classic social network analysis concepts (e.g., n-clans, k-plexes, Bron-Kerbosch clique search), standard generic data clustering methods (e.g., k-means), and software package directory listings (Section V), as they do not represent the paper's core analytical contributions.

References

1.Aggarwal, C. C., and S. Y. Philip, 2005, in Proc. of SIAM Int. Conf. on Data Mining (SDM) (SIAM), pp. 56–67.
2.Ahn, Y.-Y., J. P. Bagrow, and S. Lehmann, 2010, Nature 466(7307), 761.
3.Aicher, C., A. Z. Jacobs, and A. Clauset, 2014, J. Complex Netw. 3(2), 221.
4.Airoldi, E. M., D. M. Blei, S. E. Fienberg, and E. P. Xing, 2008, J. Mach. Learn. Res. 9, 1981.
5.Alba, R. D., 1973, J. Math. Sociol. 3, 113.
6.Albert, R., H. Jeong, and A.-L. Barab´asi, 1999, Nature 401, 130.
7.Angel, O., J. Friedman, and S. Hoory, 2015, Trans. Am. Math. Soc. 367(6), 4287.
8.Arenas, A., A. D´ıaz-Guilera, and C. J. P´erez-Vicente, 2006, Phys. Rev. Lett. 96(11), 114102.
9.Arenas, A., A. Fern´andez, S. Fortunato, and S. G´omez, 2008a, J. Phys. A 41(22), 224001.
10.Arenas, A., A. Fern´andez, and S. G´omez, 2008b, New J. Phys. 10(5), 053039.
11.Asur, S., S. Parthasarathy, and D. Ucar, 2007, in KDD ’07: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (ACM, New York, NY, USA), pp. 913–921.
12.Ball, B., B. Karrer, and M. E. J. Newman, 2011, Phys. Rev. E 84, 036103.
13.Barab´asi, A.-L., 2010, Bursts: the hidden patterns behind everything we do, from your e-mail to bloody crusades (Penguin).
14.Barber, M. J., 2007, Phys. Rev. E 76(6), 066102.
15.Barrat, A., M. Barth´elemy, and A. Vespignani, 2008, Dynamical processes on complex networks (Cambridge University Press, Cambridge, UK).
16.Baumes, J., M. K. Goldberg, M. S. Krishnamoorthy, M. M. Ismail, and N. Preston, 2005, in IADIS AC, edited by N. Guimaraes and P. T. Isaias (IADIS), pp. 97–104.
17.Baxter, R. J., 2007, Exactly solved models in statistical mechanics (Courier Corporation).
18.Ben-Hur, A., A. Elisseeff, and I. Guyon, 2001, in Pacific Symposium on Biocomputing, volume 7, pp. 6–17.
19.Benson, A. R., D. F. Gleich, and J. Leskovec, 2016, Science 353(6295), 163.
20.Blondel, V. D., J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, 2008, J. Stat. Mech. P10008.
21.Boccaletti, S., G. Bianconi, R. Criado, C. del Genio, J. G.-G. nes, M. Romance, I. Sendi˜na-Nadal, Z. Wang, and M. Zanin, 2014, Phys. Rep. 544(1), 1.
22.Boccaletti, S., M. Ivanchenko, V. Latora, A. Pluchino, and A. Rapisarda, 2007, Phys. Rev. E 75(4), 045102.
23.Bollob´as, B., 1980, Eur. J. Combin. 1(4), 311.
24.Bomze, I. M., M. Budinich, P. M. Pardalos, and M. Pelillo, 1999, in Handbook of Combinatorial Optimization, edited by D.-Z. Du and P. Pardalos (Kluwer Academic Publishers, Norwell, USA), pp. 1–74.
25.Bothorel, C., J. D. Cruz, M. Magnani, and B. Micenkova, 2015, Netw. Sci. 3(03), 408.
26.Brandes, U., D. Delling, M. Gaertler, R. G¨orke, M. Hoefer, Z. Nikoloski, and D. Wagner, 2008, IEEE Trans. Knowl. Data Eng. 20(2), 172.
27.Brennan, R. L., and R. J. Light, 1974, Br. J. Math. Stat. Psychol. 27(2), 154.
28.Brin, S., and L. E. Page, 1998, Comput. Netw. ISDN 30, 107.
29.Bron, C., and J. Kerbosch, 1973, Commun. ACM 16, 575.
30.Bruno, A. M., W. N. Frost, and M. D. Humphries, 2015, Neuron 86(1), 304 .
31.Bui, T. N., S. Chaudhuri, F. T. Leighton, and M. Sipser, 1987, Combinatorica 7(2), 171.
32.Caldarelli, G., 2007, Scale-free networks (Oxford University Press, Oxford, UK).
33.Chakrabarti, D., R. Kumar, and A. Tomkins, 2006, in KDD ’06: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (ACM, New York, NY, USA), pp. 554–560.
34.Chakraborty, T., A. Dalmia, A. Mukherjee, and N. Ganguly, 2016, preprint arXiv:1604.03512 .
35.Chi, Y., X. Song, D. Zhou, K. Hino, and B. L. Tseng, 2007, in KDD ’07: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (ACM, New York, NY, USA), pp. 153–162.
36.Clauset, A., 2005, Phys. Rev. E 72(2), 026132.
37.Clauset, A., M. E. J. Newman, and C. Moore, 2004, Phys. Rev. E 70(6), 066111.
38.Cohen, R., and S. Havlin, 2010, Complex Networks: Structure, Robustness and Function (Cambridge University Press, Cambridge, UK).
39.Collins, L. M., and C. W. Dent, 1988, Multivar. Behav. Res. 23(2), 231.
40.Cˆome, E., and P. Latouche, 2015, Stat. Modelling 15(6), 564.
41.Condon, A., and R. M. Karp, 2001, Random Struct. Algor. 18, 116.
42.Coscia, M., F. Giannotti, and D. Pedreschi, 2011, Stat. Anal. Data Min. 4(5), 512.
43.Danon, L., A. D´ıaz-Guilera, J. Duch, and A. Arenas, 2005, J. Stat. Mech. P09008.
44.Danon, L., J. Duch, A. Arenas, and A. D´ıaz-Guilera, 2007, in Large Scale Structure and Dynamics of Complex Networks: From Information Technology to Finance and Natural Science, edited by C. G. and V. A. (World Scientific, Singapore), pp. 93–114.
45.Darst, R. K., Z. Nussinov, and S. Fortunato, 2014, Phys. Rev. E 89(3), 032809.
46.Daudin, J.-J., F. Picard, and S. Robin, 2008, Stat. Comput. 18(2), 173.
47.Decelle, A., F. Krzakala, C. Moore, and L. Zdeborov´a, 2011, Phys. Rev. Lett. 107, 065701.
48.Delling, D., M. Gaertler, R. G¨orke, and D. Wagner, 2006, Experiments on comparing graph clusterings, Technical Report, Universit¨at Karlsruhe, Germany.
49.Delvenne, J.-C., S. N. Yaliraki, and M. Barahona, 2010, Proc. Natl. Acad. Sci. USA 107(29), 12755.
50.Dorogovtsev, S. N., and J. F. F. Mendes, 2013, Evolution of networks: From biological nets to the Internet and WWW (Oxford University Press).
51.Dyer, M. E., and A. M. Frieze, 1989, J. Algorithms 10(4), 451.
52.Erd¨os, P., and A. R´enyi, 1959, Publ. Math. Debrecen 6, 290.
53.Erd¨os, P., and A. R´enyi, 1960, Publ. Math. Inst. Hungar. Acad. Sci 5, 17.
54.Esquivel, A. V., and M. Rosvall, 2012, eprint arXiv:1202.0425.
55.Estrada, E., 2011, The structure of complex networks: theory and applications (Oxford University Press, UK).
56.Estrada, E., and P. A. Knight, 2015, A First Course in Network Theory (Oxford University Press, UK).
57.Evans, T. S., 2010, J. Stat. Mech. Theor. Exp. 2010(12), P12037.
58.Evans, T. S., and R. Lambiotte, 2009, Phys. Rev. E 80(1), 016105.
59.Expert, P., T. S. Evans, V. D. Blondel, and R. Lambiotte, 2011, Proc. Natl. Acad. Sci. USA 108(19), 7663.
60.Fienberg, S. E., and S. Wasserman, 1981, Sociol. Methodol. 12, 156.
61.Fortunato, S., 2010, Phys. Rep. 486, 75.
62.Fortunato, S., and M. Barth´elemy, 2007, Proc. Natl. Acad. Sci. USA 104, 36.
63.Fred, A., and A. K. Jain, 2003, in Computer Vision and Pattern Recognition, 2003. Proceedings. 2003 IEEE Computer Society Conference on (IEEE), volume 2, pp. II–128.
64.Gelman, A., J. B. Carlin, H. S. Stern, and D. B. Rubin, 2014, Bayesian Data Analysis, volume 2 (Taylor & Francis).
65.Girvan, M., and M. E. Newman, 2002, Proc. Natl. Acad. Sci. USA 99(12), 7821.
66.Goder, A., and V. Filkov, 2008, in ALENEX, pp. 109–117.
67.Good, B. H., Y.-A. de Montjoye, and A. Clauset, 2010, Phys. Rev. E 81(4), 046106.
68.Granell, C., R. K. Darst, A. Arenas, S. Fortunato, and S. G´omez, 2015, Phys. Rev. E 92(1), 012805.
69.Granell, C., S. G´omez, and A. Arenas, 2012, Int. J. Bifurcat. Chaos 22(07), 1250171.
70.Gr¨unwald, P. D., I. J. Myung, and M. A. Pitt, 2005, Advances in Minimum Description Length: Theory and Applications (MIT Press, Cambridge, USA).
71.Guimer`a, R., and L. A. N. Amaral, 2005, Nature 433, 895.
72.Guimer`a, R., and M. Sales-Pardo, 2009, Proc. Natl. Acad. Sci. USA 106(52), 22073.
73.Guimer`a, R., M. Sales-Pardo, and L. A. Amaral, 2004, Phys. Rev. E 70(2), 025101 (R).
74.Handcock, M. S., A. E. Raftery, and J. M. Tantrum, 2007, J. Roy. Stat. Soc. A 170(46), 1.
75.Hastings, M. B., 2006, Phys. Rev. E 74(3), 035102.
76.Holland, P., K. B. Laskey, and S. Leinhardt, 1983, Soc. Netw. 5, 109.
77.Holme, P., and J. Saram¨aki, 2012, Phys. Rep. 519(3), 97.
78.Hopcroft, J., O. Khan, B. Kulis, and B. Selman, 2004, Proc. Natl. Acad. Sci. USA 101, 5249.
79.Hric, D., R. K. Darst, and S. Fortunato, 2014, Phys. Rev. E 90, 062805.
80.Hric, D., T. P. Peixoto, and S. Fortunato, 2016, Phys. Rev. X 6, 031038.
81.Hu, Y., H. Chen, P. Zhang, M. Li, Z. Di, and Y. Fan, 2008, Phys. Rev. E 78(2), 026121.
82.Huang, J., H. Sun, Y. Liu, Q. Song, and T. Weninger, 2011, PLoS ONE 6(8), e23829.
83.Hubert, L., and P. Arabie, 1985, J. Classif. 2(1), 193.
84.H¨ullermeier, E., and M. Rifqi, 2009, in Joint 2009 International Fuzzy Systems Association World Congress and 2009 European Society of Fuzzy Logic and Technology Conference, IFSA-EUSFLAT 2009, pp. 1294–1298.
85.Jaccard, P., 1901, Bull. Soc. Vaud. Sci. Nat. 37, 547.
86.Jain, A. K., M. N. Murty, and P. J. Flynn, 1999, ACM Comput. Surv. 31(3), 264.
87.Jeub, L. G., P. Balachandran, M. A. Porter, P. J. Mucha, and M. W. Mahoney, 2015, Phys. Rev. E 91(1), 012821.
88.Karrer, B., E. Levina, and M. E. J. Newman, 2008, Phys. Rev. E 77(4), 046119.
89.Karrer, B., and M. E. J. Newman, 2011, Phys. Rev. E 83, 016107.
90.Kivel¨a, M., A. Arenas, M. Barthelemy, J. P. Gleeson, Y. Moreno, and M. A. Porter, 2014, J. Complex Netw. 2(3), 203.
91.Krzakala, F., C. Moore, E. Mossel, J. Neeman, A. Sly, L. Zdeborov´a, and P. Zhang, 2013, Proc. Natl. Acad. Sci. USA 110(52), 20935.
92.Lambiotte, R., J. . Delvenne, and M. Barahona, 2008, eprint arXiv:0812.1770.
93.Lancichinetti, A., and S. Fortunato, 2009, Phys. Rev. E 80(1), 016118.
94.Lancichinetti, A., and S. Fortunato, 2009, Phys. Rev. E 80(5), 056117.
95.Lancichinetti, A., and S. Fortunato, 2011, Phys. Rev. E 84, 066122.
96.Lancichinetti, A., and S. Fortunato, 2012, Sci. Rep. 2, 336.
97.Lancichinetti, A., and S. Fortunato, 2014, Phys. Rev. E 89, 049902.
98.Lancichinetti, A., S. Fortunato, and J. Kertesz, 2009, New J. Phys. 11(3), 033015.
99.Lancichinetti, A., S. Fortunato, and F. Radicchi, 2008, Phys. Rev. E 78(4), 046110.
100.Lancichinetti, A., M. Kivel¨a, J. Saram¨aki, and S. Fortunato, 2010, PLoS ONE 5(8), e11976.
101.Lancichinetti, A., F. Radicchi, J. J. Ramasco, and S. Fortunato, 2011, PLoS ONE 6(4), e18961.
102.Larremore, D. B., A. Clauset, and A. Z. Jacobs, 2014, Phys. Rev. E 90(1), 012805.
103.Latouche, P., E. Birmele, and C. Ambroise, 2012, Stat. Modelling 12(1), 93.
104.Leng, M., Y. Yao, J. Cheng, W. Lv, and X. Chen, 2013, in Database Systems for Advanced Applications (Springer), pp. 324–338.
105.Leskovec, J., K. J. Lang, A. Dasgupta, and M. W. Mahoney, 2009, Internet Math. 6(1), 29.
106.Lewis, A., N. Jones, M. Porter, and C. Deane, 2010, BMC Syst. Biol. 4(1), 100.
107.Liben-Nowell, D., J. Novak, R. Kumar, P. Raghavan, and A. Tomkins, 2005, Proc. Natl. Acad. Sci. USA 102(33), 11623.
108.Lin, Y.-R., Y. Chi, S. Zhu, H. Sundaram, and B. L. Tseng, 2008, in WWW ’08: Proceeding of the 17th International Conference on World Wide Web (ACM, New York, NY, USA), pp. 685–694.
109.Luccio, F., and M. Sami, 1969, IEEE Trans. Circuit Th. CT 16, 184.
110.Luce, R. D., 1950, Psychometrika 15(2), 169.
111.Luce, R. D., and A. D. Perry, 1949, Psychometrika 14(2), 95.
112.Lusseau, D., 2003, Proc. Royal Soc. London B 270, S186.
113.von Luxburg, U., 2006, A tutorial on spectral clustering, Technical Report 149, Max Planck Institute for Biological Cybernetics.
114.Mackay, D. J. C., 2003, Information Theory, Inference, and Learning Algorithms (Cambridge University Press, Cambridge, UK).
115.MacMahon, M., and D. Garlaschelli, 2015, Phys. Rev. X 5, 021006.
116.MacQueen, J. B., 1967, in Proc. of the fifth Berkeley Symposium on Mathematical Statistics and Probability, edited by L. M. L. Cam and J. Neyman (University of California Press, Berkeley, USA), volume 1, pp. 281–297.
117.Malliaros, F. D., and M. Vazirgiannis, 2013, Phys. Rep. 533(4), 95.
118.McDaid, A. F., D. Greene, and N. Hurley, 2011, eprint arXiv:1110.2515.
119.Meil˘a, M., 2005, in Proceedings of the 22nd International Conference on Machine Learning (ACM), pp. 577–584.
120.Meil˘a, M., 2007, J. Multivar. Anal. 98(5), 873.
121.Meil˘a, M., and D. Heckerman, 2001, Mach. Learn. 42(1), 9.
122.Mezard, M., G. Parisi, and M. Virasoro, 1987, Spin glass theory and beyond (World Scientific Publishing Company, Singapore).
123.Mokken, R. J., 1979, Qual. Quant. 13(2), 161.
124.Molloy, M., and B. Reed, 1995, Random Struct. Algor. 6, 161.
125.Moody, J., and D. R. White, 2003, Am. Sociol. Rev. 68(1), 103.
126.Moore, C., X. Yan, Y. Zhu, J.-B. Rouquier, and T. Lane, 2011, in Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (ACM, New York, NY, USA), KDD ’11, pp. 841–849.
127.Mucha, P. J., T. Richardson, K. Macon, M. A. Porter, and J. P. Onnela, 2010, Science 328(5980), 876.
128.Nadakuditi, R. R., and M. E. J. Newman, 2012, Phys. Rev. Lett. 108, 188701.
129.Newman, M., 2010, Networks: An Introduction (Oxford University Press, Inc., New York, NY, USA).
130.Newman, M., 2013, eprint arXiv:1308.6494.
131.Newman, M., 2016, eprint arXiv:1606.02319.
132.Newman, M., and A. Clauset, 2016, Nat. Commun. 7, 11863.
133.Newman, M. E. J., 2004, Phys. Rev. E 70(5), 056131.
134.Newman, M. E. J., 2004a, Eur. Phys. J. B 38, 321.
135.Newman, M. E. J., 2004b, Phys. Rev. E 69(6), 066133.
136.Newman, M. E. J., 2006, Proc. Natl. Acad. Sci. USA 103, 8577.
137.Newman, M. E. J., 2012, Nat. Phys. 8(1), 25.
138.Newman, M. E. J., and M. Girvan, 2004, Phys. Rev. E 69(2), 026113.
139.Newman, M. E. J., and E. A. Leicht, 2007, Proc. Natl. Acad. Sci. USA 104, 9564.
140.Newman, M. E. J., and G. Reinert, 2016, Phys. Rev. Lett. 117, 078301.
141.Onnela, J.-P., D. J. Fenn, S. Reid, M. A. Porter, P. J. Mucha, M. D. Fricker, and N. S. Jones, 2012, Phys. Rev. E 86, 036104.
142.Palla, G., A.-L. Barab´asi, and T. Vicsek, 2007, Nature 446, 664.
143.Palla, G., I. Der´enyi, I. Farkas, and T. Vicsek, 2005, Nature 435, 814.
144.Parthasarathy, S., Y. Ruan, and V. Satuluri, 2011, in Social Network Data Analytics (Springer), pp. 79–113.
145.Peel, L., 2015, J. Complex Netw. 3(3), 431.
146.Peixoto, T. P., 2013, Phys. Rev. Lett. 110, 148701.
147.Peixoto, T. P., 2014, Phys. Rev. X 4, 011047.
148.Peixoto, T. P., 2015a, Phys. Rev. E 92(4), 042807.
149.Peixoto, T. P., 2015b, Phys. Rev. X 5, 011033.
150.Peixoto, T. P., and M. Rosvall, 2015, eprint arXiv:1509.04740.
151.Perotti, J. I., C. J. Tessone, and G. Caldarelli, 2015, Phys. Rev. E 92, 062825.
152.Persson, C., L. Bohlin, D. Edler, and M. Rosvall, 2016, eprint arXiv:1606.08328.
153.Pons, P., and M. Latapy, 2005, in International Symposium on Computer and Information Sciences (Springer), pp. 284–293.
154.Porter, M. A., J.-P. Onnela, and P. J. Mucha, 2009, Notices Amer. Math. Soc. 56(9), 1082.
155.Radicchi, F., C. Castellano, F. Cecconi, V. Loreto, and D. Parisi, 2004, Proc. Natl. Acad. Sci. USA 101, 2658.
156.Raghavan, U. N., R. Albert, and S. Kumara, 2007, Phys. Rev. E 76(3), 036106.
157.Rand, W. M., 1971, J. Am. Stat. Assoc. 66(336), 846.
158.Reichardt, J., and S. Bornholdt, 2006, Phys. Rev. E 74(1), 016110.
159.Rissanen, J., 1978, Automatica 14, 465.
160.Ronhovde, P., and Z. Nussinov, 2009, Phys. Rev. E 80(1), 016109.
161.Ronhovde, P., and Z. Nussinov, 2010, Phys. Rev. E 81, 046114.
162.Rosvall, M., and C. T. Bergstrom, 2008, Proc. Natl. Acad. Sci. USA 105, 1118.
163.Rosvall, M., and C. T. Bergstrom, 2010, PLoS one 5(1), e8694.
164.Rosvall, M., and C. T. Bergstrom, 2011, PLoS ONE 6(4), e18209.
165.Rosvall, M., A. V. Esquivel, A. Lancichinetti, J. D. West, and R. Lambiotte, 2014, Nat. Commun. 5.
166.Sarkar, P., and A. W. Moore, 2005, ACM SIGKDD Explor. Newsl. 7(2), 31.
167.Sarkar, S., S. Chawla, P. A. Robinson, and S. Fortunato, 2016, Phys. Rev. E 93, 062312.
168.Schaeffer, S. E., 2007, Comput. Sci. Rev. 1(1), 27.
169.Scott, J., 2000, Social Network Analysis: A Handbook (SAGE Publications, London, UK).
170.Seidman, S. B., and B. L. Foster, 1978, J. Math. Sociol. 6, 139.
171.Serrour, B., A. Arenas, and S. G´omez, 2011, Comput. Commun. 34(5), 629 .
172.Simon, H., 1962, Proc. Am. Phil. Soc. 106(6), 467.
173.Singh, A., and M. D. Humphries, 2015, Scientific reports 5, 8828.
174.Snijders, T., and K. Nowicki, 1997, J. Classif. 14, 75.
175.Spiliopoulou, M., 2011, in Social Network Data Analytics, edited by C. C. Aggarwal (Springer US), pp. 149–175.
176.Strehl, A., and J. Ghosh, 2002, J. Mach. Learn. Res. 3, 583, ISSN 1532-4435.
177.Topchy, A., A. K. Jain, and W. Punch, 2005, IEEE Trans. Pattern Anal. Mach. Intell. 27, 1866.
178.Traag, V. A., and J. Bruggeman, 2009, Phys. Rev. E 80(3), 036115.
179.Traag, V. A., P. Van Dooren, and Y. Nesterov, 2011, Phys. Rev. E 84, 016114.
180.Traud, A., E. Kelsic, P. Mucha, and M. Porter, 2011, SIAM Review 53(3), 526.
181.Traud, A. L., P. J. Mucha, and M. A. Porter, 2012, Physica A 391(16), 4165.
182.Van Dongen, S., 2000, Graph Clustering by Flow Simulation, Ph.D. thesis, Dutch National Research Institute for Mathematics and Computer Science, University of Utrecht, Netherlands.
183.Viamontes Esquivel, A., and M. Rosvall, 2011, Phys. Rev. X 1, 021025.
184.Wasserman, S., and K. Faust, 1994, Social network analysis (Cambridge University Press, Cambridge, UK).
185.Xie, J., S. Kelley, and B. K. Szymanski, 2013, ACM Comput. Surv. 45(4), 43:1.
186.Xie, J., and B. K. Szymanski, 2012, in Proceedings of the 16th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining - Volume Part II (Springer-Verlag, Berlin, Heidelberg), PAKDD’12, pp. 25–36.
187.Xu, R., and D. Wunsch, 2008, Clustering (John Wiley & Sons, Piscataway, NJ, USA).
188.Yang, J., and J. Leskovec, 2012a, in Data Mining (ICDM), 2012 IEEE 12th International Conference on (IEEE), pp. 1170–1175.
189.Yang, J., and J. Leskovec, 2012b, in Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics (ACM, New York, NY, USA), MDS’12, pp. 3:1–3:8.
190.Yang, J., and J. Leskovec, 2013, in Proceedings of the Sixth ACM International Conference on Web Search and Data Mining (ACM, New York, NY, USA), WSDM’13, pp. 587–596.
191.Yang, J., and J. Leskovec, 2014, ACM Trans. Intell. Syst. Technol. 5(2), 26:1.
192.Yang, J., J. McAuley, and J. Leskovec, 2013, in 2013 IEEE 13th International Conference on Data mining (ICDM) (IEEE), pp. 1151–1156.
193.Yang, T., Y. Chi, S. Zhu, Y. Gong, and R. Jin, 2009, in SIAM Int. Conf. on Data Mining (SDM) (SIAM), volume 9, pp. 990–1001.
194.Zachary, W. W., 1977, J. Anthropol. Res. 33, 452.
195.Zanghi, H., C. Ambroise, and V. Miele, 2008, Pattern Recogn. 41(12), 3592.
196.Zhang, P., 2015, J. Stat. Mech. Theor. Exp. P11006.
197.Zhang, P., and C. Moore, 2014, Proc. Natl. Acad. Sci. 111(51), 18144.
198.Zhang, P., C. Moore, and M. Newman, 2016, Phys. Rev. E 93(1), 012303.
199.Zhang, X., T. Martin, and M. E. Newman, 2015, Phys. Rev. E 91(3), 032803.
200.Zhou, H., 2003a, Phys. Rev. E 67(6), 061901.
201.Zhou, H., 2003b, Phys. Rev. E 67(4), 041908.
202.Zhou, H., and R. Lipowsky, 2004, Lect. Notes Comp. Sci. 3038, 1062.

Citation

MLA

Fortunato, S., and D. Hric. “Community Detection in Networks: A User Guide”. Physics Reports, vol. 659, 2016, pp. 1–4, https://doi.org/10.1016/j.physrep.2016.09.002.

APA

Fortunato, S., & Hric, D. (2016). Community detection in networks: A user guide. Physics Reports, 659, 1–44. https://doi.org/10.1016/j.physrep.2016.09.002

Chicago

Fortunato, S., and D. Hric. 2016. “Community Detection in Networks: A User Guide”. Physics Reports 659: 1–44. https://doi.org/10.1016/j.physrep.2016.09.002.

Harvard

Fortunato, S. and Hric, D. (2016) “Community detection in networks: A user guide”, Physics Reports, 659, pp. 1–44. Available at: https://doi.org/10.1016/j.physrep.2016.09.002.

Vancouver

1. Fortunato S, Hric D (2016) Community detection in networks: A user guide. Physics Reports 659:1–44

BibTeX

@article{Fortunato_2016, title={Community detection in networks: A user guide}, volume={659}, ISSN={0370-1573}, url={http://dx.doi.org/10.1016/j.physrep.2016.09.002}, DOI={10.1016/j.physrep.2016.09.002}, journal={Physics Reports}, publisher={Elsevier BV}, author={Fortunato, Santo and Hric, Darko}, year={2016}, month=Nov, pages={1–44} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Community detection in networks: A user guide

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Detectability Threshold in Sparse Assortative Stochastic Block Models

Knowl 2 — Resolution Limit and Scale Bias of Modularity Maximization

Knowl 3 — Probabilistic Definitions of Strong and Weak Communities

Knowl 4 — Iterative Consensus Clustering Algorithm

Knowl 5 — Inferring Cluster Count via Non-Backtracking and Flow Matrix Spectra

Knowl 6 — Degree-Corrected Stochastic Block Models and Hierarchical Description Length

Knowl 7 — Map Equation and Infomap for Flow-Based Clustering

Knowl 8 — Spurious Community Detection and Significance Testing Against Null Models

Knowl 9 — Mismatch Between Topological Communities and Metadata Annotations

Knowl 10 — Normalized Mutual Information Bias vs. Variation of Information Metric

Knowl 11 — Network Community Profile and Core-Periphery Architecture of Real Networks

Knowl 12 — Comparative Performance of Line Graph Edge Clustering vs. Vertex Clustering

References

Citation

BibTeX

Access the Paper