PaperlayerView exact revision on arXiv

Source-linked AI summary

Discovering Social Circles in Ego Networks

Julian McAuley, Jure Leskovec

arXiv:1210.8182v3cs.SIphysics.soc-ph

TL;DR

Manually organizing large personal social networks into circles is laborious and does not update automatically. The paper learns overlapping, nested social circles from ego-network structure and profile information, accurately detecting circles across Facebook, Google+, and Twitter.

  • Problem

    Existing manual or naive methods for organizing social circles are time-consuming, fail to update automatically, or miss individual community structure when profile information is limited.

  • Method

    The model treats circle affiliations as latent multi-membership variables and learns circle-specific profile similarity dimensions alongside network structure.

  • Results

    Experiments on Facebook, Google+, and Twitter show that circles can be accurately detected using both network and profile information, including disjoint, overlapping, and hierarchically nested circles.

  • Takeaways & Limitations

    Automatically detecting circles can organize personal-network information while accommodating multiple types of circle membership and weak user supervision.

  • Takeaways & Limitations

    The approach requires quadratic memory for pairwise node compatibility, limiting scalability beyond the fewer-than-1,000-friend ego-networks typically encountered.

Abstract

from arXiv · show

People's personal social networks are big and cluttered, and currently there is no good way to automatically organize them. Social networking sites allow users to manually categorize their friends into social circles (e.g. 'circles' on Google+, and 'lists' on Facebook and Twitter), however they are laborious to construct and must be updated whenever a user's network grows. In this paper, we study the novel task of automatically identifying users' social circles. We pose this task as a multi-membership node clustering problem on a user's ego-network, a network of connections between her friends. We develop a model for detecting circles that combines network structure as well as user profile information. For each circle we learn its members and the circle-specific user profile similarity metric. Modeling node membership to multiple circles allows us to detect overlapping as well as hierarchically nested circles. Experiments show that our model accurately identifies circles on a diverse set of data from Facebook, Google+, and Twitter, for all of which we obtain hand-labeled ground-truth.

1 Introduction

The paper frames automatic social-circle discovery as a user-specific clustering problem on ego-networks, addressing the limitations of manual and feature-based organization. Its model combines network structure with profile information to detect overlapping and nested circles, with experiments across three platforms.

  • Social circles support content filtering, privacy, and sharing groups of users across services such as Google+, Facebook, and Twitter.
  • Manual circle construction is time-consuming and does not automatically adapt as users add friends, while naïve feature-based grouping misses individual community structure and suffers when profile information is unavailable.
  • Circle discovery is formulated as clustering the friendship network among one user’s friends, called the ego-network.
  • The paper introduces an unsupervised model that jointly learns circle memberships and profile-similarity dimensions, while also supporting circle updates and seed-based weak supervision.
  • The model represents multiple memberships and circle-specific profile similarity, allowing circles to overlap or form hierarchically within one another.
  • Experiments use hand-labeled circles from Facebook, Google+, and Twitter and report better performance than natural alternatives and the state of the art.

2 A Generative Model for Friendships in Social Circles

The generative model treats circle memberships as latent variables and explains observed edges using both circle structure and pairwise profile similarity. Circle-specific parameters encode which profile dimensions characterize each circle.

  • Its design targets common properties, different aspects across circles, overlapping or nested memberships, combined profile and network evidence, and interpretable explanations.
  • The model takes an ego-network and user profiles as input and predicts circles together with parameter vectors describing how each circle emerged.
  • Pairwise features φ(x, y) encode shared profile properties, while each circle’s θ_k identifies the similarity dimensions associated with that circle.
  • Circle memberships are latent, and nodes sharing a circle receive opportunities to form edges, naturally permitting overlapping and hierarchical circles.
  • The model distinguishes edges within a circle from edges outside or crossing it through the circle-specific trade-off parameter α_k.

3 Unsupervised Learning of Model Parameters

The paper learns memberships and model parameters by alternating optimization, using graph-based approximation for circle assignments and quasi-Newton optimization for similarity parameters. Regularization promotes interpretable models, while BIC selects the number of circles.

  • The learning objective maximizes a regularized log-likelihood while treating circle memberships as latent variables.
  • Coordinate ascent alternates between optimizing circle memberships and model parameters until memberships converge.
  • L-BFGS optimizes the smooth parameter objective, while ℓ1 regularization yields sparse and readily interpretable parameters.
  • For a fixed circle, membership optimization is expressed as pseudo-Boolean optimization and approximately solved with QPBO.
  • The number of circles is chosen by minimizing an approximation to the Bayesian Information Criterion, whose parameter penalty increases linearly with K.
  • An additional circle is added only when it has a significant impact on the log-likelihood.

4 Extensions

The extensions adapt the model to evolving ego-networks and partial user supervision. They predict memberships for new friends and use seed nodes as constraints, with substantial accuracy gains already from a few seeds.

  • The semi-supervised extensions condition on partially observed circle assignments so users can update and maintain circles as their networks evolve.
  • For a newly added friend, the model predicts memberships from the friend’s features and connectivity to existing ego-network nodes.
  • New-node membership prediction requires evaluating only likelihood terms involving that node, reducing computation from quadratic to linear time.
  • With seed-node supervision, manually labeled users are imposed as membership constraints rather than inferred as latent variables.
  • On Facebook, approximately 25% of circles are entirely contained within another circle, illustrating the nested structures the model must accommodate.

