Real-Time Association Mining in Large Social Networks

Benjamin Paul Chamberlain, Josh Levy-Kramer, Clive Humby, Marc Peter DeisenrotharXiv 2016 · OpenReview

TL;DR

This paper introduces a novel single-machine system for real-time community detection in massive social networks. By compressing user neighborhoods using minhash signatures and enabling fast queries with Locality Sensitive Hashing, the system achieves millisecond response times on standard laptops, making large-scale graph exploration interactive and accessible.

What Problem Does This Paper Address?

Analyzing the structure and communities within large social networks is crucial for various applications, from understanding societal allegiances to optimizing marketing strategies. However, the sheer scale of these networks (billions of users and connections) typically necessitates expensive, distributed computing systems. These systems are complex to maintain and often lack the responsiveness needed for interactive exploration. This paper addresses the challenge of performing real-time community detection on these massive graphs using only a single, commodity laptop, bridging the gap between the need for scalable analysis and the practical limitations of current infrastructure.

Methods

The core of the proposed system lies in two key techniques:

  • Minhash Signatures for Neighborhood Compression: Instead of storing the full neighborhood graph for each user (which can be millions of nodes), the authors represent each user's neighborhood as a fixed-length "minhash signature." This signature is a compressed representation that efficiently estimates the Jaccard similarity between two users' neighborhoods. This dramatically reduces memory requirements, allowing massive graphs to fit into a single machine's memory.
  • Locality Sensitive Hashing (LSH) for Fast Queries: To quickly find users similar to a given set of "seed" users, the system employs LSH. LSH is designed to efficiently find approximate nearest neighbors in high-dimensional spaces. By using the minhash signatures, LSH can rapidly identify candidate similar users, avoiding the need for exhaustive pairwise comparisons.

These techniques are combined in a two-stage process: first, "seed expansion" uses LSH to find a set of candidate similar accounts, and second, a global community detection algorithm (WALKTRAP) is applied to a weighted graph constructed from these candidates to reveal community structures.

Datasets

The primary dataset used in this research is the Twitter Follower network, comprising approximately 700 million vertices and 20 billion edges. The authors also present results using a Facebook Pages engagement graph with 450 million vertices and 700 million edges to demonstrate the generalizability of their approach.

Key Insights and Ideas

  • Neighborhood Similarity as a Robust Metric: The paper argues that the Jaccard similarity of user neighborhoods is a surprisingly robust metric for identifying associations in noisy social networks. This is because neighborhoods are shaped by the collective actions of many users, making them less susceptible to individual noise or manipulation compared to other attributes like profile text.
  • Minhash and LSH Enable Real-Time on a Laptop: The combination of minhash for compression and LSH for fast querying is the critical innovation that allows for real-time performance on standard hardware. This is a significant departure from traditional approaches that rely on distributed systems.
  • Interactive Exploration is Key: The authors emphasize that real-time performance is not just about speed but about enabling interactive exploration. This allows analysts to iteratively refine their queries and gain deeper insights, mirroring the experience of using interactive programming languages like Python and R.

Key Results

  • Dramatic Speedup: The system reduces query times from hours on industrial desktop machines to milliseconds on standard laptops.
  • Significant Space Reduction: Minhash signatures reduce the memory requirement for representing the graph by a factor of approximately 1000.
  • High Accuracy: The minhash approximation for Jaccard similarity achieves an error of just 0.001 at 1,000 hashes, with a Spearman rank correlation of 0.97 with true Jaccard similarities.
  • Superior Performance to PPR: In experiments comparing their method (specifically Minhash Similarity and Agglomerative Clustering) against Personal PageRank (PPR), their approach consistently achieved higher recall across various ground-truth communities, especially for diffuse communities.
  • Practical Deployment: The system has been deployed in software actively used by social network analysts.

Limitations and Future Work

  • Binary Graph Assumption: The current system treats the social network graph as binary (presence or absence of a connection). The authors suggest future work to incorporate edge weights (e.g., message counts, connection time) using extensions to minhashing for weighted sets.
  • Theoretical Bounds for DSNs: While b-bit minhashing and Odd Sketches offer theoretical advantages for very similar sets, their strong theoretical bounds do not hold for typical DSN settings where Jaccard similarities are often low. Further cost-benefit analysis would be needed to implement these for DSNs.
  • Generalizability to Other Network Types: While the method is presented for social networks, the authors believe it is applicable to other large networks, including bipartite networks (e.g., recommender systems), which could be a fruitful area for future research.

Summary updated

Abstract

For a broad range of research, governmental and commercial applications it is important to understand the allegiances, communities and structure of key players in society. One promising direction towards extracting this information is to exploit the rich relational data in digital social networks (the social graph). As social media data sets are very large, most approaches make use of distributed computing systems for this purpose. Distributing graph processing requires solving many difficult engineering problems, which has lead some researchers to look at single-machine solutions that are faster and easier to maintain. In this article, we present a single-machine real-time system for large-scale graph processing that allows analysts to interactively explore graph structures. The key idea is that the aggregate actions of large numbers of users can be compressed into a data structure that encapsulates user similarities while being robust to noise and queryable in real-time. We achieve single machine real-time performance by compressing the neighbourhood of each vertex using minhash signatures and facilitate rapid queries through Locality Sensitive Hashing. These techniques reduce query times from hours using industrial desktop machines operating on the full graph to milliseconds on standard laptops. Our method allows exploration of strongly associated regions (i.e. communities) of large graphs in real-time on a laptop. It has been deployed in software that is actively used by social network analysts and offers another channel for media owners to monetise their data, helping them to continue to provide free services that are valued by billions of people globally.
BibTeX
@misc{chamberlain2016real,
  author = {Benjamin Paul Chamberlain and Josh Levy-Kramer and Clive Humby and Marc Peter Deisenroth},
  title = {{Real-Time Association Mining in Large Social Networks}},
  year = {2016},
  eprint = {1601.03958},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1601.03958},
}
Figure