Robustness of community structure in networks.

By Brian Karrer, Elizaveta Levina, Mark Newman. 2007

336 citations recorded by the source corpus.

The discovery of community structure is a common challenge in the analysis of network data. Many methods have been proposed for finding community structure, but few have been proposed for determining whether the structure found is statistically significant or whether, conversely, it could have arisen purely as a result of chance. In this paper we show that the significance of community structure can be effectively quantified by measuring its robustness to small perturbations in network structure. We propose a suitable method for perturbing networks and a measure of the resulting change in community structure and use them to assess the significance of community structure in a variety of networks, both real and computer generated.

Subfields: Computer Networks and Communications, 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 Computer Networks and Communications

In Statistical and Nonlinear Physics

Citations in the corpus

Prioritizing network communities (2018, methodology): “Random perturbations of the network are based on rewiring of α fraction of the edges in a degree preserving manner 35 (Supplementary Note 2).”
Community detection in graphs (2009, methodology): “For a given value of α, many realizations of the perturbed graph are generated, their cluster structures are identified with some method (Karrer et al. used modularity optimization) and compared with the partition obtained from the original unperturbed graph.”
Community detection in networks: A user guide (2016, background): “One could divide V (X ,Y) by log n (Karrer et al., 2008), to force the score to be in the range [0, 1], but the actual span of values of the measure depends on the number of clusters of the partitions.”
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).”
Empirical comparison of algorithms for network community detection (2010, background): “Detecting clusters or communities in real-world graphs such as large social networks, web graphs, and biological networks is a problem of considerable practical interest that has received a great deal of attention [16, 17, 13, 8, 19].”
Functional Brain Networks Develop from a “Local to Distributed” Organization (2009, methodology): “VOI is a measure of how much information is not shared between two sets of community assignments and allows for the quantification of network robustness (see [95] and [96]).”
Comparing Community Structure to Characteristics in Online Collegiate Social Networks (2008, methodology): “[20, 26], methods to compare graph partitions can be classified roughly into three groups: (1) pair counting, (2) cluster matching, and (3) information-theoretic techniques.”
Stable Community Cores in Complex Networks (2012, methodology): “For example in [9] the method involves removing a fraction of links”
Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters (2008, background): “In part as a response to this, some recent work has had a more statistical flavor [86, 140, 144, 94, 133].”
Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks (2008, background): “cance of a particular partition based on its robustness in three different ways [73], [74], [75], [76], [77], [78]: (i) robust (persistent) across time; (ii) robust to small perturbations to the graph; and (iii) robust to the optimization algorithm and the starting point of the optimization.”
Statistical properties of community structure in large social and information networks (2008, background): “In part as a response to this, some recent work has had a more statistical flavor [85, 137, 141, 93, 130].”
On the permanence of vertices in network communities (2014, background): “However, it has been observed [5, 13], that Jazz has a much stronger community structure than the power grid.”
Clustering and Community Detection in Directed Networks: A Survey (2013, background): “In the related literature different perturbation approaches have been proposed for undirected networks [119, 120, 121], but their applicability to directed ones is not straightforward.”
Mapping Change in Large Networks (2008, background): “resampling of articles, which makes no assumption about the underlying distribution (see, for example, refs.”