Analyzing Resilience of Interest-Based Social Networks Against Node and Link Failures

Jun Zhao

TL;DR

This paper introduces a theoretical framework to analyze the resilience of interest-based social networks against both node and link failures. By modeling these networks as intersections of random graphs, the authors derive precise mathematical conditions under which the network remains connected, offering crucial insights for designing robust online platforms.

What Problem Does This Paper Address?

Online social networks are increasingly used for disseminating information, from advertisements to news. The effectiveness of these systems hinges on network connectivity. However, real-world networks are susceptible to failures: users can voluntarily or involuntarily leave (node failures), and communication links can break (link failures). This paper addresses the critical question of how resilient interest-based social networks are to these combined failures, specifically focusing on maintaining connectivity for reliable message dissemination. Existing models often simplify network structures or consider only one type of failure, leaving a gap in understanding the combined impact.

Methods

The authors model interest-based social networks as the intersection of two types of random graphs:

  1. Uniform d-intersection graph ($G_d(n, K_n, P_n)$): This captures shared interests. Users select $K_n$ objects from a pool of $P_n$ objects, and a link forms if they share at least $d$ objects.
  2. Erdős-Rényi graph ($G(n, f_n)$): This models random friendships, where any two users are friends with probability $f_n$.

Link failures are incorporated by intersecting with another Erdős-Rényi graph ($G(n, g_n)$), representing link activity probability. Node failures are then analyzed on this combined graph. The core of the methodology involves deriving a "zero-one law" and an "asymptotically exact probability" for network connectivity. This is achieved through sophisticated mathematical techniques, including graph coupling and probabilistic analysis, to establish lower and upper bounds on connectivity probabilities.

Datasets

  • Anobii Network: A real-world social network of book lovers, used to validate theoretical findings. The authors crawled data from Anobii, focusing on books published after 2010, and constructed a network where users are linked if they share at least 2 common books and are also friends.
  • Synthetic Networks: The paper also generates synthetic networks based on the proposed model to systematically explore the impact of various parameters.

Key Insights and Ideas

  • Interplay of Interests and Friendships: The resilience of these networks is not solely determined by the number of friends but critically depends on the structure of shared interests. A strong interest-based structure can compensate for weaker friendship links.
  • Critical Scaling Laws: The paper identifies precise scaling relationships between network parameters (number of users, objects, interests, friendship probability, link activity) that dictate whether the network remains connected under failure. These laws are crucial for network design.
  • Unified Framework for Failures: By modeling both link and node failures within a single probabilistic framework, the research provides a more realistic assessment of network robustness.
  • Mathematical Elegance: The derivation of a "zero-one law" and "asymptotically exact probability" offers a powerful analytical tool for understanding network behavior at scale.

Key Results

The paper presents Theorem 1, which provides a zero-one law and an asymptotically exact probability for the connectivity of interest-based social networks under both node and link failures. This theorem establishes critical conditions based on the edge probability of the network, which is a function of $n, K_n, P_n, f_n, g_n,$ and $d$.

Specifically, the probability of the network remaining connected after $m$ node failures converges to:

  • 1 if the edge probability scales appropriately (e.g., $\ln n + m \ln \ln n + a_n$ where $a_n \to \infty$).
  • 0 if the edge probability scales too slowly (e.g., $a_n \to -\infty$).
  • An exact value (related to $e^{-a_n^* / (m!)}$) if $a_n$ converges to a finite value $a_n^*$.

Experimental results on the Anobii dataset and synthetic networks visually confirm these theoretical predictions, showing clear transition points in connectivity probability as parameters change.

Limitations and Future Work

  • Model Simplifications: The paper acknowledges that the Erdős-Rényi model for friendships is a simplification. Future work could explore more complex friendship models. Similarly, the uniform d-intersection graph model assumes a specific way interests are shared.
  • Parameter Sensitivity: While the paper provides critical scaling laws, understanding the practical implications of these laws for real-world parameter choices remains an area for further exploration.
  • Beyond Connectivity: The current work focuses on connectivity. Future research could extend this to analyze other network properties like the existence of a giant component or the efficiency of information propagation beyond just reachability.
  • Adversarial Failures: The current model assumes random failures. Analyzing resilience against targeted or adversarial attacks would be a valuable extension.

Summary updated

Abstract

In typical online social networks, users are linked by symmetric friend relations and can define circles of friends based on shared interests. In this paper, we look at social networks where users form links subject to both friendships and shared interests. Our goal is to understand resilience of these networks in terms of connectivity when both nodes and links are allowed to fail. We derive a zero-one law as well as the asymptotically exact probability result for connectivity under both node and link failures. The results answer the question of how to set the network parameters such that reliable message dissemination can be achieved. We formally prove the results and confirm the results via experiments as well.
BibTeX
@article{zhao2017analyzing,
  author = {Jun Zhao},
  title = {{Analyzing Resilience of Interest-Based Social Networks Against Node and Link Failures}},
  journal = {IEEE Trans. Signal Inf. Process. Over Networks},
  year = {2017},
  url = {https://openreview.net/forum?id=QRwoVTUDYG},
}
Figure