Stability of graph communities across time scales

Area of Science:

• Network science
• Computational biology
• Data analysis

Background:

• Complex networks (biological, social, engineering) require community detection for structural insights.
• Existing community detection methods lack consensus on quality quantification and ranking.
• Dynamic processes on networks offer new perspectives for community analysis.

Purpose of the Study:

• To introduce a novel metric, partition stability, for quantifying and ranking community structures in networks.
• To establish a dynamical framework for understanding community detection across various time scales.
• To unify existing partitioning measures within a single dynamical definition.

Main Methods:

• Utilizing a dynamic Markov process on networks to define partition stability.
• Analyzing clustered autocovariance to measure community structure quality.
• Employing Markov time as an intrinsic resolution parameter to establish community hierarchies.

Main Results:

• Partition stability allows for time-dependent comparison and ranking of network partitions.
• The Markov time naturally generates a hierarchy of communities, from fine-grained to coarse-grained.
• Modularity, normalized cut size, and spectral clustering are shown to be special cases of the stability measure at different time scales.

Conclusions:

• The proposed dynamical definition of partition stability offers a unifying framework for network community detection.
• This method provides a robust way to characterize the relevance of partitions over time in diverse networks.
• The approach facilitates reduced descriptions of complex systems, such as atomic-level protein structures, across multiple time scales.