I Like Her more than You: Self-determined Communities

Maria-Florina Balcan, Christian Borgs, Mark Braverman, Jennifer T. Chayes, Shang-Hua Teng

Abstract

A central challenge in e-commerce and social network analysis is identifying overlapping communities among individuals or objects without external tags or metadata. We address this by introducing a framework based on "affinity systems," where communities are defined by the relative preferences of their members. We define "self-determined" communities as groups that collectively prefer each other over outsiders. This paper provides a tight polynomial bound on the number of such communities and presents a polynomial-time algorithm for their enumeration. Furthermore, we develop a local algorithm with strong stochastic guarantees that can locate a community in time nearly linear to the community's size. Our framework allows for the "lifting" of sparse social networks into dense affinity systems, providing a robust and computationally tractable alternative to traditional clustering models.

Introduction

Traditional community detection often relies on graph density—the idea that everyone in a group is friends—or external identification. However, real-world communities, such as researchers in a niche sub-field or consumers with specific tastes, are often endogenous and overlapping. They are defined not by a central authority, but by the internal preferences of the members themselves.

Existing mathematical models, such as $(\alpha, \beta)$-clusters, attempt to capture this but face significant computational hurdles. A single network can contain a superpolynomial number of such clusters, making them impossible to list for large datasets. Moreover, finding even one such cluster can be as difficult as solving the "Hidden Clique" problem. This research introduces a more robust definition of a community that is both mathematically sound and computationally efficient.

The Affinity System Framework

At the core of our approach is the Affinity System. In this model, every individual in a set has a ranked list of preferences for every other individual. This moves away from simple binary connections (friend/not friend) to a more nuanced representation of relative affinity.

The Voting Mechanism

To determine if a subset $S$ constitutes a community, we employ a voting mechanism:

  1. Voting: Every member of $S$ "votes" for their top $\theta|S|$ preferred individuals.
  2. Self-Determination: A group is considered a $(\theta, \alpha, \beta)$ self-determined community if:
  3. Internal Support ($\alpha$): Every member inside the group receives a high fraction of votes from their peers.
  4. External Leakage ($\beta$): Every person outside the group receives a low fraction of votes from the group.

By limiting the number of votes a member can cast (the $\theta$ parameter), the model prevents "popularity" from distorting the results. This forces the algorithm to focus on relative affinity rather than global celebrity.

Algorithmic Contributions

We propose a multi-stage process to identify these communities:

  • Approximation: Using a small "seed" of members to identify a rough set that overlaps significantly with the target community.
  • Purification: Refining the rough set into the exact community using a sampling-based approach.
  • Filtering: Removing candidates that fail to meet the strict self-determination criteria.

Local Search for Scale

For massive, internet-scale networks, we provide a local algorithm. Starting with a single seed vertex, the algorithm explores the network only as much as necessary to find that vertex's community. We achieve a near-linear time complexity of $O(t \log t)$, where $t$ is the size of the community, rather than the size of the entire network.

Theoretical Insights

Unlike previous models, we prove that the number of self-determined communities is always polynomial relative to the number of nodes ($n^{O(\log(1/\alpha)/\alpha)}$). This ensures that the enumeration of all communities is a tractable problem.

Furthermore, we address the "Lifting" problem. Social networks are often sparse, but we demonstrate that they can be transformed into dense affinity systems using techniques such as Personalized PageRank or Shortest Path distances. This allows our preference-based algorithms to be applied to standard graph data.

Results and Comparison

Our analysis connects self-determined communities with $(\alpha, \beta)$-clusters. We formally demonstrate that while finding traditional $(\alpha, \beta)$-clusters is as hard as the Hidden Clique problem, our self-determined definition provides a necessary path forward for practical applications. The local algorithm's success is guaranteed with a probability of $\Omega(2\alpha - 1)$, suggesting that if a community is sufficiently coherent ($\alpha > 1/2$), it can be identified without global knowledge of the network.

Limitations and Future Work

While this framework offers a significant leap in tractability, challenges remain:

  • The $\alpha > 1/2$ Threshold: Current local algorithms require members to receive votes from more than half of their community. Lowering this threshold while maintaining efficiency is a priority.
  • Lifting Selection: While various methods (PageRank, Effective Resistance) can lift a graph into an affinity system, a definitive guide on which method suits specific data types (e.g., biological vs. social) is still needed.
  • Multi-Facet Complexity: Real-world relationships are multi-faceted (e.g., professional vs. social affinities). Simplifying the computational overhead for these multi-view communities remains an open research challenge.

Summary updated

Abstract

A central problem in e-commerce is determining overlapping communities among individuals or objects in the absence of external identification or tagging. We address this problem by introducing a framework that captures the notion of communities or clusters determined by the relative affinities among their members. To this end we define what we call an affinity system, which is a set of elements, each with a vector characterizing its preference for all other elements in the set. We define a natural notion of (potentially overlapping) communities in an affinity system, in which the members of a given community collectively prefer each other to anyone else outside the community. Thus these communities are endogenously formed in the affinity system and are "self-determined" or "self-certified" by its members. We provide a tight polynomial bound on the number of self-determined communities as a function of the robustness of the community. We present a polynomial-time algorithm for enumerating these communities. Moreover, we obtain a local algorithm with a strong stochastic performance guarantee that can find a community in time nearly linear in the of size the community. Social networks fit particularly naturally within the affinity system framework -- if we can appropriately extract the affinities from the relatively sparse yet rich information from social networks, our analysis then yields a set of efficient algorithms for enumerating self-determined communities in social networks. In the context of social networks we also connect our analysis with results about $(\alpha,\beta)$-clusters introduced by Mishra, Schreiber, Stanton, and Tarjan \cite{msst}. In contrast with the polynomial bound we prove on the number of communities in the affinity system model, we show that there exists a family of networks with superpolynomial number of $(\alpha,\beta)$-clusters.
BibTeX
@inproceedings{balcan2013i,
  author = {Maria-Florina Balcan and Christian Borgs and Mark Braverman and Jennifer T. Chayes and Shang-Hua Teng},
  title = {{I Like Her more than You: Self-determined Communities}},
  booktitle = {SODA},
  year = {2013},
  doi = {10.1137/1.9781611973105.55},
}
Figure