PaperlayerView exact revision on arXiv

Source-linked AI summary

Finding statistically significant communities in networks

Andrea Lancichinetti, Filippo Radicchi, Jose' Javier Ramasco, Santo Fortunato

arXiv:1012.2363v2physics.soc-phcs.IRcs.SIq-bio.QM

TL;DR

Community detection methods often lack the flexibility to handle directed, weighted, overlapping, hierarchical, dynamic, and statistically insignificant structure. The paper introduces OSLOM, which locally optimizes cluster significance against a null model and combines repeated local analysis with hierarchical processing. OSLOM is reported to perform especially well on directed graphs and strongly overlapping clusters while supporting broad network applications.

  • Problem

    Existing community-detection algorithms often cannot handle directed, overlapping, hierarchical, dynamic, or statistically insignificant structures.

  • Method

    OSLOM locally optimizes the statistical significance of clusters relative to a global configuration-model null model, with repeated analysis and hierarchical processing.

  • Results

    OSLOM performs excellently across artificial benchmark graphs, outperforming on directed graphs and strongly overlapping clusters while recognizing absent community structure or randomness.

  • Takeaways & Limitations

    OSLOM provides a multi-purpose toolbox for directed, weighted, overlapping, hierarchical, and dynamic network community analysis, including large-network workflows.

Abstract

from arXiv · show

