Community Detection Part 2 — Higher-Order Structures, Dynamic Networks, and the Frontier

Introduction — Recap and Motivation for Part 2

Part 1 covered the fundamentals of Community Detection: the history, Modularity Q formulation, standard algorithms (Louvain, Leiden, Infomap, SBM), and fundamental difficulties like the Resolution Limit and detectability threshold.

However, the methods in Part 1 share implicit assumptions:

1. Only pairwise edges — Communities defined solely by whether edges exist between pairs of nodes
2. Static (single snapshot) graphs — The network is assumed not to change over time
3. Single type of relationship — Only one kind of connection between nodes

Real-world networks violate all these assumptions. In social networks, triadic closure ("a friend of a friend is a friend") matters; relationships evolve over time; and the same people may be connected by "friendship," "collaboration," and "hobby" relationships simultaneously.

This sequel dives into three research directions that address these complexities:

• Higher-Order community detection — Motifs, hypergraphs, simplicial complexes
• Dynamic network community detection — Tracking communities in evolving graphs
• Multiplex network community detection — Integrating multiple relationship layers

Part I: Higher-Order Community Detection

Why Edges Alone Are Insufficient

Most algorithms from Part 1, including Modularity-based methods, define communities as "subgraphs with dense edges." But this definition has a blind spot.

Consider two graphs:

• Graph A: 6 nodes, 9 edges. Every edge belongs to a triangle (3 triangles total)
• Graph B: 6 nodes, 9 edges. Zero triangles. A complete bipartite graph $K_{3,3}$

Both have the same edge density, but structurally they are completely different. Graph A exhibits strong local cohesion (triadic closure) — in social networks, this reflects "friends of friends become friends." Graph B does not.

Edge-density-based methods cannot distinguish them. This is precisely the motivation for considering higher-order structures.

Clique Percolation Method (CPM) — Pioneering Higher-Order Approach

The first influential method leveraging higher-order structures was the Clique Percolation Method (CPM) by Palla, Derényi, Farkas & Vicsek (2005). CPM’s idea is straightforward:

1. Enumerate all $k$-cliques (complete subgraphs on $k$ nodes) in the network
2. Consider two $k$-cliques "adjacent" if they share $k-1$ nodes
3. Define a community as the union of all $k$-cliques reachable through adjacent $k$-cliques

For example, in a protein-protein interaction (PPI) network, applying CPM with $k=4$ uses sets of four mutually interacting proteins as building blocks to detect larger functional modules.

A key feature of CPM is that it naturally detects overlapping communities — nodes can belong to multiple communities simultaneously. Since $k$-clique chains can intersect, a node belonging to multiple chains holds membership in multiple communities. In real social networks, one person typically belongs to "work colleagues," "university friends," and "hobby groups" simultaneously, and CPM reflects this reality.

However, CPM has limitations: the choice of parameter $k$ significantly affects results, and in sparse networks, $k$-cliques may be too rare to form meaningful communities. CPM was specialized to $k$-cliques as its higher-order building block; the following sections generalize this idea to arbitrary network motifs.

Network Motifs: Foundations

A network motif is a small subgraph pattern that appears statistically significantly often in a network. The concept was established by Uri Alon and colleagues (Milo et al., 2002), who discovered that specific patterns like feed-forward loops appeared far more frequently in E. coli gene regulatory networks than in random networks.

Motifs are important because they carry functional meaning:

• Triangles: Trust and information transfer efficiency in social networks. "If A trusts B and B trusts C, then A is likely to trust C"
• Feed-forward loops: Signal filtering in gene regulation
• 4-cycles: Foundation for collaborative filtering in bipartite networks (user–product)

Benson-Gleich-Leskovec: Motif-Based Community Detection (2016)

The most influential work on higher-order community detection is Benson, Gleich & Leskovec's "Higher-order organization of complex networks" (Science, 2016). Their idea is elegant:

Define communities based on motif density, not edge density.

The Core: Motif Conductance

Standard Conductance (from Part 1):

Benson et al. extended this to Motif Conductance for motif $M$:

Where:

