Finding instabilities in the community structure of complex networks

29 November 2005

journal article
research article
Published by American Physical Society (APS) in Physical Review E

Vol. 72 (5) , 056135
https://doi.org/10.1103/physreve.72.056135

Abstract

The problem of finding clusters in complex networks has been studied by mathematicians, computer scientists, and, more recently, by physicists. Many of the existing algorithms partition a network into clear clusters without overlap. Here we introduce a method to identify the nodes lying “between clusters,” allowing for a general measure of the stability of the clusters. This is done by adding noise over the edge weights. Our method can in principle be used with almost any clustering algorithm able to deal with weighted networks. We present several applications on real-world networks using two different clustering algorithms.

Keywords

All Related Versions

Version 1, 2005-03-24, ArXiv

This publication has 25 references indexed in Scilit:

Communities Detection in Large Networks
Published by Springer Nature ,2004
Why social networks are different from other types of networks
Physical Review E, 2003
Global protein function prediction from protein-protein interaction networks
Nature Biotechnology, 2003
The Structure and Function of Complex Networks
SIAM Review, 2003
Community structure in social and biological networks
Proceedings of the National Academy of Sciences, 2002
An efficient algorithm for large-scale detection of protein families
Nucleic Acids Research, 2002
Statistical mechanics of complex networks
Reviews of Modern Physics, 2002
Emergence of Scaling in Random Networks
Science, 1999
On power-law relationships of the Internet topology
ACM SIGCOMM Computer Communication Review, 1999
Collective dynamics of ‘small-world’ networks
Nature, 1998