Weighted Betweenness Preferential Attachment: A New Mechanism Explaining Social Network Formation and Evolution

Alexandru Topîrceanu, Mihai Udrescu, Radu MărculescuScientific 2018 · DOI

Abstract

The dynamics of social networks is a complex process, as there are many factors which contribute to the formation and evolution of social links. While certain real-world properties are captured by the degree-driven preferential attachment model, it still cannot fully explain social network dynamics. Indeed, important properties such as dynamic community formation, link weight evolution, or degree saturation cannot be completely and simultaneously described by state of the art models. In this paper, we explore the distribution of social network parameters and centralities and argue that node degree is not the main attractor of new social links. Consequently, as node betweenness proves to be paramount to attracting new links - as well as strengthening existing links -, we propose the new Weighted Betweenness Preferential Attachment (WBPA) model, which renders quantitatively robust results on realistic network metrics. Moreover, we support our WBPA model with a socio-psychological interpretation, that offers a deeper understanding of the mechanics behind social network dynamics.

Introduction

For decades, the Barabási-Albert (BA) model, rooted in Degree Preferential Attachment (DPA), has been the standard for modeling network growth. The "rich get richer" principle suggests that nodes with higher degrees are more likely to attract new connections. However, DPA fails to account for several critical aspects of human social networks:

  1. Degree Saturation: Unlike the infinite growth suggested by DPA, humans face physical and psychological limits on the number of active friendships (e.g., Dunbar’s number).
  2. Link Weights: Relationships vary in strength (strong vs. weak ties), a nuance lost in binary models.
  3. Community Dynamics: Real-world networks are characterized by clusters and communities, which DPA does not naturally replicate.

This paper addresses these gaps by proposing that "betweenness"—the capacity to act as a bridge between communities—is the primary driver of network evolution.

Methodology: The WBPA Model

The authors introduce the Weighted Betweenness Preferential Attachment (WBPA) model. Betweenness centrality measures how often a node lies on the shortest path between other nodes, serving as a proxy for bridging potential. The WBPA algorithm operates through three core mechanisms:

  • Initial Weight Distribution: New link weights are proportional to the target node's betweenness.
  • Growth via Betweenness: New nodes connect to existing nodes based on a probability proportional to their betweenness rather than their degree.
  • Dynamic Weight Redistribution: To simulate social energy limits, adding a new link causes a redistribution that slightly weakens existing links. If a link's weight reaches zero, it is pruned, naturally leading to degree saturation.

Experimental Setup and Datasets

The model was validated against 18 real-world datasets (ranging from 590 to 364,000 nodes), including Facebook, Google+, Twitter-like platforms (POK, Timik), scientific collaboration networks (Geom, CM), and interaction networks like Enron email and MathOverflow. A Statistical Fidelity ($\phi$) metric was used to compare synthetic networks against these real-world benchmarks across six graph metrics.

Key Results and Discussion

The WBPA model demonstrated significant improvements over traditional degree-driven models. It achieved an average fidelity of $\phi_{Btw} = 0.831$, outperforming the $\phi_{Deg} = 0.777$ of DPA models. Specifically, WBPA excelled in replicating Average Path Length (APL) and Clustering Coefficients (ACC).

Node betweenness vs. node degree in an online social network (OSN).

A crucial finding is the relationship between betweenness and degree. In real networks, this ratio follows a specific distribution. WBPA matched this real-world B/D ratio with a minimal -4.5% difference, whereas traditional models deviated by 50% to 80%.

Comparison of centrality distribution slopes for degree and betweenness.

The "Betweenness Paradox" explains why popular nodes eventually stop growing: as a node bridges a gap and attracts more links, it becomes part of a dense cluster, which may actually decrease its betweenness as it is no longer the unique bridge. This aligns with socio-psychological theories suggesting humans prioritize qualitative "bridging potential" over simple quantitative popularity.

Conclusion

While WBPA offers superior accuracy and a more realistic socio-psychological foundation, it comes with increased computational complexity due to the cost of calculating betweenness centrality. Future research will focus on hybrid models incorporating other centralities, extending the model to directed networks, and further refining the psychological mechanisms of social link formation.

Summary updated

Abstract

The dynamics of social networks is a complex process, as there are many factors which contribute to the formation and evolution of social links. While certain real-world properties are captured by the degree-driven preferential attachment model, it still cannot fully explain social network dynamics. Indeed, important properties such as dynamic community formation, link weight evolution, or degree saturation cannot be completely and simultaneously described by state of the art models. In this paper, we explore the distribution of social network parameters and centralities and argue that node degree is not the main attractor of new social links. Consequently, as node betweenness proves to be paramount to attracting new links - as well as strengthening existing links -, we propose the new Weighted Betweenness Preferential Attachment (WBPA) model, which renders quantitatively robust results on realistic network metrics. Moreover, we support our WBPA model with a socio-psychological interpretation, that offers a deeper understanding of the mechanics behind social network dynamics.
BibTeX
@inproceedings{topirceanu2018weighted,
  author = {Alexandru Topîrceanu and Mihai Udrescu and Radu Mărculescu},
  title = {{Weighted Betweenness Preferential Attachment: A New Mechanism Explaining Social Network Formation and Evolution}},
  booktitle = {Scientific},
  year = {2018},
  doi = {10.1038/s41598-018-29224-w},
}
Figure