Leveraging Peer Centrality in the Design of Socially-Informed Peer-to-Peer Systems

Nicolas Kourtellis, Adriana IamnitchiarXiv 2012 · OpenReview

TL;DR

This paper introduces the "projection graph" (PG) model to understand how decentralized social graphs (SGs) in P2P systems affect network properties and routing. They show that by mapping user communities to peers, the PG's centrality metrics can be accurately estimated from the SG, enabling more efficient social search and P2P overlay design.

What Problem Does This Paper Address?

As social applications increasingly rely on user social graphs (SGs) for features like recommendations and security, distributing these SGs across peer-to-peer (P2P) networks presents a challenge. The core problem is understanding how the structure of the SG, when decentralized onto a P2P network, impacts the P2P overlay's performance and how to leverage this for better application design. Specifically, the authors want to know how the topology of the SG and its decentralization affect peer centrality and routing within the P2P system. This is crucial because SGs change slowly, while P2P networks experience high churn, making it desirable to infer P2P network properties from the more stable SG.

Methods

The paper's central contribution is the projection graph (PG) model. This model represents a P2P network where each peer hosts a subset of users from an underlying social graph (SG). PG edges connect peers whose users are socially connected, and their weights reflect the number of SG edges between those users. The authors analytically study three key social network centrality metrics: degree, node betweenness, and edge betweenness. They then experimentally investigate the correlation between these metrics in the SG and the corresponding PG. A significant part of their methodology involves using a "Recursive-Louvain" community detection algorithm to partition large SGs into smaller communities, which are then mapped to individual peers. This allows them to simulate varying degrees of social data decentralization.

Datasets

The authors evaluated their approach using five real-world social and P2P networks:

  • P2P-Gnutella04 and P2P-Gnutella31: Snapshots of the Gnutella file-sharing network.
  • Soc-Epinions1: A trust network from the Epinions review site.
  • Soc-Slashdot0922: A friend/foe network from Slashdot.org.
  • Email-Enron: An email communication network from Enron.

They also used data from Steam Community and LiveJournal for case studies, focusing on user-created groups as a basis for mapping users to peers.

Key Insights and Ideas

  • The Projection Graph (PG) as a bridge: The PG effectively models how a decentralized SG manifests in a P2P network, allowing us to study the P2P overlay's properties through the lens of the SG.
  • Community size matters: There's an "optimal" community size (around 50-150 users per peer) where the PG's properties closely mirror the SG's, leading to high correlation in centrality metrics. This suggests a sweet spot for decentralization.
  • Inferring peer centrality from user centrality: The high correlation observed means that a peer can estimate its own importance (centrality) in the P2P network by aggregating the centrality scores of the users it hosts, without needing global network knowledge. This is crucial for privacy and scalability.
  • PG edges as valuable P2P links: High-weight PG edges, representing strong social ties between communities, can be prioritized for P2P overlay construction and routing, leading to more efficient communication.
  • Local information is often sufficient: For many applications, using local information like degree centrality (either of users or peers) is as effective as using global metrics like node or edge betweenness, simplifying implementation.

Key Results

  • High correlation within optimal community sizes: For community sizes between 50-150 users per peer, the correlation between user centrality in the SG and peer centrality in the PG is high (often > 0.8 for degree and node betweenness).
  • Improved search performance: Social search techniques leveraging PG centrality (especially degree) achieved higher success rates and reduced the number of hops and peers accessed compared to random techniques. For example, in person-finder searches, centrality techniques reduced walk length by 1-2 hops and decreased peer access by up to 40%.
  • Reduced P2P overlay overhead: Using PG edges for P2P overlay construction led to similar or lower system overhead compared to random techniques, with significant reductions in overhead for team-builder searches.
  • Centrality metrics are sensitive to decentralization: The degree and node betweenness centrality of peers increase up to a certain community size (around 50-150 users/peer) and then plateau or decrease, indicating how decentralization impacts network structure. Edge betweenness centrality was found to be more sensitive to community size.

Limitations and Future Work

  • Data replication: The current PG model assumes each user's data is stored on a single peer. Future work could incorporate data replication across multiple peers.
  • Dynamic P2P overlays: While the PG is static, real P2P networks are dynamic. Future research could explore how dynamic P2P overlays can leverage PG properties.
  • Structured P2P overlays: The paper primarily focuses on unstructured P2P overlays. Extending the PG model to structured overlays is a potential future direction.
  • Application-specific optimizations: The authors suggest that further work could explore application-specific optimizations based on PG properties, such as proactive caching informed by predicted social link formation.
  • User-created groups vs. communities: In case studies, users could belong to multiple groups. The authors had to select a single "most representative" group for each user, which is a simplification. Future work could explore more nuanced mapping strategies.

Summary updated

Abstract

Social applications mine user social graphs to improve performance in search, provide recommendations, allow resource sharing and increase data privacy. When such applications are implemented on a peer-to-peer (P2P) architecture, the social graph is distributed on the P2P system: the traversal of the social graph translates into a socially-informed routing in the peer-to-peer layer. In this work we introduce the model of a projection graph that is the result of decentralizing a social graph onto a peer-to-peer network. We focus on three social network metrics: degree, node betweenness and edge betweenness centrality and analytically formulate the relation between metrics in the social graph and in the projection graph. Through experimental evaluation on real networks, we demonstrate that when mapping user communities of sizes up to 50-150 users on each peer, the association between the properties of the social graph and the projection graph is high, and thus the properties of the (dynamic) projection graph can be inferred from the properties of the (slower changing) social graph. Furthermore, we demonstrate with two application scenarios on large-scale social networks the usability of the projection graph in designing social search applications and unstructured P2P overlays.
BibTeX
@misc{kourtellis2012leveraging,
  author = {Nicolas Kourtellis and Adriana Iamnitchi},
  title = {{Leveraging Peer Centrality in the Design of Socially-Informed Peer-to-Peer Systems}},
  year = {2012},
  eprint = {1210.6052},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1210.6052},
}
Figure