SGP: Preservation of Community Structure in Big Social Network Sampling

TL;DR

Social networks are expanding at an astronomical rate, making direct analysis of million-node graphs computationally prohibitive. SGP (Sampling based on Graph Partition) addresses this by partitioning the original network into sub-communities before sampling. Unlike traditional random methods, SGP ensures the resulting sub-graph mimics both the global skeleton (topology) and the local clusters (community structure) of the original data.

Problem & Motivation

Why is sampling social networks so hard? Traditional methods like Random Node (RN) or Random Walk (RW) suffer from "localized bias" or "sparsity gaps."

• RN often breaks the connectivity of the graph, leaving isolated nodes.
• RW can get stuck in dense clusters, failing to capture the "global picture."

The authors argue that a "good" sample must maintain Topological Similarity and Community Similarity. Most prior works treat the graph as a homogeneous entity; SGP treats it as a collection of interconnected modules.

Methodology: The Core of SGP

The SGP algorithm operates on the intuition that edges within a community have more common neighbors than edges connecting different communities.

1. Edge Weighting and Partitioning

The first step is identifying which edges are "bridges" between communities. The authors define an Edge Weight ($E{W}_e$) that counts cycles of length 3 and 4.

• High $E{W}_e$: The edge is deep inside a community.
• Low $E{W}_e$: The edge is likely a bridge between two distinct groups.

By filtering edges with small $E{W}_e$, the graph naturally breaks into $q$ disjoint sub-graphs.

2. Stratified Sampling via Diameter

Once partitioned, SGP doesn't just pick nodes randomly. It finds the diameter of each sub-graph.

• It picks a starting node $v_s$ at one end of the diameter.
• Nodes are grouped into "strata" based on their distance from $v_s$.
• Sampling is performed proportionally within these distance-based strata.

Figure: The stratified model ensures that the sample spreads across the entire span (diameter) of the sub-graph.

Experiments & Results

The authors compared SGP against 6 SOTA methods, including Forest Fire (FF) and Random PageRank Node (RPN), using Kolmogrov-Smirnov (K-S) tests to measure distributional similarity.

Performance on Large Datasets

The results indicate that as the network size increases (e.g., astro-ph and cond-mat), SGP’s advantages become more pronounced.

Figure: Scatter plots demonstrating SGP's superior ability to follow the original distribution compared to random methods.

Critical Analysis & Conclusion

The "Power Grid" Exception

Interestingly, SGP struggled with the power dataset (Western States Power Grid). The authors noted that this network has a massive diameter (46) and the nodes are not distributed radially around a centroid. This suggests that SGP is optimized for "Social" topologies (small-world, dense clusters) rather than "Infrastructure" topologies (long strings, grid-like).

Takeaway

SGP proves that Graph Partitioning is not just for community detection; it's a powerful tool for data reduction. By sampling within partitions, we protect the "social DNA" of the network, ensuring that the small sub-graph we analyze in our labs remains a faithful mirror of the massive network in the real world.

Future Work: Adapting SGP for high-diameter, non-radial networks like power grids or transport systems remains an open challenge.