Finding Endogenously Formed Communities

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

Abstract

Identifying overlapping communities in large-scale networks—such as e-commerce platforms or social media—is a fundamental challenge, especially when external tags or categories are absent. This paper introduces the Affinity System framework, which models communities based on the internal preferences of their members rather than global graph metrics. By defining "self-determined" communities where members collectively prefer each other over outsiders, the authors establish a polynomial bound on the number of such communities and provide efficient algorithms for their discovery.

Introduction

In modern digital ecosystems, individuals rarely belong to a single, discrete group. A user might simultaneously belong to communities defined by professional interests, hobbies, and geographic locations. Traditional clustering methods often struggle with these overlaps or rely on external metadata that may be sparse or unavailable. Furthermore, existing mathematical definitions, such as $(\alpha, \beta)$-clusters, often suffer from a "combinatorial explosion," resulting in a superpolynomial number of potential communities that are computationally impossible to enumerate.

This research addresses these challenges by focusing on endogenously formed communities. These are groups that exist because the members themselves "certify" their belonging through mutual affinity, rather than being forced into a cluster by a global algorithm.

The Affinity System Model

The core of this framework is the Affinity System, where every element in a set maintains a ranked list of preferences for all other elements. A subset $S$ is considered a "self-determined community" based on three parameters $(\theta, \alpha, \beta)$:

  1. Voting: Members cast "votes" for their top $\theta|S|$ preferences.
  2. Internal Density ($\alpha$): Every member of the community receives a high fraction of votes from fellow members.
  3. External Sparsity ($\beta$): Individuals outside the community receive very few votes from the members.

This "self-certification" captures the intuition that a community is a group that agrees on its own boundaries. By limiting the number of votes a member can cast relative to the community size, the model avoids the mathematical explosion of possible groups, making the problem computationally tractable.

Algorithmic Framework

The authors propose two primary algorithmic approaches to identify these communities:

Global Enumeration

The paper provides a multi-stage algorithm capable of finding all self-determined communities in polynomial time. This is a significant theoretical advancement over previous models where the number of potential clusters could be superpolynomial.

For "internet-scale" data where processing the entire network is unfeasible, the authors introduce a "seed-based" local algorithm. Given a single member $v$, the algorithm can reconstruct $v$’s community in time nearly linear to the size of the community ($O(t \log t)$), rather than the size of the entire network. This is particularly effective when the community is robust (e.g., $\alpha > 1/2$).

Lifting Sparse Networks

To apply this dense model to sparse social networks, the authors describe "lifting" techniques. By using metrics like PageRank or Effective Resistance, a sparse graph can be transformed into a dense Affinity System, allowing the proposed algorithms to function on standard network data.

Theoretical Results and Complexity

The paper establishes several key results:

  • Polynomial Bounds: The paper proves there are at most $n^{O(1)}$ self-determined communities in any affinity system, ensuring that enumeration is always feasible.
  • Hardness Contrast: The authors demonstrate that while finding $(\alpha, \beta)$-clusters is as difficult as the "Hidden Clique" problem, finding self-determined communities remains efficient.
  • Stochastic Guarantees: The local algorithm comes with strong performance guarantees, proving that a "good seed" is sufficient to identify a robust community efficiently.

Conclusion and Future Work

The Affinity System framework provides a mathematically rigorous and computationally efficient way to handle overlapping communities. While the theoretical foundations are robust, practical application requires careful tuning of the $\theta, \alpha,$ and $\beta$ parameters. Future work involves empirical validation on large-scale e-commerce datasets, such as retail product logs or citation networks, to refine the model for real-world noise and varying community densities.

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 $(α,β)$-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 $(α,β)$-clusters.
BibTeX
@inproceedings{balcan2013finding,
  author = {Maria-Florina Balcan and Christian Borgs and Mark Braverman and Jennifer Chayes and Shang‐Hua Teng},
  title = {{Finding Endogenously Formed Communities}},
  booktitle = {SODA},
  year = {2013},
  doi = {10.1137/1.9781611973105.55},
}
Figure