PaperlayerView exact revision on arXiv

Source-linked AI summary

Finding Community Structure in Mega-scale Social Networks

Ken Wakita, Toshiyuki Tsurumi

arXiv:cs/0702048v1cs.CYphysics.soc-ph

TL;DR

CNM community analysis does not scale well to mega-scale social networks, motivating a search for the source of its inefficiency. The paper uses consolidation-ratio heuristics to balance merged communities and evaluates three CNM variants. The methods substantially improve execution efficiency and scalability, with one variant also improving modularity.

  • Problem

    CNM was impractical for mega-scale SNS networks: an analysis of about one million users was stopped after a week with less than 10% completed.

  • Method

    The paper introduces three consolidation-ratio heuristics that guide community-pair selection alongside modularity, and incorporates them into three CNM variants.

  • Results

    The proposed methods dramatically improve efficiency and scalability; HE’ processes G500K 7 times faster, improves modularity by 8-11%, and handles datasets beyond the original algorithm’s capacity.

  • Takeaways & Limitations

    Consolidation-ratio heuristics enable CNM community analysis on substantially larger social-network datasets than the original proposal.

  • Takeaways & Limitations

    The data-structure efficiency analysis relies on an optimistic preferential-attachment assumption about heavily linked community pairs.

Abstract

from arXiv · show

Community analysis algorithm proposed by Clauset, Newman, and Moore (CNM algorithm) finds community structure in social networks. Unfortunately, CNM algorithm does not scale well and its use is practically limited to networks whose sizes are up to 500,000 nodes. The paper identifies that this inefficiency is caused from merging communities in unbalanced manner. The paper introduces three kinds of metrics (consolidation ratio) to control the process of community analysis trying to balance the sizes of the communities being merged. Three flavors of CNM algorithms are built incorporating those metrics. The proposed techniques are tested using data sets obtained from existing social networking service that hosts 5.5 million users. All the methods exhibit dramatic improvement of execution efficiency in comparison with the original CNM algorithm and shows high scalability. The fastest method processes a network with 1 million nodes in 5 minutes and a network with 4 million nodes in 35 minutes, respectively. Another one processes a network with 500,000 nodes in 50 minutes (7 times faster than the original algorithm), finds community structures that has improved modularity, and scales to a network with 5.5 million.

1. INTRODUCTION

Community structure analysis helps reveal the organization of social networks, but CNM becomes impractical on larger networks. The paper attributes this inefficiency to unbalanced community merging and introduces consolidation-ratio heuristics to improve scalability.

  • Community structure analysis is presented as an important first step for understanding the inherent complexity of social networks.
  • CNM performs well below 500,000 users but is incapable of analyzing larger networks.
  • Unbalanced community merging substantially affects CNM’s computational efficiency.
  • Consolidation ratio measures the balancedness of community pairs and, together with modularity, selects the next communities to merge.
  • Three CNM variants using different consolidation ratios were tested on subsets of an SNS network hosting 5.5 million users.The fastest variant finds community structure in a network of 1 million nodes in 5 minutes.

2. RELATED WORK

Community analysis seeks to identify cyber-communities and support reasoning about real-community structure, nature, and dynamics. Existing approaches include seed-based methods and graph partitioning into densely connected subgraphs, alongside Web link-analysis approaches.

  • Community analysis aims to find cyber-communities that support reasoning about the structure, nature, and dynamics of real-communities.
  • One algorithmic type takes a graph and one or more seed nodes, then produces a community structure including the seed information.
  • Web link analysis models pages or sites as nodes and hyperlinks as edges, forming a huge directed graph.
  • HITS assigns authority and hub values iteratively, while Companion uses Web link analysis to find pages whose contents are closely related.
  • Another algorithmic type divides a graph into densely connected subgraphs, reflecting multiple proposed notions of what constitutes a community.

3. CNM ALGORITHM

The CNM algorithm greedily merges community pairs to maximize modularity, but its performance degrades on large social networks because unbalanced merges create inefficiently tall dendrograms. Experiments on SNS subsets reveal this bottleneck and motivate consolidation-ratio-based balancing.

  • CNM algorithm: CNM greedily starts with singleton communities and repeatedly merges the pair producing the largest modularity improvement.The algorithm updates ΔQ values for communities adjacent to each newly merged community until no pair remains.
  • CNM algorithm: CNM uses community-pair heaps and a system-wide max heap to efficiently find the pair with maximum ΔQ.These data structures support logarithmic-order insertion, removal, and maximum-pair searches.
  • Performance inefficiency: Analysis time is concentrated in the first half of merging; for G500Kmixi, 10,000 merges took less than 200 seconds after 250,000 merges.Figure 1 measures elapsed time in bars representing successive blocks of 10,000 community-pair merges.
  • Performance inefficiency: The paper defines consolidation ratio as a balancedness measure for merged communities and uses it with modularity to select merge pairs.The ratio is defined as min(|ci|/|cj|, |cj|/|ci|), with community size measured by links to other communities.
  • Performance inefficiency: Unbalanced merges cause a huge dendrogram and can degrade computational efficiency to O(n^2 log n), contrary to the expected sparse-network scaling.Observed cost was approximated by T(n) ≈ 1.5 · 10^-8x^2.13±0.104, while the original analysis estimated O(n log^2 n) for social networks.

