Introduction
Simulating realistic social and information networks requires models that capture complex structural properties like power-law degree distributions and local clustering. While the Stochastic Kronecker Product Graph Model (KPGM) offers high efficiency, it often lacks the expressiveness needed for nuanced structural details. The Multiplicative Attribute Graph Model (MAGM) addresses this by assigning latent attributes to nodes, but its traditional sampling methods are computationally prohibitive, scaling quadratically ($O(n^2)$) with the number of nodes.
The Quilting Algorithm
To overcome the scalability bottleneck of MAGM, researchers developed the Quilting Algorithm. This approach bridges the gap between the efficiency of KPGM and the expressiveness of MAGM by observing that MAGM probability matrices can be decomposed into structures similar to KPGM.
Partitioning and Permutation
The core of the algorithm involves partitioning the node set into blocks where no two nodes share the same attribute configuration. This allows the complex MAGM probability matrix $Q$ to be viewed as a collection of sub-matrices.
Once partitioned, each "piece" of the MAGM matrix can be transformed via permutation into a sub-matrix that mimics a KPGM structure. This transformation is crucial because it enables the use of highly efficient recursive quadrisection sampling algorithms originally designed for KPGM.
By "quilting" these sampled sub-graphs back together, the algorithm achieves an expected time complexity of $O((\log_2(n))^3 |E|)$, where $|E|$ is the number of edges. This represents a massive improvement over the previous $O(n^2)$ bottleneck.
Results and Scalability
The Quilting Algorithm demonstrates unprecedented scalability. In empirical tests, the researchers generated a synthetic graph with 8.3 million nodes and 20 billion edges in under six hours—a task previously impossible for the MAGM model.
Key findings include:
- Linear Scaling: The running time per edge remains nearly constant as the number of nodes increases, confirming that the algorithm scales linearly with the number of edges.
- Statistical Fidelity: The generated graphs maintain the expected statistical properties of MAGM, such as power-law distributions and the growth of the largest strong component, ensuring that speed does not come at the expense of accuracy.
Conclusion
The Quilting Algorithm provides the first sub-quadratic sampling method for Multiplicative Attribute Graphs. By leveraging the mathematical relationship between MAGM and KPGM, it enables the generation of realistic, large-scale networks that were previously beyond reach. Future work may explore high-dimensional similarity search techniques like Locality Sensitive Hashing (LSH) to further optimize performance for graphs with a very high number of attributes.
Summary updated