Source-linked AI summary
Stability of graph communities across time scales
J. -C. Delvenne, S. N. Yaliraki, M. Barahona
TL;DR
Community detection lacks consensus measures for ranking graph partitions. The paper defines stability from clustered Markov-process autocovariance, showing that Markov time ranks partitions across scales and connects standard methods within a finer-to-coarser hierarchy.
Problem
Community detection has many methods but lacks consensus on how to quantify and rank the quality of graph partitions.
Method
The paper defines partition stability using clustered autocovariance of a Markov process on the graph and evaluates it across Markov time scales.
Results
Markov time provides an intrinsic resolution parameter, with modularity and normalized cut linked to t = 1 and Fiedler spectral clustering linked to t = ∞.
Takeaways & Limitations
The resulting time hierarchy identifies partitions that are relevant and persistent over distinct time windows, from finer to coarser clusterings.
Abstract
from arXiv · showhide
The complexity of biological, social and engineering networks makes it desirable to find natural partitions into communities that can act as simplified descriptions and provide insight into the structure and function of the overall system. Although community detection methods abound, there is a lack of consensus on how to quantify and rank the quality of partitions. We show here that the quality of a partition can be measured in terms of its stability, defined in terms of the clustered autocovariance of a Markov process taking place on the graph. Because the stability has an intrinsic dependence on time scales of the graph, it allows us to compare and rank partitions at each time and also to establish the time spans over which partitions are optimal. Hence the Markov time acts effectively as an intrinsic resolution parameter that establishes a hierarchy of increasingly coarser clusterings. Within our framework we can then provide a unifying view of several standard partitioning measures: modularity and normalized cut size can be interpreted as one-step time measures, whereas Fiedler's spectral clustering emerges at long times. We apply our method to characterize the relevance and persistence of partitions over time for constructive and real networks, including hierarchical graphs and social networks. We also obtain reduced descriptions for atomic level protein structures over different time scales.
I. INTRODUCTION
The paper addresses the lack of consensus for evaluating graph partitions by defining stability through a Markov process and its dependence on graph time scales. This framework ranks partitions across times and unifies several established clustering measures.
- Community detection offers many partitioning methods, but lacks a broadly accepted theory or consensus for quantifying community quality.
- The proposed measure links partition quality to a stochastic process on the clustered graph, using Markov dynamics to give communities a dynamical interpretation.
- Markov time acts as an intrinsic resolution parameter: short times favor finer coherent clusters, whereas long times favor fewer persistent clusters.
- The framework evaluates and ranks partitions at each time, identifying the time spans over which particular clusterings remain optimal.
- Modularity and normalized cut correspond to one-step Markov times, while Fiedler spectral clustering emerges in the long-time limit.
A. Autocovariance and stability of a graph partition
Stability evaluates a graph partition by tracking how a Markov process preserves community identity relative to stationarity. Its interval-based definition favors partitions that remain coherent throughout a time range, enabling a time-dependent hierarchy of optimal clusterings.
- The graph is modeled as an undirected, connected, nonbipartite network, with adjacency and degree matrices describing its topology.
- A random walk assigns equal transition probability 1/d_i to each outgoing edge and has a stationary distribution proportional to vertex degree.
- A hard partition is represented by an indicator matrix H, while each community receives a label used to observe the Markov process through cluster membership.
- The clustered autocovariance matrix records t-step transfer dependence between communities relative to two independent walkers at stationarity.
- Stability is high when trajectories remain within their starting communities, and low when apparent persistence results from leaving and later returning.
- For each Markov time, maximizing stability produces a hierarchy from finer to coarser partitions, with long-lasting optima treated as especially relevant representations.
B. Relationship of the stability with modularity, cut, normalized cut and spectral partitioning
Stability connects community quality to Markov-process time scales, recovering established criteria at specific limits and ranking partitions across intermediate times. The optimal structure generally progresses from fine partitions toward coarser, eventually spectral or trivial clusterings.
- At t = 0, stability is maximized by the finest partition, with each vertex in its own cluster.
- At t = 1, maximizing stability is equivalent to optimizing modularity.Modularity equals the trace of the one-step autocovariance matrix.
- Modularity balances cut size against community-size imbalance because minimizing Cut favors few clusters, while minimizing ∥πH∥2 favors many equal-sized clusters.
- Normalized Cut is also a one-step Markov measure, expressible as NCut = ρ(0) − ρ(1) for two communities.
- At long times, spectral clustering identifies the most stable partitions, typically yielding a two-way Fiedler partition or the trivial one-way partition.
- Across times, optimal partitions generally become coarser, although incomparable clusterings can be optimal at different times.
III. APPLICATIONS AND EXAMPLES
The paper evaluates stability across social, hierarchical scale-free, and protein structural networks to demonstrate its applicability across network types.
- Applications span social interactions, hierarchical scale-free graphs, and protein structural networks.
A. Example 1 – Time hierarchy of partitions and comparison of clustering algorithms
The scientific-collaboration example uses stability to rank algorithmically generated partitions over time and represent the resulting hierarchy. The approach compares multiple clustering algorithms while acknowledging that global stability optimization is computationally difficult.
- Time hierarchy of partitions: Stability for a candidate clustering is computable in O(cEt), or estimable with K random walks of length t in O(Kt) with accuracy O(c/K).
- Time hierarchy of partitions: Because stability optimization is likely intractable for arbitrary graphs, heuristic aggregative and divisive strategies generate practical partition sequences.
- Time hierarchy of partitions: The KVV divisive strategy ranks its generated partitions by stability to estimate the stability curve and produces a non-binary dendrogram with fewer branching points.
- Comparison of clustering algorithms: Figure 2 compares stability curves from divisive Shi-Malik, KVV, Newman, and Newman-Girvan algorithms.
B. Example 2 – Beyond the resolution limit of modularity: the small time limit of the continuous
The continuous-time extension of stability examines partitions at times below one, enabling structures finer than modularity’s resolution. In a hierarchical scale-free graph, natural partitions remain stable over long windows while modularity’s partition is transient.
- Modularity cannot produce partitions smaller than a certain relative size, creating a resolution limit that can yield overly coarse communities.
- Continuous-time stability uses exp[(M − I)t] to analyze times between zero and one and recover finer structures than modularity.
- The small-time linear interpolation recovers the totally unclustered graph at t = 0 and modularity r(1) at t = 1.
- In the 125-vertex hierarchical scale-free graph, the natural 25- and 5-cluster partitions have long stability windows, whereas modularity at t = 1 is transient.
C. Example 3: Structural graphs, model reduction and time scales
The framework is applied to atomic-level protein structural graphs to identify persistent communities and support reduced descriptions of biomolecular dynamics. For Adenylate Kinase, 4- and 18-community partitions balance structural coherence and model simplicity better than the modularity partition.
- Structural graphs and model reduction: Protein constraint graphs seek lower-dimensional mechanical descriptions consisting of relatively rigid parts connected by flexible elements.
- Adenylate Kinase: In Adenylate Kinase’s 2085-vertex graph, the 31-community modularity partition splits rigid β-sheets and α-helices, while 4- and 18-community partitions persist longer.
- Adenylate Kinase: Partition validity is evaluated by comparing intra-community Cα-carbon distance changes between open and closed conformations.
- Adenylate Kinase: Plateaux in the distance-variation measure follow the 4- and 18-community structures, indicating that added communities are not significantly rigid.
IV. DISCUSSION AND FUTURE WORK
The discussion presents stability as a time-dependent quality measure that ranks partitions and organizes them into a hierarchy. It also unifies established methods by linking them to different Markov-time regimes, while identifying reduced modeling as future work.
- Stability and hierarchy: Stability is defined through the autocovariance of a Markov process and ranks graph partitions according to their relevance at each Markov time.
- Stability and hierarchy: Maximum-stability partitions form a hierarchy from finer to coarser clusterings as Markov time grows, rather than selecting one unique partition.
- Unifying partition methods: Modularity, cut, and normalized cut correspond to stability at t = 1, whereas normalized-Fiedler spectral clustering is linked to t = ∞.
- Unifying partition methods: Continuous stability extends analysis beyond modularity’s resolution limit and can produce finer partitions than modularity.
- Applications and future work: For dynamically originated networks, persistent communities suggest reduced representations, while systematic tests of reduced models remain future research.