PaperlayerView exact revision on arXiv

Source-linked AI summary

Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction

Lovro Šubelj, Marko Bajec

arXiv:1103.2593v1physics.soc-phcs.SIphysics.data-an

TL;DR

Large complex networks require community-detection methods that remain scalable while improving on the accuracy of basic label propagation. The paper proposes a hierarchical diffusion and propagation algorithm combining defensive and offensive strategies, and reports competitive detection performance with almost-linear scaling on large networks.

  • Problem

    Scalable community detection for networks with millions of nodes and billions of edges remains an important research need, while a generally accurate label-propagation algorithm is still open.

  • Method

    The diffusion and propagation algorithm combines defensive core preservation and offensive border expansion through hierarchical core extraction and whisker-community identification.

  • Results

    The algorithm outperforms previous label-propagation approaches overall, is comparable to state-of-the-art methods, and shows almost linear complexity O(m^1.19) on real-world networks.

  • Takeaways & Limitations

    Defensive propagation has high recall for weakly defined communities, whereas offensive propagation achieves high precision; their combination improves results especially on larger networks.

Abstract

from arXiv · show

Label propagation has proven to be a fast method for detecting communities in large complex networks. Recent developments have also improved the accuracy of the approach, however, a general algorithm is still an open issue. We present an advanced label propagation algorithm that combines two unique strategies of community formation, namely, defensive preservation and offensive expansion of communities. Two strategies are combined in a hierarchical manner, to recursively extract the core of the network, and to identify whisker communities. The algorithm was evaluated on two classes of benchmark networks with planted partition and on almost 25 real-world networks ranging from networks with tens of nodes to networks with several tens of millions of edges. It is shown to be comparable to the current state-of-the-art community detection algorithms and superior to all previous label propagation algorithms, with comparable time complexity. In particular, analysis on real-world networks has proven that the algorithm has almost linear complexity, $\mathcal{O}(m^{1.19})$, and scales even better than basic label propagation algorithm ($m$ is the number of edges in the network).

I. INTRODUCTION

Community detection is important for interpreting large complex networks, but scalable and generally accurate algorithms remain an open challenge. This work advances label propagation by combining defensive and offensive community formation with hierarchical core extraction and whisker identification.

  • Motivation: Communities are densely connected node groups that can reveal the structure and function of large complex networks.They may correspond to functional modules in systems such as metabolic networks.
  • Motivation: The growth of real-world networks to millions of nodes and billions of edges has driven demand for scalable community-detection methods.Simple label propagation was introduced as a promising approach for finding significant communities in large networks.
  • Approach: The proposed method combines defensive preservation, which favors community-core nodes, with offensive expansion, which favors border nodes.Cores and borders are estimated using random walks that formulate diffusion over the network.
  • Approach: Diffusion and propagation combines these strategies hierarchically by extracting the network core, identifying whisker communities, and recursively processing the core.The algorithm is evaluated on planted-partition benchmarks and 23 real-world networks spanning tens of nodes to several tens of millions of edges.
  • Reported evaluation: The algorithm is reported as comparable to state-of-the-art community-detection methods and superior to previous label-propagation algorithms with comparable time complexity.The introduction characterizes its time complexity as almost linear in the number of edges.

II. LABEL PROPAGATION AND ADVANCES

Label propagation assigns nodes the most common neighboring label and groups nodes sharing labels into communities, offering near-linear speed but facing convergence, stability, and accuracy challenges.

  • Basic label propagation: Each node starts with a unique label and repeatedly adopts the most common label among its neighbors.Ties are resolved randomly.
  • Basic label propagation: Nodes sharing a label at equilibrium are classified into the same community.The procedure exploits denser within-community connectivity relative to between-community connectivity.
  • Basic label propagation: Near-linear time complexity is a principal advantage because the algorithm commonly converges in fewer than 10 iterations on moderately sized networks.
  • Performance and limitations: 95% of nodes obtained their “right” label after 5 iterations, but the method’s simplicity often leaves accuracy below the state of the art.
  • Advances and limitations: Hop attenuation prevents labels from spreading too far and eliminates formation of a single major community, while node preference strengthens propagation control.Attenuation decreases a label’s score after propagation; preference incorporates node propagation strength.
  • Convergence and stability: Synchronous updates can oscillate on bipartite networks, whereas asynchronous random-order updates can avoid this problem and may improve performance.
  • Convergence and stability: Nodes with equally strong connections to multiple communities may never stabilize, reflecting overlapping-community structure that this work does not investigate.On a network-scientist collaboration graph, up to 10% of nodes changed labels after 10000 iterations.
  • Convergence and stability: Subsequent node reshuffling increases computational time, while omitting it only slightly decreases basic LPA performance.

