A Social Identity Approach to Identify Familiar Strangers in a Social Network

Nitin Agarwal, Huan Liu, Sudheendra Murthy, Arunabha Sen, Xufei WangICWSM 2009 · OpenReview

Abstract

We present a novel problem of searching for ‘familiar strangers’ in a social network. Familiar strangers are individuals who are not directly connected but exhibit some similarity. The power-law nature of social networks determines that majority of individuals are directly connected with a small number of fellow individuals, and similar individuals can be largely unknown to each other. Moreover, the individuals of a social network have only a local view of the network, which makes the problem of aggregating these familiar strangers a challenge. In this work, we formulate the problem, show why it is significant to address the challenge, and present an approach that innovatively employs the social identities of the individuals with competitive approaches. A blogger and citation network are used to showcase technical details and empirical results with related issues and future work.

Introduction

In the physical world, a "familiar stranger" is a person one encounters repeatedly—perhaps on a daily commute—but never interacts with. In the digital landscape of social networks, these are users who share significant interests, hobbies, or professional backgrounds but remain outside one's immediate social circle.

The primary challenge in identifying these individuals lies in the topological structure of social networks, which typically follow a "long-tail" or power-law distribution. Most users possess very few direct contacts, meaning that highly similar individuals are often separated by multiple hops. From a computational perspective, finding these individuals is expensive. Most users only possess a "local view" of the network (their immediate friends), and an exhaustive search for similar peers across the entire graph grows exponentially ($O(d^h)$). This research proposes a method to "search smart" by leveraging local information to navigate the network efficiently.

Methodology: The Social Identity Approach

The authors propose a Social Identity Approach to search through egocentric views of a network. This method is rooted in Social Identity Theory, which posits that individuals naturally categorize their social contacts into meaningful groups based on shared attributes.

Figure 1: Conceptual framework showing the local knowledge of a seed blogger 'u' and the goal of identifying familiar strangers within the broader network.

The approach consists of two main phases:

  1. Social Identity Construction: Rather than treating every contact as an isolated node, the system clusters a user’s contacts based on metadata (e.g., blog tags, publication venues). By employing k-means clustering and Latent Semantic Analysis (LSA), the algorithm manages high-dimensional and sparse data to form coherent "social identities" for groups of contacts.
  2. Guided Search Algorithm: When a user seeks a stranger matching a specific "goal" (e.g., an interest in "Sports"), the algorithm identifies the cluster of contacts most aligned with that goal. It then propagates the search specifically through those contacts, effectively pruning irrelevant branches of the network at every step.

To establish a performance baseline, the authors compared their results against the Steiner Tree problem, using a 2-approximation algorithm to represent the theoretical lower bound for the search space required to connect similar nodes with a global view.

Datasets and Experimental Setup

The study evaluated the approach using two distinct real-world datasets:

  • BlogCatalog: A social directory containing 23,566 nodes and approximately 1.1 million links. Attributes included blog categories and tags.
  • DBLP: A bibliography of computer science publications with 35,001 nodes and roughly 1 million links. Here, social connections were defined by co-authorship, and attributes were derived from publication venues.

Key Results

The Social Identity Approach (SocialId) demonstrated significant advantages over both Exhaustive and Random search methods in terms of both accuracy and efficiency.

Figure 6: Comparison of search steps required to reach varying levels of accuracy. The SocialId approach remains highly efficient compared to the exponential cost of exhaustive search.
  • Accuracy: The method achieved 79.3% accuracy on BlogCatalog and 91.3% on DBLP. For comparison, a random search under identical constraints yielded less than 3% accuracy.
  • Efficiency: The reduction in search space was profound. On the BlogCatalog dataset, the Social Identity approach required searching only 0.1331% of the space that an exhaustive search would have traversed.
  • Scalability: As shown in Figure 6, while the cost of an exhaustive search explodes as accuracy requirements increase, the Social Identity approach remains near the Steiner Tree lower bound, making it suitable for massive, real-world social graphs.

Conclusion and Future Work

The research highlights that "who you know" is often less critical for network navigation than understanding "what your friends are interested in." By transforming metadata into social identities, search becomes a guided process rather than a blind crawl.

However, several areas for future research remain. The current clustering process is static and performed offline; in dynamic environments like real-time social media, these identities would require frequent updates. Furthermore, while the Steiner Tree provides a mathematical proxy for ground truth, defining the "ideal" familiar stranger remains a subjective challenge. Finally, the privacy implications of aggregating user metadata to facilitate these searches warrant further ethical consideration.

Summary updated

Abstract

We present a novel problem of searching for ‘familiar strangers’ in a social network. Familiar strangers are individuals who are not directly connected but exhibit some similarity. The power-law nature of social networks determines that majority of individuals are directly connected with a small number of fellow individuals, and similar individuals can be largely unknown to each other. Moreover, the individuals of a social network have only a local view of the network, which makes the problem of aggregating these familiar strangers a challenge. In this work, we formulate the problem, show why it is significant to address the challenge, and present an approach that innovatively employs the social identities of the individuals with competitive approaches. A blogger and citation network are used to showcase technical details and empirical results with related issues and future work.
BibTeX
@inproceedings{agarwal2009social,
  author = {Nitin Agarwal and Huan Liu and Sudheendra Murthy and Arunabha Sen and Xufei Wang},
  title = {{A Social Identity Approach to Identify Familiar Strangers in a Social Network}},
  booktitle = {ICWSM},
  year = {2009},
  url = {https://openreview.net/forum?id=uAA5w90M7L},
}
Figure