Popularity versus similarity in growing networks

Fragkiskos Papadopoulos, Maksim Kitsak, M. Ángeles Serrano, Marián Boguñá, Dmitri Krioukov

Introduction

For over a decade, the "Preferential Attachment" (PA) model has been the standard explanation for the power-law degree distributions observed in complex networks. However, PA suffers from two significant limitations: the "Clustering Paradox," where models predict near-zero clustering despite high clustering in real networks, and the "Global Knowledge Problem," which assumes nodes possess unrealistic global information about the network's state. This paper proposes a unified geometric framework that addresses these issues by balancing a node's popularity with its similarity to others.

The Geometric Framework

The authors map network growth onto a hyperbolic disc, where nodes are defined by two coordinates:

  • Radial Coordinate ($r$): Represents popularity. As the network grows, new nodes are added with increasing radii, while older, more popular nodes remain closer to the center.
  • Angular Coordinate ($\theta$): Represents similarity. Nodes are distributed randomly along the circle, with the angular distance between them reflecting their similarity.
Geometric representation of the popularity-similarity framework on a hyperbolic disc.

Connections are formed by minimizing the product of age and angular distance, which is mathematically equivalent to connecting to the nearest neighbors in hyperbolic space. A "temperature" parameter ($T$) controls the noise in the system; at low temperatures, clustering is maximized, while high temperatures lead the model to converge toward standard Preferential Attachment.

Empirical Validation

To validate the model, the authors analyzed three diverse real-world networks:

  1. Internet (AS level): A technological network.
  2. E. coli Metabolic Network: A biological network.
  3. PGP Web of Trust: A social network.

Using Maximum Likelihood Estimation (MLE) and Markov Chain Monte Carlo (MCMC) methods, the researchers inferred the hidden hyperbolic coordinates of nodes within these systems to test the model's predictive accuracy.

Key Results

The framework demonstrates that Preferential Attachment is an emergent phenomenon resulting from local optimization in hyperbolic space. The model proves that the probability of a node attracting a new link is a linear function of its degree, mirroring PA without requiring global knowledge.

Connection probability as a function of hyperbolic distance across three real-world networks.

As shown in the empirical results, the model's predicted connection probabilities align closely with real-world data across all three domains. Unlike traditional PA, this geometric approach naturally produces the high clustering coefficients ($\bar{c} \approx 0.6-0.8$) observed in actual networks. Furthermore, the model's accuracy in describing link probabilities enables high-precision link prediction.

Discussion and Limitations

While the model provides a powerful universal explanation for network structure, it faces computational challenges. Mapping large-scale networks with millions of nodes using MCMC is currently expensive. Additionally, the model struggles with "over-inflated" clique structures, such as those found in the IMDb actor network, which deviate from the assumption of sparse, distance-based connectivity. Future work may focus on optimizing these mappings and applying the framework to improve recommender systems and information navigation.

Summary updated

Abstract

Popularity is attractive -- this is the formula underlying preferential attachment, a popular explanation for the emergence of scaling in growing networks. If new connections are made preferentially to more popular nodes, then the resulting distribution of the number of connections that nodes have follows power laws observed in many real networks. Preferential attachment has been directly validated for some real networks, including the Internet. Preferential attachment can also be a consequence of different underlying processes based on node fitness, ranking, optimization, random walks, or duplication. Here we show that popularity is just one dimension of attractiveness. Another dimension is similarity. We develop a framework where new connections, instead of preferring popular nodes, optimize certain trade-offs between popularity and similarity. The framework admits a geometric interpretation, in which popularity preference emerges from local optimization. As opposed to preferential attachment, the optimization framework accurately describes large-scale evolution of technological (Internet), social (web of trust), and biological (E.coli metabolic) networks, predicting the probability of new links in them with a remarkable precision. The developed framework can thus be used for predicting new links in evolving networks, and provides a different perspective on preferential attachment as an emergent phenomenon.
BibTeX
@inproceedings{papadopoulos2012popularity,
  author = {Fragkiskos Papadopoulos and Maksim Kitsak and M. Ángeles Serrano and Marián Boguñá and Dmitri Krioukov},
  title = {{Popularity versus similarity in growing networks}},
  booktitle = {Nature},
  year = {2012},
  doi = {10.1038/nature11459},
}
Figure