Significant communities in large sparse networks

Abstract

Researchers use community-detection algorithms to reveal large-scale organization in biological and social networks, but community detection is useful only if the communities are significant and not a result of noisy data. To assess the statistical significance of the network communities, or the robustness of the detected structure, one approach is to perturb the network structure by removing links and measure how much the communities change. However, perturbing sparse networks is challenging because they are inherently sensitive; they shatter easily if links are removed. Here we propose a simple method to perturb sparse networks and assess the significance of their communities. We generate resampled networks by adding extra links based on local information, then we aggregate the information from multiple resampled networks to find a coarse-grained description of significant clusters. In addition to testing our method on benchmark networks, we use our method on the sparse network of the European Court of Justice (ECJ) case law, to detect significant and insignificant areas of law. We use our significance analysis to draw a map of the ECJ case law network that reveals the relations between the areas of law.

7 pages, 7 figures

References in corpus (14)

• Fast unfolding of communities in large networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Maps of random walks on complex networks reveal community structure
• Comparing community structure identification
• Hierarchical structure and the prediction of missing links in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Finding statistically significant communities in networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• An information-theoretic framework for resolving community structure in complex networks
• Robustness of community structure in networks
• Community Detection as an Inference Problem
• Large-scale structure of time evolving citation networks
• (Un)detectable cluster structure in sparse networks
• Effect of size heterogeneity on community identification in complex networks

Cited by in corpus (7)

• A General Optimization Technique for High Quality Community Detection in Complex Networks
• Stacking Models for Nearly Optimal Link Prediction in Complex Networks
• Significant Scales in Community Structure
• Communities and bottlenecks: Trees and treelike networks have high modularity
• Link-Prediction Enhanced Consensus Clustering for Complex Networks
• Resampling effects on significance analysis of network clustering and ranking
• Time-dependent community structure in legislation cosponsorship networks in the Congress of the Republic of Peru