• $\text{cut}_M(S, \bar{S})$: Number of motif $M$ instances with nodes in both $S$ and $\bar{S}$ ("boundary-crossing motifs")
• $\text{vol}_M(S)$: Sum of motif-weighted degrees of nodes in $S$. Formally, $\text{vol}_M(S) = \sum_{i \in S} d_i^{(M)}$, where $d_i^{(M)} = \sum_j W_{ij}^{(M)}$ (row sum of the motif-weighted adjacency matrix defined below)

Intuitively, smaller $\phi_M(S)$ means "motif $M$ is dense inside community $S$ with few boundary-crossing motifs."

Motif-Weighted Adjacency Matrix

To minimize Motif Conductance, Benson et al. construct the motif-weighted adjacency matrix $W^{(M)}$:

This matrix is used to build the motif-weighted Laplacian for spectral clustering:

where $D^{(M)}$ is the diagonal degree matrix of $W^{(M)}$.

Crucially, Benson et al. proved a Cheeger-like inequality for the motif-weighted Laplacian (Benson et al., 2016):

where $\lambda_2^{(M)}$ is the second smallest eigenvalue of the motif-weighted Laplacian and $\phi_M^*$ is the optimal Motif Conductance. This guarantees that spectral methods provide bounded approximations to the optimal partition — the same structural result as the classical Cheeger inequality from Part 1.

The following demo shows the concrete process of triangle-motif-based community detection:

Why Motif-Based Methods Excel

Compared to edge-based methods, motif-based approaches offer:

1. Richer information: Beyond 2-body (pairwise) relationships, they leverage patterns of 3 or more nodes
2. Domain knowledge integration: Choose motifs suited to your domain — feed-forward loops for biology, triangles for social networks
3. Noise robustness: Random edges rarely form motifs, so motif density is robust to random noise

Hypergraph Community Detection

While motif-based approaches extend edges to consider motif density, another direction uses hypergraphs.

In standard graphs, edges connect exactly 2 nodes. In hypergraphs, a hyperedge directly connects any number of nodes:

This naturally models multi-body relationships:

• Paper co-authorship (3+ authors)
• Email CC (multiple recipients)
• Chemical reactions (multiple reactants)

For example, in the DBLP co-authorship network, papers with 3+ authors are naturally modeled as hyperedges. Decomposing such a paper into 3 pairwise edges loses the information that these authors collaborated simultaneously on the same work. Hypergraphs preserve this multi-body relationship exactly.

Community detection on hypergraphs uses several approaches:

Clique Expansion: Convert each hyperedge $e = \{v_1, ..., v_k\}$ into $\binom{k}{2}$ pairwise edges and process as a standard graph. However, this loses information — 4 people in a single meeting (one hyperedge) differs from 4 people having 6 separate conversations (6 edges).

Direct Hypergraph Methods: Spectral clustering on hypergraphs uses the hypergraph Laplacian introduced by Zhou, Huang & Schölkopf (2006):

where $H$ is the incidence matrix (node × hyperedge), $D_v$ is the node degree matrix, $W_e$ is the hyperedge weight matrix, and $D_e$ is the diagonal matrix of hyperedge degrees (sizes).

Kumar et al. (2020) took a different approach, preserving hypergraph structure while iteratively maximizing a weighted modularity that leverages hyperedge sizes for flexible community quality definitions.

Simplicial Complex Approaches

A further development beyond hypergraphs uses simplicial complexes from topology. A simplicial complex is a collection of $k$-simplices ($k+1$ nodes) satisfying the inclusion condition: every subset of a simplex is also a simplex in the complex.

• 0-simplex: node
• 1-simplex: edge
• 2-simplex: triangle (3 nodes + 3 edges)
• $k$-simplex: complete graph on $(k+1)$ nodes (plus all faces)

On simplicial complexes, the Hodge Laplacian can be defined using boundary operators on $k$-chains, measuring "smoothness" of flows. This enables community detection based on edge flows (1-chains). Schaub et al. (2020) proposed a signal processing framework using the Hodge Laplacian spectrum.

So far, we have explored leveraging higher-order structures in static graphs: edges → cliques → motifs → hyperedges → simplices, progressively expanding the "expressive power" of relationships. But real networks have another crucial dimension: time. Social media friendships change daily, co-authorship networks grow yearly. How to handle these temporal dynamics is the next major research challenge.

Part II: Dynamic Network Community Detection

