Gravity Effects on Information Filtering and Network Evolving

Jinhu Liu, Zi-Ke Zhang, Chengcheng Yang, Lingjiao Chen, Chuang Liu, Xueqi WangarXiv 2013 · arXiv

Introduction

In the era of information overload, recommender systems are essential for navigating vast digital landscapes. Traditional models often struggle to balance the "rich-get-richer" effect of popularity with the "birds of a feather" effect of similarity. This paper proposes a unified framework inspired by classical physics—specifically Newton’s Law of Universal Gravitation—to model social tagging networks and improve recommendation accuracy.

Methodology: The Gravity Model

The authors adapt Newton’s Law ($F = G \frac{m_1 m_2}{r^2}$) to tripartite networks consisting of users, objects, and tags. In this digital gravity model:

  • Mass ($m$): Represents popularity or activity level. For a user, it is the total number of tags used; for an object, it is the total number of tags received.
  • Distance ($r$): Defined by the overlap in shared tags between a user and an object. A higher number of common tags implies a smaller "distance."
  • Recommendation Algorithm: The likelihood of a user selecting an object is proportional to the product of their masses divided by a function of their distance, adjusted by a tunable parameter $\alpha$.

Experimental Setup and Datasets

The model was validated using two real-world datasets: MovieLens (movie ratings and tags) and Del.icio.us (URL bookmarks and tags). These datasets were pre-processed to ensure a minimum activity threshold for users, objects, and tags, ensuring high-quality data for testing.

Key Results

Recommendation Accuracy and the $\alpha$ Parameter

The gravity-based algorithm consistently outperformed baseline models. A critical component of this success is the tunable parameter $\alpha$, which allows the system to balance the influence of popularity (mass) and similarity (distance).

AUC performance as a function of the tunable parameter α for MovieLens and Del.icio.us datasets. The shaded region indicates the optimal range for α.

As shown in the figure above, the Area Under the Curve (AUC) metric is sensitive to $\alpha$. The model achieves peak performance within specific ranges, demonstrating that the optimal balance between popularity and similarity varies by dataset. This flexibility allows the algorithm to be tailored to different network environments.

Network Evolution and Realism

Beyond recommendation, the gravity model (GR) was applied to simulate network growth. Unlike standard random (ER) or preferential attachment (PA) models, the GR model successfully replicated the structural properties of real-world social tagging systems, such as high clustering and disassortative mixing.

Comparison of structural properties between the static real-world network (ST) and various evolution models (ER, PA, GR).

The results in the table above highlight that the GR model achieves a clustering coefficient ($C$) and other metrics far closer to the original static network (ST) than its competitors, proving its ability to mimic real-world network evolution.

Discussion and Limitations

While the gravity model provides a powerful unified framework, it introduces a dependency on the tunable parameter $\alpha$. Finding the optimal value currently requires experimental testing. Additionally, while the model is more efficient than multi-step diffusion iterations, calculating tag-based distances across massive networks remains a computational challenge. Future work will focus on mining "hidden" interests that are not explicitly captured by user-provided tags.

Summary updated

BibTeX
@misc{liu2013gravity,
  author = {Jinhu Liu and Zi-Ke Zhang and Chengcheng Yang and Lingjiao Chen and Chuang Liu and Xueqi Wang},
  title = {{Gravity Effects on Information Filtering and Network Evolving}},
  year = {2013},
  eprint = {1306.4193},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1306.4193},
}
Figure