Preferential Attachment in Graphs with Affinities

Jay Lee, Manzil Zaheer, Stephan Günnemann, Alexander J. SmolaAISTATS 2015 · OpenReview

Abstract

Preferential attachment models for random graphs are successful in capturing many characteristics of real networks such as power law behavior. At the same time they lack flexibility to take vertex attributes into account. We propose a new model, Preferential Attachment in Graphs with Affinities (PAGA), which bridges the gap between popularity-based and similarity-based growth mechanisms. PAGA is the first model to analytically guarantee power-law degree distributions and small-world properties while allowing for complex, attribute-driven community structures.

Introduction

Most real-world networks—including social media, citation webs, and the internet—exhibit two fundamental features: power-law degree distributions and homophily. In these networks, a few "hub" nodes possess a massive number of connections, and nodes with similar attributes are more likely to connect.

Existing models typically struggle to capture both simultaneously. Standard Preferential Attachment (PA) models, such as the Barabási-Albert model, produce power laws but ignore node attributes. Conversely, vertex attribute models capture affinities but often fail to produce realistic power-law distributions or suffer from mathematical degeneracy. The PAGA model addresses this challenge by providing a mathematically rigorous framework that allows for local community variation while maintaining global structural properties.

The PAGA Model

The PAGA model grows iteratively. When a new node $t+1$ enters the graph, it connects to an existing node $v$ based on a probability proportional to its current degree and its affinity with the new node: $$\text{Pr}(t+1 \to v) \propto d_t(v) + f(v, t+1) - 1$$ where $d_t(v)$ is the current degree of node $v$, and $f(v, t+1)$ is an affinity function representing the similarity between the two nodes.

Unlike many empirical models, PAGA is supported by rigorous proofs. The authors demonstrate that PAGA preserves power-law behavior, with a power-law exponent of $2 + \bar{f}$, where $\bar{f}$ is the average similarity. Additionally, the model is proven to satisfy the "small-world" property, characterized by a logarithmic diameter.

Key Insights: Popularity vs. Similarity

PAGA formalizes the intuition that network connections are driven by both popularity ("rich-get-richer") and similarity (shared attributes). A significant advantage of PAGA is its ability to model sub-graph diversity. Real networks are not monolithic; for instance, different interest groups on a platform like YouTube may grow at different rates. PAGA is uniquely capable of mimicking these varying "local" power laws within a single "global" graph.

Figure 4: Degree distribution of a real-world graph, illustrating distinct power laws for various sub-communities.
Figure 6: Degree distribution generated by the PAGA model, which successfully replicates the local power-law variations observed in real-world data.

Results and Validation

The authors validated PAGA using several datasets from the SNAP and KONECT repositories, including YouTube and high-energy physics citation networks.

  • Structural Match: PAGA graphs closely match real-world eigenvalue distributions (scree plots) and triangle counts, areas where standard PA models often fail.
  • Community Structure: The model successfully generates "grouped" adjacency matrices that exhibit dense internal clusters (communities) while maintaining global dynamics.
  • Inference: The authors developed an algorithm to infer the affinity function $f$ from observed data using logistic regression with L1 regularization. In a case study of physics papers, the model learned that papers on the same topic have high homophily, resulting in a synthetic graph with a power-law exponent (2.97) nearly identical to the real graph (3.12).

Conclusion

PAGA represents a significant step forward in random graph modeling by integrating node attributes into the preferential attachment framework without sacrificing mathematical rigor or structural realism. While the model is highly effective, future work remains in optimizing inference for massive-scale networks where arrival sequences are unknown and exploring dynamic affinities that evolve over time.

Summary updated

Abstract

Preferential attachment models for random graphs are successful in capturing many characteristics of real networks such as power law behavior. At the same time they lack flexibility to take vertex ...
BibTeX
@inproceedings{lee2015preferential,
  author = {Jay Lee and Manzil Zaheer and Stephan Günnemann and Alexander J. Smola},
  title = {{Preferential Attachment in Graphs with Affinities}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2015},
  url = {https://openreview.net/forum?id=dphVl5k-OGh},
}
Figure