Finding instabilities in the community structure of complex networks

Abstract

The problem of finding clusters in complex networks has been extensively studied by mathematicians, computer scientists and, more recently, by physicists. Many of the existing algorithms partition a network into clear clusters, without overlap. We here introduce a method to identify the nodes lying ``between clusters'' and that allows for a general measure of the stability of the clusters. This is done by adding noise over the weights of the edges of the network. Our method can in principle be applied with any clustering algorithm, provided that it works on weighted networks. We present several applications on real-world networks using the Markov Clustering Algorithm (MCL).

4 pages, 5 figures

References in corpus (15)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Finding community structure in very large networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Cooperative Game Theory Approaches for Network Partitioning
• Functional cartography of complex metabolic networks
• Specificity and stability in topology of protein networks
• Who is the best connected scientist? A study of scientific coauthorship networks
• Defining and identifying communities in networks
• Why social networks are different from other types of networks
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Detecting fuzzy community structures in complex networks with a Potts model
• Modularity and Extreme Edges of the Internet

Cited by in corpus (44)

• Community detection in graphs
• Near linear time algorithm to detect community structures in large-scale networks
• Statistical Mechanics of Community Detection
• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• Mapping change in large networks
• Clustering and Community Detection in Directed Networks: A Survey
• Entropy measures for complex networks: Toward an information theory of complex topologies
• Narrow scope for resolution-limit-free community detection
• Robustness of community structure in networks
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Modularity-Maximizing Network Communities via Mathematical Programming
• The Shannon and the Von Neumann entropy of random networks with heterogeneous expected degree
• Gibbs entropy of networks ensembles by cavity methods
• Spectral Coarse Graining and Synchronization in Oscillator Networks
• Stress-induced rearrangements of cellular networks: consequences for protection and drug design
• Detecting Important Nodes to Community Structure Using the Spectrum of the Graph
• Multi-scale analysis of the European airspace using network community detection
• Link-Prediction Enhanced Consensus Clustering for Complex Networks
• Compression of Flow Can Reveal Overlapping-Module Organization in Networks
• Detection of node group membership in networks with group overlap
• Inversion method for content-based networks
• Measuring Significance of Community Structure in Complex Networks
• Stochastic block model and exploratory analysis in signed networks
• Significant communities in large sparse networks
• Modularity functions maximization with nonnegative relaxation facilitates community detection in networks
• A generalised significance test for individual communities in networks
• Identifying overlapping communities in social networks using multi-scale local information expansion
• Effect of size heterogeneity on community identification in complex networks
• Multiple Hybrid Phase Transition: Bootstrap Percolation on Complex Networks with Communities
• Robustness of community structure to node removal
• Non-parametric resampling of random walks for spectral network clustering
• Centrality properties of directed module members in social networks
• Resampling effects on significance analysis of network clustering and ranking
• Statistical test for detecting community structure in real-valued edge-weighted graphs
• Detecting the optimal number of communities in complex networks
• Criterions for locally dense subgraphs
• Self-falsifiable Hierarchical Detection of Overlapping Communities On Social Networks
• Identifying robust features of community structure in complex networks
• Ranking nodes according to their path-complexity
• Network modules help the identification of key transport routes, signaling pathways in cellular and other networks
• Tsallis mapping in growing complex networks with fitness
• Measuring the Robustness of Graph Properties
• Validation of community robustness
• Average Sensitivity of Spectral Clustering