5 Dataset Description

The evaluation uses ego-networks and social-circle ground truth from Facebook, Google+, and Twitter, totaling 1,143 ego-networks, 5,541 circles, and 192,075 users. Facebook is fully labeled, whereas Google+ and Twitter provide only publicly accessible circles.

  • Facebook: 10 Facebook ego-networks contain 193 circles and 4,039 users, with participants labeling each network in 2–3 hours.Users identified an average of 19 circles, each containing 22 friends on average.
  • Circle structure: The Facebook circles exhibit substantial overlap: about one quarter are independent, a similar fraction are nested, and the remaining 50% overlap with another circle.These patterns characterize the 193 user-labeled circles across 10 Facebook ego-networks.
  • Google+ and Twitter: 133 Google+ ego-networks contain 479 circles and 106,674 users, while 1,000 Twitter ego-networks contain 4,869 circles.The Google+ networks are directed, and the model can be applied to directed or undirected networks.
  • Dataset composition: 1,143 ego-networks, 5,541 circles, and 192,075 users comprise the combined Facebook, Google+, and Twitter dataset.The dataset sizes differ because data availability varied across sources.
  • Ground truth: Facebook circles are fully labeled, whereas Google+ and Twitter circles are only partially labeled because only public circles are available.The three sources together provide diverse evaluation data, but their ground-truth completeness differs.

6 Constructing Features from User Profiles

The feature construction represents user profiles as hierarchical trees and encodes profile compatibility at different granularities. It tests whether circles reflect similarities among alters or similarities between alters and the ego.

  • Profile representation: User profiles are represented as trees whose levels move from broad categories to increasingly specific values.For example, education can branch into location or type, ending in values such as Princeton or Graduate School.
  • Similarity hypotheses: The model tests two hypotheses: circles may group alters sharing properties with one another or properties with the ego.A Stanford circle illustrates the distinction between alter–alter and alter–ego similarity.
  • Difference vectors: Difference vectors encode profile dimensions where two users match or differ, using either fine-grained leaf values or broader parent categories.Leaf-level encoding can reach 4,122 dimensions, while parent-category encoding uses a constant number of dimensions per platform.
  • Connectivity feature: A constant feature captures within-circle edge propensity and permits membership prediction when profile information is absent.This connectivity signal measures the extent to which circles consist of friends.
  • Compatibility features: Four feature combinations represent alter–alter or alter–ego compatibility using two difference-vector constructions and two compatibility functions.The experiments assess which of these assumptions better captures users’ subjective circle definitions.

7 Fast Inference in Large Ego-Networks

The fast-inference method accelerates MCMC membership updates by collapsing nodes with identical community memberships and features into types. This reduces each update to distinct node types plus the average node degree, but the original model still has quadratic memory requirements.

  • Scalability: Quadratic memory is required to encode compatibility between every node pair, limiting scalability despite handling ego-networks with fewer than 1,000 friends.The paper proposes a more scalable alternative for larger networks.
  • Type complexity: At most 2^K+F community/feature combinations are possible for K communities and F binary feature dimensions, though actual types are also bounded by |V|.In practice, shared features and dependent memberships make the number of distinct types much smaller.
  • Collapsed MCMC: The sampler collapses nodes sharing community memberships and features, allowing MCMC updates to operate over node types rather than individual nodes.The adaptation applies beyond binary features when many users share feature values.
  • Node types: Each node type concatenates a binary community-membership string with a binary feature string, and a sparse table counts nodes of each type.Community memberships and features are represented separately before forming the combined type.
  • Membership updates: A membership update computes likelihood contributions for node types, corrects them using incident edges, and samples the new binary label.The sampler repeatedly updates each node’s label in each community using a temperature-controlled probability.
  • Runtime: The running time of one update is linear in the number of distinct node types plus the average node degree.Both quantities are bounded by the number of graph nodes.

8 Experiments

The experiments compare predicted latent circles with hand-labeled circles using balanced error, F1, and alignment procedures. They select the number of circles with criteria that accommodate overlapping communities and account for ground-truth completeness.

  • Evaluation metrics: The evaluation compares converged maximum-likelihood latent circles with human-labeled ground-truth circles.The primary alignment measure is Balanced Error Rate, supplemented by F1.
  • Evaluation metrics: Balanced Error Rate weights false positives and false negatives equally, giving trivial or random predictions an average error of 0.5.The authors report qualitatively similar results with F1.
  • Circle alignment: Predicted and ground-truth circles are aligned by linear assignment that maximizes correspondence across the two circle sets.The correspondence may be partial when the predicted and ground-truth circle counts differ.
  • Circle-count selection: The evaluation estimates the number of circles with established techniques so baselines are not disadvantaged by mispredicting K̂ = |C|.This controls for errors in estimating the number of circles when comparing methods.
  • Facebook evaluation: For Facebook, additional predicted circles are penalized because the survey ground truth is intended to include every user-considered circle.The method never predicted more than 10 circles, while users identified 19 on average.
  • Model selection: The Bayesian Information Criterion is used for probabilistic models because it permits overlapping communities, unlike modularity, which assumes disjoint communities.Modularity instead measures dense internal and sparse external connections and selects K̂ by maximizing its value.