Formulating Dynamic Networks

Real networks change over time. Friendship formation and dissolution, paper publication and citation, protein expression changes — these are all dynamic network problems.

Two main representations exist:

Discrete snapshot model: A sequence of graph snapshots $G_1, G_2, ..., G_T$ at times $t_1, t_2, ..., t_T$. Each $G_t = (V_t, E_t)$ is a static graph.

Continuous-time model: Edge appearances and disappearances treated as timestamped events $(i, j, t_{\text{start}}, t_{\text{end}})$. Retains more detail but complicates analysis.

The snapshot model is widely used in practice, but the choice of time granularity (snapshot interval) significantly affects results.

Community Lifecycle

The core challenge in dynamic community detection is not just finding communities at each time step, but tracking communities through time. Communities experience lifecycle events:

Accurately identifying these events requires matching communities across consecutive snapshots.

The following demo shows community lifecycle events in action:

Approach 1: Independent Detection + Matching (Two-Stage)

The simplest method applies community detection independently to each snapshot, then matches communities across consecutive time steps:

Two-Stage Approach:
  1. Detect communities C_t = {C_t^1, C_t^2, ...} independently at each time t
  2. Match between adjacent times t, t+1 using Jaccard coefficient:
     J(C_t^i, C_{t+1}^j) = |C_t^i ∩ C_{t+1}^j| / |C_t^i ∪ C_{t+1}^j|
  3. Identify lifecycle events from matching:
     - C_t^i with no match → Death
     - C_{t+1}^j with no source → Birth
     - 1-to-many → Split
     - Many-to-1 → Merge

The advantage: any static community detection algorithm works "as is." Louvain, Leiden, Infomap — any method from Part 1 can be applied per snapshot.

The critical drawback: temporal coherence is not guaranteed. Minor noise (a few edges added or removed) can dramatically alter community structure, making stable communities appear to fluctuate wildly.

Approach 2: Evolutionary Clustering (2006)

Chakrabarti, Kumar & Tomkins (KDD 2006) proposed Evolutionary Clustering as a systematic solution for temporal coherence.

The core idea: add a "change cost from the previous time step" to each time step's objective function:

• $\text{quality}(C_t, G_t)$: Quality of partition $C_t$ for graph $G_t$ (e.g., Modularity Q)
• $\text{similarity}(C_t, C_{t-1})$: Similarity to previous partition (e.g., NMI, Jaccard)
• $\alpha \in [0, 1]$: Trade-off between "fitting current data" and "consistency with past"

$\alpha = 1$ means fully independent detection (ignoring history); $\alpha = 0$ means keeping the exact same structure (ignoring new data).

In practice, choosing $\alpha$ is itself a challenge. During periods of rapid network change (e.g., a global event on social media), $\alpha$ should be large; during stable periods, it should be small — but detecting when to switch is difficult.

Evolutionary Clustering was the first systematic formulation of dynamic community detection as an explicit optimization problem, influencing many subsequent methods.

Approach 3: Multislice Modularity (Mucha et al., 2010)

Mucha, Richardson, Macon, Porter & Onnela's "Community Structure in Time-Dependent, Multiscale, and Multiplex Networks" (Science, 2010) is the most influential work on dynamic community detection.

Their idea: stack time snapshots as "slices" and connect them with inter-slice coupling edges to form a super-graph:

Breaking down this formula:

Index meanings:

• $i, j$: nodes
• $s, r$: slices (time step or layer index)
• $g_{is}$: community assignment of node $i$ in slice $s$

Term 1: $\left( A_{ijs} - \gamma_s \frac{k_{is} k_{js}}{2m_s} \right) \delta_{sr}$

This is the "intra-slice" Modularity. The $\delta_{sr}$ restricts it to same-slice pairs ($s = r$). $\gamma_s$ is the resolution parameter (from Part 1), which can vary per slice.

Term 2: $\delta_{ij} \omega_{jsr}$

This is Mucha et al.'s innovation. $\delta_{ij}$ restricts it to the "same node," and $\omega_{jsr}$ is the inter-slice coupling strength. Intuitively, it "connects node $i$ at time $s$ to the same node $i$ at time $r$ with a virtual edge."

Choices for $\omega_{jsr}$:

