Stability of graph communities across time scales

By Jean-Charles Delvenne, Sophia N. Yaliraki, Mauricio Barahona. Proceedings of the National Academy of Sciences of the United States of America, 2008

501 citations recorded by the source corpus.

The complexity of biological, social, and engineering networks makes it desirable to find natural partitions into clusters (or communities) that can provide insight into the structure of the overall system and even act as simplified functional descriptions. Although methods for community detection abound, there is a lack of consensus on how to quantify and rank the quality of partitions. We introduce here the stability of a partition, a measure of its quality as a community structure based on the clustered autocovariance of a dynamic Markov process taking place on the network. 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 communities. Our dynamical definition provides a unifying framework for 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 of partitions over time for constructive and real networks, including hierarchical graphs and social networks, and use it to obtain reduced descriptions for atomic-level protein structures over different time scales.

Subfields: Molecular Biology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/7a7532522938e4411e89ee50c3949029673910b3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

Dynamics on higher-order networks: a review (2022, methodology): “A generalization of the formulation of Markov stability [123] is further adopted in order to find the communities in the hypernetwork, by assuming a partition of the nodes into c non-overlapping communities, captured by the indicator matrix CN×c where Cij takes up the value 1 when the ith node belon”
Modular and Hierarchically Modular Organization of Brain Networks (2010, background): “Alternative and related approaches have been developed for modular decomposition, such as the concept of stability which is based on the persistence of information flows within modules over time (Delvenne et al., 2010).”
Uncovering space-independent communities in spatial networks (2010, background): “In this article, we have instead preferred the ﬁrst option, mainly for 2 reasons: - i) One of the aims of modularity is to properly account for the importance of nodes in the null model, thereby producing balanced modules in terms of this measure of importance [76].”
Controllability Metrics, Limitations and Algorithms for Complex Networks (2013, unknown): “For large networks, this partitioning scheme may be inefﬁcient, and it may be replaced by a partitioning scheme with linear complexity, such as the Lou-vain method [45], [46].”
Random walks and diffusion on networks (2016, background): “ability of a partition of a network is dened as the probability that a walker is in the same community at time 0 and time tin the equilibrium of the Poissonian node-centric CTRW [347{350]. See Refs. [350, 351] for a version of Markov stability derived from a DTRW. The master equation is dp(t) dt = p”
Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks (2008, background): “For simplicity, we start by considering the case of undirected graphs, although we will see below that the arguments extend to directed graphs too.”
Memory in network flows and its effects on spreading dynamics and community detection (2013, methodology): “e structure of the dynamics with and without memory. Since we are interested in the dynamics, we have chosen to work with the ﬂow-based map equation framework (3). Alternative ﬂow-based methods exist (4,24), but the map equation framework easily allows us to maintain the mechanics of the method and ”
Multi-scale brain networks (2016, unknown): “The multi-scale modularity maximization approach and related techniques (Delvenne et al., 2010; Schaub et al., 2012; Kheirkhahzadeh et al., 2016) can seamlessly scan all topological scales by tuning the resolution parameter, which entails no additional assumptions.”
Modular Brain Networks (2015, methodology): “In doing so, we necessarily omitted many methods that may yet prove useful in network neuroscience, including several based on random walks (Delvenne et al. 2010, Pons & Latapy 2005), belief propagation (Zhang & Moore 2014), and phase synchronization (Boccaletti et al. 2007).”
Modern temporal network theory: a colloquium (2015, background): “are also not as central as for random walks on lattices or static graphs|but they do exist [270,222,87,267]. Instead people either use walks as probes of the system’s burstiness [270,54], time scales [55, 240] or other temporal patterns [257]. Another use of random walks (alluded to above) is to use”
Communities in Networks (2009, methodology): “In addition to revealing that resolution parameters arise naturally, this perspective shows that the Potts method arises as a special case of placing a continuous time random walk with Poissondistributed steps on a network [27].”
Communication dynamics in complex brain networks (2017, background): “Under this framework, the temporal scale is defined in terms of the length of time — or the number of hops — needed before a random walker can escape a cluster of nodes 111,115 .”
Structure and dynamics of molecular networks: A novel paradigm of drug discovery: A comprehensive review (2012, background): “Protein structure networks have modules, which often encode protein domains (Xu et al., 2000; Guo et al., 2003; Delvenne et al., 2010; Delmotte et al., 2011; Szalay-Bekő et al., 2012).”
Community detection in networks: A user guide (2016, background): “For instance, Newman–Girvan’s modularity is a special case of a general quality function, called stability, expressing the persistence of a randomwalk within communities [43,178].”
Spatio-Temporal Data Mining (2017, background): “To address this problem, [Delvenne et al. 2010] proposed an approach to discover clusters that are relevant at different granularities.”