III. DIFFUSION AND PROPAGATION ALGORITHM

The diffusion and propagation algorithm combines defensive preservation and offensive expansion through diffusion-based node preferences, then extends their combination with hierarchical core extraction and whisker identification.

  • Strategy formation: Diffusion-based node preferences produce defensive preservation and offensive expansion strategies for community formation.Defensive preference targets community cores, while offensive preference targets border nodes.
  • Combined algorithm: BDPA combines the defensive and offensive algorithms to preserve the advantages of both approaches.It achieves superior results on networks of moderate size.
  • Combined algorithm: DPA enhances this combination with core extraction and whisker identification for application to larger networks.

A. Dynamic hop attenuation

Dynamic hop attenuation adapts the attenuation ratio to prevent premature major-community formation while relaxing restrictions when rapid large-scale occupation is absent.

  • Motivation: No simple universal attenuation ratio δ was evident across networks, motivating dynamic strategies.Earlier experiments around δ = 0.10 produced good results in a limited setting.
  • Dynamic strategies: Large δ values can inhibit natural community growth, so prior work decreased δ from 0.50 toward 0 during execution.Early attenuation limits rapid label spread; later relaxation permits formation of actual communities.
  • Dynamic strategies: The proposed strategies activate hop attenuation mainly when one or more communities rapidly occupy a large network portion.Otherwise, the restriction is almost completely relaxed so propagation can reach equilibrium unrestrained.
  • Implementation: The authors evaluate two strategies for detecting emergence of large communities and update δ after each iteration from an initial value of 0.
  • Evaluation choice: Both strategies prevent major-community formation, but the study uses node-based rather than community-based detection because node counts provide finer granularity.After four iterations, the number of communities is generally 20 times smaller than the number of nodes, making community-based δ estimates rough.

B. Defensive and offensive propagation

The paper develops defensive preservation and offensive expansion strategies using diffusion-based node preferences, then compares their behavior across network types. Defensive propagation emphasizes community cores, whereas offensive propagation emphasizes borders and can favor heterogeneous community-size distributions.

  • Static centrality measures do not provide a consistent node-propagation preference across different network types.Experiments compared degree, eigenvector centrality, and clustering coefficient, with no single measure applying generally.
  • Random-walk diffusion estimates community cores and borders, replacing static node preferences with preferences derived from current communities.The diffusion formulation is related to PageRank, HITS, and eigenvector centrality.
  • Defensive propagation assigns greater propagation strength to core nodes, while offensive propagation assigns greater strength to border nodes.The offensive formulation uses total degree to increase values for nodes with large inter-community degree.
  • The main novelty is adapting propagation dynamics from the current communities identified during label propagation.This distinguishes the approach from methods that use fixed node preferences.
  • The exact diffusion update is approximated by updating p_n only when node n changes labels.The authors state that exact updates would likely hinder application to larger networks and produced no significant preliminary gain.
  • On average, defensive propagation performs better on the football network, whereas offensive propagation outperforms it on the elegans metabolic network.The caption characterizes football community sizes as relatively homogeneous and elegans community sizes as presumably power-law distributed.

C. Diffusion and propagation algorithm

The diffusion and propagation algorithm combines defensive and offensive label propagation hierarchically to extract a network core and retain whisker communities. Empirical analysis reports strong performance relative to label-propagation alternatives, comparable time complexity, and almost-linear scaling.

  • C. Diffusion and propagation algorithm: Sequentially applying defensive and offensive propagation fails to achieve the desired combination because converged label propagation reaches a hard-to-escape local equilibrium.The hierarchical design addresses this limitation rather than simply chaining the two algorithms on the same network.
  • C. Diffusion and propagation algorithm: The algorithm recursively reapplies the procedure to the network core while retaining identified whiskers as communities.Recursion ends when the current network is classified into one community, after which BDPA is applied.
  • C. Diffusion and propagation algorithm: BDPA significantly outperforms basic LPA and Leung et al.’s algorithm on smaller networks, while the latter produces larger communities with higher average modularity on larger networks.The comparison is based on reported modularity behavior across network sizes.
  • C. Diffusion and propagation algorithm: Hierarchical label propagation can produce one major community or flood-fill the community network on its second iteration.The authors observe that this major community commonly coincides with the network core, with other communities corresponding to whiskers.
  • C. Diffusion and propagation algorithm: DPA first uses defensive propagation to estimate communities and cores, then offensive propagation on the community network to extract the core and identify whiskers.Whisker communities are the non-major communities identified during the second step.
  • C. Diffusion and propagation algorithm: DPA outperforms other label propagation algorithms, is comparable to state-of-the-art community detection methods, and has almost-linear edge-based complexity.The reported application scope is not limited to networks with core-periphery structure.