• Couple only temporally adjacent snapshots: $\omega_{jsr} = \omega$ if $|s - r| = 1$
• Couple all snapshots uniformly: $\omega_{jsr} = \omega$ for all $s \neq r$
• Node- and time-dependent coupling: $\omega_{jsr}$ depends on $j, s, r$

Larger $\omega$ strengthens temporal coherence ("the same node should stay in the same community across time"); smaller $\omega$ gives more independence to each snapshot.

Normalization: $2\mu = \sum_{jr} \kappa_{jr}$, where $\kappa_{jr} = k_{jr} + c_{jr}$ (node $j$'s degree in slice $r$ plus its inter-slice coupling strength)

The breakthrough of this formulation:

1. Unifies dynamic and multiplex networks: Interpret slices as "time steps" for dynamic, or "layers" for multiplex
2. Leverages existing methods: This extended Modularity can be optimized with Louvain/Leiden-style greedy algorithms
3. Multiscale analysis: Varying $\gamma_s$ and $\omega$ explores structures at different scales

Approach 4: Tensor Decomposition

De Domenico et al. (2013) proposed a mathematical framework representing multiplex/dynamic networks as tensors.

A multiplex network with $L$ layers (or time snapshots) can be represented as a 4th-order tensor $\mathcal{M}$:

• $i, j$: nodes
• $\alpha, \beta$: layers
• $\mathcal{M}_{ij\alpha\alpha}$: edge weight between $i$ and $j$ in layer $\alpha$
• $\mathcal{M}_{ii\alpha\beta}$: coupling of node $i$ between layers $\alpha$ and $\beta$

Tensor decomposition (CP or Tucker decomposition) is applied to extract community structure. This is the multi-dimensional extension of matrix decomposition (PCA, NMF), simultaneously capturing structure in both node and layer dimensions.

The tensor approach offers mathematical generality but faces scalability challenges for large networks. Gauvin, Panisson & Cattuto (2014) applied this approach to face-to-face contact networks, successfully using non-negative tensor factorization (NTF) to simultaneously estimate community membership and temporal activity patterns.

Part II focused on tracking communities along the temporal axis, but Multislice Modularity and tensor decomposition frameworks are equally applicable to multiplex networks. Part III explores the challenges and methods specific to multiplex settings.

Part III: Multiplex Network Community Detection

What Is a Multiplex Network?

A multiplex network has multiple types of relationships (layers) among the same set of nodes.

Examples:

• Social media: "follow," "message," "like" as separate layers
• Transportation: "rail," "bus," "air" as separate layers
• Biology: "protein-protein interaction," "gene regulation," "metabolic pathway" as separate layers

Multiplex networks are a subclass of multilayer networks. The general formulation was systematized in Kivelä et al.'s (2014) survey; multiplex networks are the special case where the node set is identical across all layers.

Approach 1: Layer Aggregation

The simplest method aggregates all layer adjacency matrices into a single graph and applies standard community detection:

where $A^{(\alpha)}$ is layer $\alpha$'s adjacency matrix and $w_\alpha$ are weights.

This is easy but loses layer-specific information. A node that clearly belongs to community A in one layer and community B in another has this distinction erased by aggregation.

Approach 2: Multislice Modularity (Revisited)

The Mucha et al. (2010) Multislice Modularity introduced in the dynamic context applies directly to multiplex networks — simply interpret slices as "layers."

The coupling parameter $\omega$ controls cross-layer community consistency. Larger $\omega$ means the same node tends to belong to the same community across all layers.

Approach 3: Layer-Coupled Optimization

Interdonato, Tagarelli, Ienco, Sallaberry & Roche (2017) categorize multiplex community detection into three approaches:

1. Layer-independent: Detect independently per layer, merge results
2. Aggregation-based: Pre-aggregate layers
3. Layer-coupled: Optimize across all layers simultaneously

The third approach maximally leverages information but at higher computational cost.

GenLouvain: Practical Multislice Implementation

GenLouvain (Jutla, Jeub & Mucha, 2011–) is the widely-used practical implementation of Multislice Modularity optimization:

GenLouvain:
  Input: Multiplex/dynamic network (adjacency matrices A^(s), coupling ω)
  1. Build Multislice Modularity matrix B:
     B_{isjs} = A_{ijs} - γ_s * k_{is}*k_{js}/(2*m_s)  (intra-slice)
     B_{isir} = ω_{isr}                                  (inter-slice, same node)
  2. Apply Louvain local-moving + aggregation on matrix B
  3. Maximize Q_multislice
  → Community assignment for each node in each slice

Part IV: The Current Frontier

GNN-Based Community Detection

Graph Neural Network (GNN)-based community detection has developed rapidly in the 2020s.

DMoN (Tsitsulin et al., 2023): Makes Modularity differentiable, predicting community assignment matrices directly from GNN node embeddings. The loss function:

• Term 1: Modularity maximization (negated for minimization)
• Term 2: Collapse regularization. $C^T \mathbf{1}_n$ is the cluster size vector $\mathbf{s}$ (number of nodes assigned to each cluster). Minimized (value 0) when all clusters have equal size ($s_i = n/k$); penalizes concentration of all nodes into one cluster
• $C$: Soft community assignment matrix ($n \times k$) output by the GNN
• $B$: Modularity matrix ($B_{ij} = A_{ij} - k_i k_j / 2m$)

MinCutPool (Bianchi et al., 2020): Makes normalized cuts differentiable, integrating as graph pooling layers in GNNs. Detects communities hierarchically via Graph U-Net-style architectures.

The advantage of GNN-based methods: node features can be leveraged — social media profiles, paper content, protein sequences — alongside graph structure. But challenges remain:

• Interpretability: GNN intermediate representations are opaque
• Generalization: Unclear whether models transfer to structurally different graphs
• Scalability: Training costs on large graphs

Flow-Based Dynamic Community Detection

Methods focusing on temporal flow (information propagation) have also advanced. Rosvall & Bergstrom (2010) extended Infomap to dynamic networks, connecting time slices via teleportation-augmented random walks.

This is the dynamic extension of the Map Equation, unifying intra-slice random walks with inter-slice "teleports" (same-node time transitions). It implements the same inter-slice coupling concept as Mucha's Multislice Modularity within an information-theoretic framework.

Streaming Algorithms

Community detection under streaming settings — where edges arrive one at a time — is another important research direction, targeting real-time community detection in large-scale social networks.

OSLOM (Lancichinetti, Radicchi, Ramasco & Fortunato, 2011) is a method for finding statistically significant communities that also supports local community updates upon edge addition/removal, incrementally updating results without full recomputation — making it suitable for streaming scenarios.

Method Comparison and Selection Guide

Practical Algorithm Selection Guide

Extending Part 1's guide for higher-order, dynamic, and multiplex settings:

Conclusion — Toward an Integrated Perspective

Combining Parts 1 and 2, let us survey the full landscape of Community Detection.

Generation 1 (1970s–early 2000s): From graph partitioning to social network analysis. Modularity formulation, Girvan-Newman's pioneering work. The "static, single-layer, pairwise" paradigm based on edge density.

Generation 2 (late 2000s–early 2010s): Louvain/Leiden scalability, SBM statistical inference, discovery of the Resolution Limit and detectability threshold. Pursuit of "better methods" and recognition of "fundamental difficulties."

Generation 3 (late 2010s–present): The "beyond edges" paradigm expansion covered in this article:

• Higher-order structure considerations (motifs, hypergraphs, simplicial complexes)
• Temporal dynamics integration (Evolutionary Clustering, Multislice Modularity)
• Multi-relationship integration (multiplex networks, tensor approaches)
• Deep learning fusion (GNN-based methods)

The overarching insight: Community Detection is not about finding a single correct answer, but about building a toolkit for understanding network structure from multiple perspectives. Edge density, motif density, information compression efficiency, statistical significance, temporal coherence, cross-layer consistency — each corresponds to a different definition of "community" and illuminates network structure from a different angle.

This field remains actively researched, with particular attention to:

1. Hypergraph GNNs: Unsupervised community detection using Hypergraph Neural Networks (HGNN)
2. Causal communities: Defining communities based on node/edge temporal causal relationships
3. Scalable dynamic methods: Real-time processing at billion-node scale
4. Extended theoretical guarantees: Detectability thresholds for higher-order and dynamic settings

Part 1's conclusion — "perfect Community Detection is fundamentally impossible" — becomes even stronger in the advanced settings of this sequel. Yet simultaneously, the toolkit is steadily enriching, enabling us to probe ever deeper into the complexity of real-world networks.

References

• Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., & Alon, U. (2002). Network motifs: simple building blocks of complex networks. Science, 298(5594), 824–827.
• Palla, G., Derényi, I., Farkas, I., & Vicsek, T. (2005). Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435(7043), 814-818.
• Chakrabarti, D., Kumar, R., & Tomkins, A. (2006). Evolutionary clustering. KDD 2006, 554–560.
• Mucha, P. J., Richardson, T., Macon, K., Porter, M. A., & Onnela, J.-P. (2010). Community structure in time-dependent, multiscale, and multiplex networks. Science, 328(5980), 876–878.
• Rosvall, M., & Bergstrom, C. T. (2010). Mapping change in large networks. PLoS ONE, 5(1), e8694.
• Lancichinetti, A., Radicchi, F., Ramasco, J. J., & Fortunato, S. (2011). Finding statistically significant communities in networks. PLoS ONE, 6(4), e18961.
• De Domenico, M., Solé-Ribalta, A., Cozzo, E., Kivelä, M., Moreno, Y., Porter, M. A., Gómez, S., & Arenas, A. (2013). Mathematical formulation of multilayer networks. Physical Review X, 3(4), 041022.
• Yang, J., & Leskovec, J. (2013). Overlapping community detection at scale: a nonnegative matrix factorization approach. WSDM 2013, 587-596.
• Kivelä, M., Arenas, A., Barthelemy, M., Gleeson, J. P., Moreno, Y., & Porter, M. A. (2014). Multilayer networks. Journal of Complex Networks, 2(3), 203–271.
• Gauvin, L., Panisson, A., & Cattuto, C. (2014). Detecting the community structure and activity patterns of temporal networks: a non-negative tensor factorization approach. PLoS ONE, 9(1), e86028.
• Benson, A. R., Gleich, D. F., & Leskovec, J. (2016). Higher-order organization of complex networks. Science, 353(6295), 163–166.
• Interdonato, R., Tagarelli, A., Ienco, D., Sallaberry, A., & Roche, M. (2017). Local community detection in multilayer networks. Data Mining and Knowledge Discovery, 31(5), 1444–1479.
• Bianchi, F. M., Grattarola, D., & Alippi, C. (2020). Spectral clustering with graph neural networks for graph pooling. ICML 2020.
• Kumar, T., Vaidyanathan, S., Ananthapadmanabhan, H., Parthasarathy, S., & Ravindran, B. (2020). Hypergraph clustering by iteratively reweighted modularity maximization. Applied Network Science, 5, 52.
• Schaub, M. T., Benson, A. R., Horn, P., Lippner, G., & Jadbabaie, A. (2020). Random walks on simplicial complexes and the normalized Hodge 1-Laplacian. SIAM Review, 62(2), 353–391.
• Tsitsulin, A., Palowitch, J., Perozzi, B., & Müller, E. (2023). Graph clustering with graph neural networks. JMLR, 24(127), 1–21.
• Zhou, D., Huang, J., & Schölkopf, B. (2006). Learning with Hypergraphs: Clustering, Classification, and Embedding. NeurIPS 2006.
• Jutla, I. S., Jeub, L. G. S., & Mucha, P. J. (2011–). A generalized Louvain method for community detection implemented in MATLAB. http://netwiki.amath.unc.edu/GenLouvain

Further Reading

• Ahn, Y.-Y., Bagrow, J. P., & Lehmann, S. (2010). Link communities reveal multiscale complexity in networks. Nature, 466(7307), 761-764.
• Benson, A. R., Gleich, D. F., & Lim, L.-H. (2017). The spacey random walk: a stochastic process for higher-order data. SIAM Review, 59(2), 321–345.
• Rossetti, G. (2021). CDlib: Community Discovery Library. SoftwareX, 16, 100842.
• Fortunato, S. (2010). Community detection in graphs. Physics Reports, 486(3-5), 75-174.
• Fortunato, S., & Hric, D. (2016). Community detection in networks: A user guide. Physics Reports, 659, 1-44.