8.3 Baselines

The paper compares its model with baselines using network structure, profile information, or both, and reports better performance across Facebook, Google+, and Twitter. Its results also support modeling hard memberships in multiple circles while combining node and edge information.

  • Baselines: The baselines include methods using only network structure, only profile information, or both.Reported alternatives include mixed-membership stochastic block models, Block-LDA, K-means, clique percolation, low-rank embedding, and multi-assignment clustering.
  • Performance: The best model achieves BER scores of 0.84 on Facebook, 0.72 on Google+, and 0.70 on Twitter.Its corresponding F1 scores are 0.59, 0.38, and 0.34, respectively.
  • Performance: The model outperforms all baselines on every dataset by a statistically significant margin.Compared with the nearest competitors, φ1 improves BER by 43% on Facebook, 26% on Google+, and 16% on Twitter.
  • Modeling choice: Good performance depends critically on predicting hard memberships to multiple circles using both node and edge information.The baselines do not combine these capabilities precisely, which the paper identifies as a shortcoming addressed by its model.
  • Feature analysis: Compressed profile features do not significantly reduce performance and are sufficient for modeling shared attribute categories rather than exact attribute values.The friend-to-friend and friend-to-user feature schemes perform similarly.
  • Qualitative analysis: The method correctly identifies overlapping circles and sub-circles in example Facebook and Google+ ego-networks.Learned parameter vectors also identify circle-specific social dimensions, while community membership provides the strongest edge-formation signal and profile data remains relevant.

8.6 Circle Maintenance

The paper evaluates adding users to existing circles, incorporating seed-node supervision, and scaling inference to large ego-networks. Seed nodes improve prediction, while the scalable MCMC procedure handles large networks at a substantial runtime cost.

  • Adding users: For circle maintenance, the model suppresses one user, learns parameters from the remaining ego-network and circles, and predicts that user’s memberships.The experiment repeats for 10 random choices of the suppressed user per ego-network.
  • Adding users: The maintenance model is compared with a fully supervised SVM that classifies membership independently for each community using node features.The SVM does not use edge information or interdependencies between circles.
  • Adding users: The best features achieve BER values of 0.30, 0.34, and 0.34 on Facebook, Google+, and Twitter, with F1 scores of 0.38, 0.59, and 0.54, respectively.The SVM performs better when rich node features are available, but node information alone is uninformative on Google+ and Twitter.
  • Seed supervision: Adding seed nodes significantly increases accuracy for every tested number of circles, especially when users identify only a small number of circles.For small K, most of the benefit is gained after only two seeds.
  • Scalability: The MCMC inference method scales better than QPBO for large ego-networks, although identifying K = 10 circles on 1,000 nodes takes around one hour.QPBO becomes intractable around 1,000 nodes because it optimizes a distribution defined on complete graphs; MCMC can collapse nodes with identical features and memberships.
  • Scalability: MCMC accuracy is best on reasonably small ego-networks and degrades for large ego-networks, while small networks comprise most of the data.Its results are slightly worse than Figure 4 because K is not selected using BIC.

9 Discussion and Future Work

The model performs best on ego-networks with up to a few hundred nodes, while accuracy degrades for networks exceeding 1,000 nodes. Its independent-per-user formulation also cannot exploit cross-user circle relationships because complete network information is unavailable.

  • Future work: Modeling each user independently simplifies scaling into separate small problems but prevents exploiting relationships between circles across users.
  • Future work: Complete network information would be needed to test cross-user or whole-network circle models, which the available data do not provide.
  • Scalability: Performance is strongest on ego-networks with up to a few hundred nodes but degrades significantly beyond 1,000 nodes.The paper leaves open whether this reflects harder optimization or model assumptions breaking down at larger scales.
  • Scalability: The close-knit, shared-property assumption underlying the model fits networks with at most a few hundred nodes better.
  • Scope: Performance on Facebook networks with over 1,000 friends exceeds that on small Google+ and Twitter networks, implicating network nature alongside size.

10 Conclusion

The paper presents an unsupervised algorithm for detecting social circles in ego-networks using network and profile information. Evaluated across Facebook, Google+, and Twitter, the model detects disjoint, overlapping, and hierarchically nested circles accurately.

  • The algorithm automatically detects social circles in ego-networks, addressing the burden of manually organizing personal social-network data.
  • The model is designed for disjoint, overlapping, and hierarchically nested circles and combines network structure with profile information.
  • Experiments on 1,143 ego-networks and 5,541 ground-truth circles from Facebook, Google+, and Twitter show that circles can be accurately detected.
Loading 1210.8182v3…