IV. EVALUATION AND DISCUSSION

Across planted-partition benchmarks and 23 real-world networks, DPA generally outperformed label-propagation alternatives while retaining favorable scaling. Its defensive and offensive components showed complementary precision–recall behavior, and hierarchical extraction was most useful on larger networks.

  • Propagation strategies: Defensive propagation favored recall and detected weakly defined communities, while offensive propagation favored precision and slightly outperformed basic LPA.On the largest network, DDALPA converged in 25 iterations but produced modularity 0.470.
  • Benchmark networks: DPA and BDPA outperformed the three individual propagation algorithms on planted-partition benchmarks, with larger gains on larger networks.Core extraction did not improve results on networks with thousands of nodes or fewer, but results improved significantly on larger networks.
  • Benchmark networks: DPA matched or exceeded leading community-detection methods, reaching NMI values of 0.651 and 0.541 at µ = 0.8 where competing methods remained below approximately 0.35.The comparison used benchmark networks selected to coincide with those in Lancichinetti and Fortunato’s analysis.
  • Real-world networks: DPA obtained significantly higher modularity than comparable label-propagation approaches, especially on networks with millions of nodes and edges.On football, its modularity was 0.606 versus the previously reported 0.605.
  • Real-world networks: BDPA performed better on smaller networks, whereas DPA’s hierarchical core extraction was more appropriate for larger networks.Core extraction commonly contributed little on networks with fewer than thousands of nodes or edges, but a single extraction produced significant modularity gains on larger networks.
  • Complexity and convergence: DPA scaled better than LPAM: on networks with tens of millions of edges, average iterations were 147 for DPA and 78 for LPA, while LPAM exceeded 300 on much smaller networks.The reported scaling exponent was O(m^1.19) for DPA versus O(m^1.23) for LPA, although DPA was outperformed by LPA because of a larger constant.
  • Stability: DPA and BDPA produced more stable community structures than LPA, although many distinct structures could still arise on larger networks.DPA yielded 1116 and 1330 distinct structures on the football and jazz networks, respectively.

V. CONCLUSION

The article proposes a hierarchical, local-measure label propagation algorithm combining defensive and offensive community formation strategies. It also examines how propagation strategies alter process dynamics and reveal community structures with distinctive properties.

  • The algorithm combines defensive preservation and offensive expansion strategies for community formation.
  • Its hierarchical analysis recursively extracts network cores and identifies whisker communities.
  • The method uses only local measures and does not require the number of communities beforehand.
  • The work clarifies how different propagation strategies alter label-propagation dynamics and reveal community structures with unique properties.

Appendix A: Core-periphery structure

Large social and information networks can exhibit a core-periphery structure: a central core surrounded by small, weakly connected communities. Communities connected to the rest by one edge are called whiskers.

  • Large social and information networks can divide into a central core and a remaining periphery.
  • The periphery contains many small, well-defined communities that are only weakly connected to the rest of the network.
  • Communities connected to the rest of the network by a single edge are called whiskers.

Appendix B: Algorithms

The appendix presents the proposed algorithms and implementation considerations, including disconnected-label handling, modularity-based selection, and a small-network convergence adjustment for offensive propagation.

  • The appendix gives pseudocode for the proposed algorithms and discusses implementation issues.
  • Disconnected communities that share a label after convergence can be detected using breadth-first search.
  • Each BDPA or DPA run unfolds several community sets, returning the set with the highest modularity on the original network.
  • For networks with several thousands of nodes or fewer, ODALPA updates diffusion values only after the first iteration to avoid nonconvergence.
  • The basic algorithm initializes unique node labels, zero hop attenuation, and diffusion values p_n = 1/|N| before iterating shuffled node updates.
  • DPA combines DDALPA and ODALPA, with offensive propagation replacing node preference π_i by 1 − π_i and replacing k_cn_i by k_i.
Loading 1103.2593v1…