You can also access our individual websites (via the Members page) for further information about our research and lists of our publications.
@article{Delvenne:2010:10.1073/pnas.0903215107,
author = {Delvenne, J-C and Yaliraki, SN and Barahona, M},
doi = {10.1073/pnas.0903215107},
journal = {PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA},
pages = {(12755--12760)--(12755--12760)},
title = {Stability of graph communities across time scales},
url = {http://dx.doi.org/10.1073/pnas.0903215107},
volume = {107},
year = {2010}
}
TY - JOUR
AB - 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.
AU - Delvenne,J-C
AU - Yaliraki,SN
AU - Barahona,M
DO - 10.1073/pnas.0903215107
EP - 12760
PY - 2010///
SN - 0027-8424
SP - 12755
TI - Stability of graph communities across time scales
T2 - PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA
UR - http://dx.doi.org/10.1073/pnas.0903215107
UR - http://hdl.handle.net/10044/1/10255
VL - 107
ER -