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.
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