Community structure is one of the main structural features of networks, revealing both their internal organization and the similarity of their elementary units. Despite the large variety of methods proposed to detect communities in graphs, there is a big need for multi-purpose techniques, able to handle different types of datasets and the subtleties of community structure. In this paper we present OSLOM (Order Statistics Local Optimization Method), the first method capable to detect clusters in networks accounting for edge directions, edge weights, overlapping communities, hierarchies and community dynamics. It is based on the local optimization of a fitness function expressing the statistical significance of clusters with respect to random fluctuations, which is estimated with tools of Extreme and Order Statistics. OSLOM can be used alone or as a refinement procedure of partitions/covers delivered by other techniques. We have also implemented sequential algorithms combining OSLOM with other fast techniques, so that the community structure of very large networks can be uncovered. Our method has a comparable performance as the best existing algorithms on artificial benchmark graphs. Several applications on real networks are shown as well. OSLOM is implemented in a freely available software (http://www.oslom.org), and we believe it will be a valuable tool in the analysis of networks.

I. INTRODUCTION

Community detection helps reveal functional subunits and vertex similarities, but existing methods often fail to accommodate directed, weighted, overlapping, hierarchical, dynamic, or statistically insignificant structure. OSLOM addresses these gaps by locally optimizing cluster significance against a configuration-model null model.

  • Motivation: Community detection can identify functional subunits and structural roles that are not apparent from non-topological information alone.Core and boundary positions may correspond to control, stability, or mediation roles.
  • Limitations of existing methods: Many community algorithms cannot readily handle directed graphs, although directedness is essential in citation networks, food webs, and the Web.Weighted edges pose a related challenge, though extensions are generally easier.
  • Limitations of existing methods: Existing methods often assign each vertex to one cluster, despite communities that overlap and hierarchies in which communities contain or are contained by others.Overlapping communities turn partitions into covers and increase the problem’s complexity.
  • Statistical significance: Meaningful communities must be distinguished from pseudo-communities caused by random fluctuations in graphs without preferential linking.Many algorithms still identify clusters in random graphs, even when those clusters are not meaningful.
  • OSLOM: OSLOM locally optimizes cluster statistical significance relative to a global null model and is proposed as a method meeting the listed requirements.The paper evaluates it on artificial benchmarks and applies it to real networks.
  • Statistical significance: The significance analysis uses the configuration model, which preserves vertex degrees while randomly rewiring the remaining edges.External vertices are ranked by the probability of having at least their observed number of connections to a candidate cluster; bootstrap sampling handles discrete cumulative distributions.

B. Single cluster analysis

Single-cluster analysis alternates between adding statistically significant external vertices and removing insignificant internal vertices. Because bootstrap-based scores are stochastic, the procedure is repeated and retains vertices with sufficiently high participation frequency.

  • Expansion: OSLOM first computes scores for external neighbors and adds the best-ranked vertices when their cumulative significance is below tolerance P.If the q-th candidate qualifies, all q highest-ranked candidates are added.
  • Cleaning: The procedure then removes the worst internal vertex whenever it fails the same significance test, continuing until all retained internal vertices are significant.The resulting cluster has compatible external vertices and significant internal vertices.
  • Cleaning: The complete two-step procedure is necessary because good external vertices and bad internal vertices can coexist in the starting cluster.Cleaning guarantees significance relative to the current null model.
  • Repetition and selection: Because score computation is stochastic, OSLOM repeats the analysis and defines each vertex’s participation frequency across non-empty outputs.A cluster is considered significant when the single-cluster analysis yields a non-empty subgraph in more than 50% of iterations, and retained vertices satisfy fi > 0.5.
  • Computational considerations: The worst-case complexity scales with cluster size, the number of cluster neighbors, and the loops needed for reliable participation frequencies.Reducing iterations speeds computation but can affect statistical reliability.

C. Network analysis

Network analysis grows significant clusters from randomly selected starting vertices, repeatedly applying single-cluster cleaning to explore different regions. It then resolves whether candidate clusters should remain separate, overlap, or merge.

  • Network exploration: The full-network procedure starts from a randomly selected vertex and initializes the candidate group as C = {i}.This provides a starting point when no prior community information is available.
  • Network exploration: Each iteration adds q significant neighboring vertices before applying the single-cluster analysis.The number q is sampled from a power law with exponent −3.
  • Overlapping output: Repeating the procedure from several starting vertices explores different network regions and yields a final set of clusters that may overlap.Repeated covers are analyzed to select clusters for the final output.
  • Cluster unions: OSLOM compares separate clusters with their union by testing whether the component clusters remain significant within the union’s induced subgraph.For two clusters, the submodules are preferred when their cleaned union exceeds P2 · |C3|, with P2 = 0.7.
  • Cluster unions: For multiple clusters, OSLOM recursively searches for significant submodules and uses the same rule to identify minimal clusters and decide among their unions.Minimal clusters have no significant internal cluster structure under the rule.

D. OSLOM

OSLOM assembles local significance testing, cluster cleaning, internal-structure checks, and hierarchical analysis into a multi-stage algorithm. It can refine existing partitions or covers and recursively constructs super-networks to recover higher-level structure.

  • Algorithm: The assembled procedure is named OSLOM, the Order Statistics Local Optimization Method.Its components combine single-cluster cleaning with full-network and hierarchical analysis.
  • Algorithm: OSLOM consists of three phases: finding significant clusters, analyzing internal structure or unions, and detecting hierarchical structure.The first phase continues until convergence.
  • Initialization: The algorithm can start from an existing partition or cover, using the first phase to clean clusters supplied by another fast method or prior information.This supports OSLOM as a refinement procedure rather than only a standalone detector.
  • Hierarchy: For hierarchy detection, OSLOM converts each significant cluster into a supervertex and weights superedges by the number of edges between representative clusters.The resulting super-network becomes the input for the next hierarchical level.
  • Hierarchy: Edges incident on overlapping vertices are distributed across cluster pairs using 1/(νi · νj), while original edge weights are rescaled as w/(νi · νj).The supernetwork construction is repeated until no further clusters are produced.

1. Significant clusters

OSLOM evaluates clusters by statistical significance in a configuration-model null model, naturally allowing homeless vertices and overlapping clusters. It also analyzes hierarchical structure, including branches with different depths.

  • Significant clusters: OSLOM’s score measures cluster significance relative to random graphs with the same degree sequence.The tolerance P determines whether detected clusters are accepted as unlikely under the null model.
  • Significant clusters: Homeless vertices are left outside clusters when they are not significantly linked to any group.This makes random noise or non-significant vertices a natural output rather than forcing every vertex into a cluster.
  • Significant clusters: Independent cluster cleaning allows some vertices to belong to multiple clusters, producing overlapping communities.OSLOM’s treatment of overlaps is evaluated on dedicated benchmarks.
  • Hierarchy: OSLOM analyzes hierarchical cluster structure through a dedicated procedure that performs well on hierarchical benchmarks.The method can identify multiple organizational levels rather than only a flat partition.
  • Hierarchy: Different hierarchical branches can have different depths because some vertices remain homeless while others form proper clusters.This coexistence yields branches with unequal numbers of hierarchical levels.

5. Weighted networks

OSLOM extends its significance-based framework to weighted and directed networks through null-model variables for edge weights and directions. The paper also studies dynamic snapshots and empirical computational scaling.

  • Weighted networks: Weighted-network modeling assumes separable topology and weight contributions in the configuration model.Vertex strength is the sum of incident edge weights, and expected edge weights are based on endpoint average weights.
  • Weighted networks: The weighted null model uses a harmonic mean of endpoint average weights to define expected edge-weight contributions.The harmonic average is chosen because it is more sensitive to small average weights.
  • Weighted networks: OSLOM combines weighted and topological probability variables into a joint variable whose order-statistics distribution supports cluster scoring.The two probabilities are defined over different element sets, making their combination non-trivial.
  • Directed networks: Directed graphs are handled with separate incoming and outgoing variables, while graphs with directions and weights use four variables per vertex.The final score is the product of the corresponding variables.
  • Dynamic networks: For dynamic networks, OSLOM combines information across time slices rather than analyzing each snapshot independently.The approach is motivated by preserving information from previous network states.
  • Complexity: The measured execution time scales approximately as a power law of network size, with a fitted exponent of 1.1(1) for large graphs.This behavior appears largely independent of community mixing and implementation choice, apart from a multiplicative factor.

A. Artificial networks

Artificial-network tests compare OSLOM with established methods on LFR benchmarks covering non-overlapping, large, and overlapping communities. OSLOM matches Infomap on standard tests and performs strongly when overlaps are present.

  • Benchmark design: The evaluation uses LFR graphs with planted communities and heterogeneous vertex-degree and community-size distributions.Tests include undirected, unweighted networks with varying mixing levels and community sizes.
  • Benchmark design: NMI measures similarity between planted and recovered partitions or covers, enabling comparisons for both hard and overlapping community assignments.Infomap is used for non-overlapping comparisons, while COPRA and MOSES are used for overlapping communities.
  • Large graphs: Both OSLOM and Infomap remain effective on large LFR graphs, although OSLOM can lose accuracy by identifying homeless vertices when communities are well defined.These vertices are not significantly linked to any cluster according to OSLOM’s criterion.
  • Overlapping communities: OSLOM significantly outperforms COPRA in both overlapping-community tests and MOSES when only some vertices overlap.OSLOM and MOSES are quite close when all vertices are overlapping.

3. Hierarchical LFR benchmark

The artificial-network evaluation tests hierarchical recovery, absence of community structure, and robustness to added noise. OSLOM recovers hierarchical levels under moderate mixing, remains conservative on random graphs, and separates substantial noise from planted communities.

  • Hierarchical benchmark: The hierarchical LFR benchmark generates micro- and macro-communities by applying the wiring procedure twice with separate mixing parameters.The test compares recovered partitions with planted Fine and Coarse levels.
  • Hierarchical benchmark: When µ2 is small, OSLOM and the hierarchical Infomap extension recover both levels; for µ1 + µ2 ≳ 0.7, only the Coarse level remains detectable.OSLOM performs better than Infomap when µ1 is not too small.
  • Random graphs: On random Erdős–Rényi and scale-free graphs, OSLOM keeps the fraction of vertices in non-trivial clusters very low across average degrees.Infomap finds many non-trivial clusters at low average degree but improves as average degree increases.
  • Noise robustness: In noisy-graph tests, OSLOM correctly separates planted clusters from up to about 300 preferentially attached noisy vertices.The noisy vertices represent almost a third of the whole network, whereas Infomap and COPRA do not recognize them as noise.
  • Real networks: The real-network application section covers social, information, biological, and infrastructural systems and reports community-structure statistics.The supplied passages identify the word-association network as one application.

1. The word association network

OSLOM is applied to real networks spanning overlapping word associations, geographically structured commuter flows, large social and Web graphs, and dynamic air-traffic data. These applications illustrate hierarchical cluster-size patterns, scalability through refinement, and similarity measures for evolving networks.

  • The word association network: Word associations form overlapping communities because words can have multiple meanings and belong to different groups.Examples include overlapping words such as intelligence, shared by the mind and intelligent groups.
  • Real-network applications: The UK commuter network contains 10 608 ward vertices, with directed weighted edges representing daily flows between areas of residence and work or study.Edge weights count commuters per day, using 2001 UK census data.
  • Large networks: OSLOM analyzes large LiveJournal and .uk Web networks through a two-step procedure that initializes clusters with Louvain and then refines them.The refinement reduces computational complexity, although direct OSLOM application could be more accurate.
  • Large networks: For the Web graph, nearly 20 million vertices and 300 million edges were analyzed in about 40 hours, while LiveJournal distributions were comparable across methods.LiveJournal’s first two OSLOM hierarchical levels were also similar, whereas the Web levels were more dissimilar and followed power-law decay up to a cutoff near 2000 vertices.
  • Dynamic networks: Dynamic US airport analysis compares community-cover similarity with network-matrix similarity across quarterly snapshots and reveals yearly periodicity.Both measures peak in winter, when the networks are typically more stable.

IV. DISCUSSION

The discussion presents OSLOM as a statistically significance-based, multi-purpose community-detection method that handles diverse graph features and scales through refinement. It also identifies computational costs, stochastic-iteration requirements, and reduced accuracy for fuzzy benchmark communities.

  • Capabilities: OSLOM detects statistically significant clusters while accounting for direction, weights, overlaps, hierarchy, and network dynamics.The method is presented as a general toolbox for varied graph datasets and applications.
  • Evaluation: Benchmark tests report excellent results, with OSLOM superior on directed graphs and strongly overlapping clusters and effective at recognizing absent community structure or randomness.These claims concern comparisons with leading algorithms on varied artificial benchmark graphs.
  • Limitations: On fuzzy benchmark graphs, OSLOM can return slightly less accurate results because some vertices have no topological basis for their planted community assignment.Such vertices may have as many or more neighbors in other communities due to fluctuations.
  • Methodological considerations: OSLOM’s global configuration-model null model can create resolution-limit problems, so the method recursively searches within detected clusters.Treating each cluster as a separate network progressively limits the search horizon.
  • Computational considerations: More iterations improve accuracy but increase complexity, while independent runs can be distributed across processors.This stochastic-optimization issue is shared with other community-detection techniques.
  • Computational considerations: Exhaustive searches dominate runtime, so OSLOM can refine fast initial partitions to make million-vertex systems tractable.Combining OSLOM with Louvain enabled analysis of systems with millions of vertices.

Appendix A: Numerical estimation of the internal connection probability

The appendix describes numerical approximations for OSLOM’s significance calculations and weighted-network extension. It combines topology- and weight-based scores under null-model assumptions to rank candidate vertices efficiently.

  • Internal connection probability: OSLOM repeatedly evaluates a cluster-significance probability under the configuration null model to clean clusters and assess hierarchical levels.The appendix focuses on practical estimation of this probability.
  • Internal connection probability: A hypergeometric approximation replaces direct normalization when its self-loop condition k_i^2/2M < 1 holds; otherwise the normalization is measured directly.The approximation is close to the original distribution except when self-loops are likely.
  • Weighted extension: For weighted graphs, each edge weight is normalized by the average weight of the edges considered, and the normalized weights are summed.The resulting sum follows an Erlang distribution under the stated null-model construction.
  • Weighted extension: Topology and weight scores are combined by multiplying them and transforming the product into a final score used to rank vertices.The transformation r_tw = x(1 − log x) assumes two uniform, independent variables.

Appendix C: Further tests on benchmark graphs

On Girvan–Newman graphs, OSLOM’s accuracy declines more slowly than Infomap’s as external connectivity increases, despite homeless vertices slightly reducing its low-mixing performance.

  • Girvan–Newman benchmark: The benchmark contains 128-vertex graphs divided into four equal-sized groups, with each vertex having expected degree 16.The external-neighbor parameter satisfies kin+kout = 16.
  • Girvan–Newman benchmark: Infomap is more accurate at low kout, but its performance drops rapidly for kout ≳6 while OSLOM declines more slowly.Accuracy is measured by Normalized Mutual Information against the planted partition.
  • Girvan–Newman benchmark: OSLOM is slightly worse than Infomap because it finds several homeless vertices.

2. Weighted LFR benchmark

Across weighted and directed LFR benchmarks, OSLOM generally handles difficult mixing and community-size conditions well, although performance worsens in some high-mixing or larger-network settings.

  • Weighted LFR benchmark: The weighted LFR tests vary µw while fixing µt, using N = 5000 and N = 50000 graphs with specified community-size ranges.The benchmarks are undirected and non-overlapping, with parameters documented in Figures 18 and 19.
  • Weighted LFR benchmark: When µt = 0.5 or µt = 0.6 and N = 5000, OSLOM detects the correct clusters for every µw, while Infomap fails for µw ≳0.6.For N = 50000, OSLOM maintains excellent performance across the whole µw range under the same µt values.
  • Weighted LFR benchmark: OSLOM recognizes weighted clusters from topology alone when µt is not too large, because its topological score suppresses the combined vertex score.The weighted score rtw is the product of the topological score r′t and weight score rw.
  • Weighted LFR benchmark: For µt = 0.7, both algorithms worsen but OSLOM remains superior; for µt = 0.8, Infomap is more accurate when N = 5000.Both methods perform poorly at µt = 0.8 when N = 50000.
  • Directed LFR benchmark: OSLOM outperforms Infomap on directed LFR graphs, especially when communities span a broader range of sizes.Both algorithms slightly worsen on larger networks.

Appendix D: Real-world systems

Applications to social, organizational, and metabolic networks show that OSLOM identifies overlapping, homeless, and hierarchical structures, while also revealing noisy or weakly organized regions.

  • Zachary karate club: OSLOM finds two karate-club communities, with vertex 3 overlapping both and vertex 12 homeless because of its loose relationship with the group.The detected communities otherwise coincide with Zachary’s observed split, except for the treatment of vertices 3 and 12.
  • Bottlenose dolphins: OSLOM finds two dolphin communities with five overlapping vertices and two homeless vertices that are very loosely connected to the rest of the network.
  • American college football: The college-football network yields three hierarchical levels, including 11 lowest-level clusters and a higher-level East–West geographic separation.At the second level, OSLOM finds two large communities plus four homeless teams.
  • C. elegans metabolic network: In the C. elegans metabolic network, OSLOM finds 25 lower-level clusters and 3 higher-level clusters, with more than 20% homeless vertices at the lower level.The network is described as rather noisy.
Loading 1012.2363v2…