Finding instabilities in the community structure of complex networks.

By David Gfeller, Jean-Cédric Chappelier, P. De Los Rios. 2005

125 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

How researchers see this paper

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

In Artificial Intelligence

In Statistical and Nonlinear Physics

Citations in the corpus

Community detection in graphs (2009, background): “As in the approach by Gfeller et al. the behaviour of the function 〈V (α)〉 does not have an absolute meaning, 71 but needs to be compared with the corresponding curve obtained for a null model.”
Modular Brain Networks (2015, background): “Another approach, known as robustness testing, entails adding a small amount of noise to the community detection process to induce change in a network's community structure (Gfeller et al. 2005, Karrer et al. 2008, Wu & Huberman 2004).”
Community Structure in Graphs (2007, background): “For standard algorithms, the problem of identifying overlapping vertices could be addressed by checking for the stability of partitions against slight variations in the structure of the graph, as described in [33].”
Stable Community Cores in Complex Networks (2012, background): “In [5], the noise added to the weight of a link between nodes i and j, initially equal to wij , is given by a distribution between −σwij and σwij , where σ is a constant parameter.”