Stochastic Kronecker Graph on Vertex-Centric BSP

Ernest K. Ryu, Sean ChoiarXiv 2012 · arXiv

Abstract

The Poisson Stochastic Kronecker Graph (PSKG) is a novel network generation model optimized for distributed, vertex-centric systems like Apache Giraph. By transitioning from an edge-centric multinomial distribution to independent Poisson processes at each vertex, PSKG achieves "embarrassingly parallel" performance while maintaining the structural properties of the standard Stochastic Kronecker Graph (SKG) model.

Introduction

To study massive real-world networks, researchers require synthetic graph generators that mimic complex properties such as "small-world" connectivity and power-law degree distributions. The Stochastic Kronecker Graph (SKG) is a standard model for this purpose. However, SKG is inherently "edge-centric," relying on a global process to "drop" edges into a matrix. This approach is poorly suited for modern distributed computing frameworks like Vertex-Centric Bulk Synchronous Parallel (BSP), where each vertex acts as an independent unit. Forcing SKG into these systems often leads to significant communication overhead or slow serial execution. The authors set out to bridge this gap by enabling every vertex to determine its own edges independently.

Methodology: The Poissonization of SKG

The authors propose PSKG to bridge the gap between SKG's modeling power and the requirements of vertex-centric systems. The core innovation is the "Poissonization" of the edge generation process.

  1. From Multinomial to Poisson: In standard SKG, edge distribution follows a global multinomial distribution. PSKG replaces this by having each vertex $u$ independently determine its out-degree using a Poisson distribution.
  2. Local Mean Calculation: Vertices calculate their own expected edge load using only their ID and a small initiator matrix ($P$). This requires zero inter-node communication.
  3. Recursive Destination Selection: After determining the number of edges, vertices use a recursive algorithm to select destination nodes.
  4. Probabilistic Load Balancing: To prevent computational "hot spots," the authors utilize a specialized partitioning algorithm. By traversing the decision tree of the Kronecker product, the system can pre-calculate vertex ranges for workers to ensure balanced edge counts.
Decision tree for probabilistic load balancing and edge distribution.

Key Results and Evaluation

The PSKG model was evaluated against traditional SKG using synthetic graphs generated from different initiator matrices, including a small $2^{12}$ vertex configuration and a larger $4^8$ vertex configuration. The primary goal was to ensure that the Poisson approximation did not degrade the structural properties of the generated networks.

The authors compared the models across four standard metrics: Degree Distribution, Hop Plot (reachability), Scree Plot (eigenvalues), and Network Values (eigenvectors). As shown in the results, the curves for PSKG and SKG are virtually indistinguishable, confirming that PSKG perfectly mimics the modeling capabilities of SKG while offering superior scalability and predictable load balancing.

Comparison of SKG and PSKG across four standard network metrics, showing near-perfect alignment.

Conclusion

PSKG provides an "embarrassingly parallel" solution for graph generation on BSP frameworks. By eliminating communication bottlenecks and providing mathematical guarantees for load balancing, it enables the generation of massive-scale synthetic networks. While PSKG excels at generation, future work remains in developing vertex-centric methods for "fitting"—automatically determining the initiator matrix $P$ from real-world data—to complete the distributed analysis pipeline.

Summary updated

BibTeX
@misc{ryu2012stochastic,
  author = {Ernest K. Ryu and Sean Choi},
  title = {{Stochastic Kronecker Graph on Vertex-Centric BSP}},
  year = {2012},
  eprint = {1208.2239},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1208.2239},
}
Figure