4. ALGORITHM

The proposed CNM implementation combines a community-pair data structure with consolidation-ratio heuristics to reduce the inefficiency caused by unbalanced community growth. Three heuristics use different community-size valuations while preserving the core CNM structure.

  • 4.1 Data structure: The implementation stores each community’s neighboring pairs in a community-ID-sorted list and tracks the pair with maximum ∆Q.Community pairs reference their two communities, and merging lists eliminates duplicates while updating ∆Q values.
  • 4.1 Data structure: Merging two communities combines their pair lists, removes duplicates, and updates ∆Q values for pairs adjacent to the new community.With sorted lists, the merge takes time linear in the number of community pairs.
  • 4.1 Data structure: The max-∆Q links require rescanning a neighbor’s entire pair list when its current largest pair decreases in ∆Q.Other update cases can avoid a full scan, but the decreasing-largest-pair case lacks a convenient direct test.
  • 4.1 Data structure: O(m) merging, O(1) maximum-∆Q retrieval, and hoped-for O(m) ∆Q updates are obtained by arranging community pairs in sorted lists.Here, m denotes the number of community pairs.
  • 4.2 Heuristics based on consolidation ratio: The proposed heuristics address inefficiency from unbalanced growth by valuing candidate pairs with consolidation ratios designed to encourage balanced merges.The algorithm’s structure remains that of CNM, while pair valuation incorporates ∆Q and a consolidation ratio.
  • 4.2 Heuristics based on consolidation ratio: Three heuristics measure community size differently: HE uses degree, HE’ uses degree only during candidate comparison, and HN uses the number of members.HE’s degree measure reflects the number of neighboring community pairs and the associated merge cost.

5. EVALUATION

The evaluation compares the original CNM algorithm with three consolidation-ratio heuristics on SNS networks, finding major speed, scalability, and modularity differences among them.

  • Experimental setup: Four single-threaded Java CNM implementations were evaluated on SNS-network subsets ranging from 50K to 1000K nodes.The implementations included the original algorithm and heuristics HE, HE’, and HN.
  • Execution efficiency: 5.9 hours was required for the original algorithm to analyze its largest feasible dataset, G500K mixi.The original algorithm could not analyze larger tested networks.
  • Execution efficiency: Less than five minutes was required by NE to process G1M mixi, compared with about 36 minutes for HE and 3 hours for HE’.The heuristics remained practically usable despite their differing runtimes.
  • Consolidation ratio: NE maintained consolidation ratios better than 1:100 through most of analysis, postponing most unbalanced merges to the final stage.The original algorithm frequently produced ratios from 1:1,000 to 1:10,000, especially during the first half.
  • Consolidation ratio: NE merged 10,000 communities in less than 7 seconds for the first 760K of 870K merges and handled the heaviest computation in under 25 seconds.HE required 60–130 seconds per 10,000 merges in its heavy phase, while HE’ required 100–650 seconds.
  • Modularity: HE’ slightly outperformed the original algorithm in modularity, processing G500K mixi 7 times faster and improving modularity by 8–11%.HN was slightly faster than HE but produced modularity 21–28% lower than the original algorithm.
  • Modularity: Heuristic modularity exceeded the original during the first half of computation, while HE’ grew steadily and HE’s growth nearly stopped shortly after its early rise.The authors suggest HE may form a core structure early enough to permit approximate early termination.
  • Community structure: All four methods found a few large communities above 10,000 nodes and many small communities below 10 nodes, with almost no middle-sized communities.Community-size distributions were shown on a log-scale chart.

6. SUMMARY

The research made community analysis practical for middle-scale social networks and identifies further work on visualization and cyber-community dynamics.

  • 6. SUMMARY: 100,000-node social networks became analyzable in a few minutes on a standard laptop computer.This reduced dependence on server analyses that previously required days or hours of waiting.
  • 6. SUMMARY: Future work includes visual presentation of cluster structures and analysis of cyber-communities and their dynamics.These activities were ongoing at the time of writing.
Loading cs/0702048v1…