Beyond preferential attachment: falling of stars and survival of superstars

Shahar Somin, Yaniv Altshuler, Alex Pentland, Erez ShmueliRoyal 2022 · DOI

TL;DR

This paper reveals a surprising divergence between how node popularity changes in networks based on absolute degree versus relative rank. While absolute popularity follows predictable "rich-get-richer" patterns, relative popularity exhibits a non-monotonic, inverse-U shaped dynamic, leading to distinct stability zones for nodes. This challenges the long-held assumption of monotonic dynamics in network evolution and offers new explanations for phenomena like superstar stability.

What Problem Does This Paper Address?

For decades, network science has largely relied on the "preferential attachment" model, which posits that nodes with more connections (higher degree) are more likely to gain new connections. This leads to a predictable, monotonic increase in popularity for high-degree nodes. However, many real-world systems, from scientific citations to social media, are often analyzed by rank rather than absolute degree. This paper asks a crucial question: do these same preferential attachment dynamics apply to node rank? If not, what governs the evolution of relative popularity, and what are the implications for understanding network stability and the behavior of "superstars"?

Methods

The authors employ a multi-pronged approach:

  • Empirical Analysis: They analyze three real-world datasets (Amazon product rankings, Ethereum blockchain transactions, and eToro social trading platform) to observe temporal changes in both node degrees and ranks.
  • Theoretical Modeling: They develop an agent-based model to simulate network evolution and derive analytical expressions for rank change dynamics. This model incorporates preferential attachment for degree but explores non-monotonic rank dynamics.
  • Comparative Analysis: They directly compare the dynamics of absolute degree changes with relative rank changes to highlight differences.

Datasets

The study utilizes three distinct, publicly available datasets:

  1. Amazon Rankings Dataset: Product reviews and metadata from Amazon, spanning May 1996 to July 2014. This dataset was used to construct weekly bipartite networks of users, products, and ratings.
  2. Ethereum Blockchain Trading Ledger: Records of all Ethereum transactions from February 2016 to June 2018. Weekly bipartite networks of traders and cryptocurrencies were built, with edges representing trades.
  3. eToro Social Trading Platform: Data from an online social trading platform, encompassing approximately 3 million accounts and over 40 million trades over three years. Weekly networks of traders were constructed, with edges representing copying actions.

Key Insights and Ideas

  • Rank vs. Degree Divergence: The most striking finding is that preferential attachment, which strongly governs absolute degree, does not apply to relative rank. This means the "rich get richer" principle for popularity doesn't directly translate to rank.
  • The Inverse-U Shape: Rank changes, particularly rank deterioration, follow a non-monotonic, inverse-U shaped curve. This suggests that nodes in certain rank positions are inherently more or less stable than others.
  • Stability Zones: The inverse-U dynamics imply a partition of nodes into four distinct stability categories:
  • Top-ranked: High stability, minor rank changes expected.
  • Mid-high ranked: High instability, prone to significant rank drops.
  • Mid-low ranked: High stability, expected to preserve rank.
  • Bottom-ranked: High instability, with potential for significant rank increases.
  • Superstar Survival: The findings help explain how top-ranked "superstars" can maintain their positions despite fluctuations in their absolute network degrees. They are likely to fall into a stable rank category.
  • Star Instability: Conversely, nodes that are highly popular but not quite superstars (mid-high ranked) are more prone to rank instability and falling.

Key Results

  • Empirical analysis across all three datasets consistently shows that while degree changes exhibit monotonic, preferential attachment patterns, rank changes (both improvement and deterioration) do not.
  • The average rank deterioration, R₁(r), as a function of current rank (r) consistently forms an inverse-U shaped curve across all datasets and in the theoretical model.
  • The agent-based model simulations predict that nodes tend to converge into one of two stable categories: "Top ranked" or "Mid-low ranked."
  • The model's analytical derivation of rank change (R₁) shows a clear inverse-U shape, with the exact curve properties depending on system parameters like the number of nodes (N), number of edges (H), and the power-law distribution parameter (γ).

Limitations and Future Work

  • Computational Limits: The authors note that fitting the model to the Amazon and Blockchain datasets was computationally challenging due to their large parameters, suggesting a need for more efficient implementations or analysis of smaller datasets.
  • Analytical Approximations: While the model provides a good fit for the eToro dataset, further analytical work is needed to derive precise expressions for the inverse-U curve and establish upper/lower bounds, which could better support empirical findings.
  • Temporal Stability: The study presents preliminary results on year-long intervals of the Amazon dataset, showing inverse-U patterns persist but curve characteristics change over time. Investigating how system stability evolves over longer periods is a promising future direction.
  • Generalizability: The authors suggest that the findings might extend beyond explicit network structures to any system with preferential attachment and power-law degree distributions, warranting further investigation in such settings.
  • Policy Implications: The insights could inform policymakers and regulators on how to influence system dynamics and control internal mobility.

Summary updated

Abstract

Numerous studies over the past decades established that real-world networks typically follow preferential attachment and detachment principles. Subsequently, this implies that degree fluctuations monotonically increase while rising up the 'degree ladder', causing high-degree nodes to be prone for attachment of new edges and for detachment of existing ones. Despite the extensive study of node degrees (absolute popularity), many domains consider node ranks (relative popularity) as of greater importance. This raises intriguing questions-what dynamics are expected to emerge when observing the ranking of network nodes over time? Does the ranking of nodes present similar monotonous patterns to the dynamics of their corresponding degrees? In this paper, we show that surprisingly the answer is not straightforward. By performing both theoretical and empirical analyses, we demonstrate that preferential principles do not apply to the temporal changes in node ranking. We show that the ranking dynamics follows a non-monotonous curve, suggesting an inherent partition of the nodes into qualitatively distinct stability categories. These findings provide plausible explanations to observed yet hitherto unexplained phenomena, such as how superstars fortify their ranks despite massive fluctuations in their degrees, and how stars are more prone to rank instability.
BibTeX
@inproceedings{somin2022beyond,
  author = {Shahar Somin and Yaniv Altshuler and Alex Pentland and Erez Shmueli},
  title = {{Beyond preferential attachment: falling of stars and survival of superstars}},
  booktitle = {Royal},
  year = {2022},
  doi = {10.1098/rsos.220899},
}
Figure