Finding Endogenously Formed Communities

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

TL;DR

This paper introduces a novel framework called "affinity systems" to model and find "self-determined" communities within data, where members collectively prefer each other over outsiders. They develop efficient polynomial-time algorithms for finding these communities and prove bounds on their number, offering a more robust approach than existing methods for social network analysis and e-commerce.

What Problem Does This Paper Address?

In many real-world scenarios, like e-commerce or social networks, we need to identify groups of individuals or items that naturally belong together. This is challenging because these groups, or "communities," often overlap, and there's no pre-existing "ground truth" or labels to guide us. Traditional clustering methods often struggle with overlapping communities or require specific assumptions about community size or structure. The authors aim to address this by defining communities that are "endogenously formed" – meaning they arise organically from the relationships and preferences within the data itself, rather than being imposed by external criteria.

Methods

The core of the paper is the affinity system model. Here, each element (e.g., a person, a product) has a "preference vector" indicating its affinity for all other elements. Based on these preferences, they define self-determined communities: subsets of elements where members collectively prefer each other more than they prefer those outside the subset.

They introduce two main algorithmic contributions:

  1. Polynomial-time enumeration: An algorithm that can find all self-determined communities within an affinity system.
  2. Local community finding: A quasi-linear time algorithm that can find a community starting from a single "seed" element, which is crucial for large-scale networks where examining the entire dataset is infeasible.

They also extend their framework to handle weighted affinity systems (where preferences are numerical scores rather than just rankings) and multi-faceted affinity systems (where elements have multiple sets of preferences, e.g., for "fun" vs. "academic" interests).

Datasets

Not discussed in the paper. The paper focuses on theoretical frameworks and algorithms, using synthetic examples and general graph structures for analysis rather than specific real-world datasets.

Key Insights and Ideas

  • "Self-determined" communities are powerful: The idea that communities can be defined by internal preferences, making them "self-certified," is a key conceptual advance. This avoids relying on external labels or assumptions about community structure.
  • Affinity systems generalize many scenarios: The framework elegantly captures various data types, from social interactions to product preferences, by modeling them as preference vectors.
  • Local algorithms are essential for scale: The development of a local algorithm that finds communities efficiently without seeing the whole network is a significant practical contribution for analyzing massive datasets.
  • The number of communities can be bounded: Despite the potential for overlapping communities, they prove polynomial bounds on the number of self-determined communities under certain conditions, which is a strong theoretical result.
  • Distinction from (α, β)-clusters: While related, their notion of self-determined communities differs from existing (α, β)-clusters, particularly in how votes are aggregated, which allows for polynomial bounds on community numbers, unlike some superpolynomial bounds for (α, β)-clusters.

Key Results

  • A polynomial-time algorithm for enumerating all self-determined communities.
  • A local algorithm that finds a community in nearly linear time with respect to the community size, given a good seed.
  • A polynomial bound on the number of self-determined communities, specifically $n^{O(\log(1/\alpha)/\alpha)}$, which is polynomial in $n$ for constant $\alpha$.
  • The framework and algorithms are extended to weighted and multi-faceted affinity systems.
  • They show that finding (α, β)-clusters can be as hard as the hidden clique problem, highlighting the computational challenges in some related community detection tasks.

Limitations and Future Work

  • Seed selection for local algorithms: The local algorithm's success depends on starting with a "good seed" vertex. While they show how to find such seeds, it adds a layer of complexity.
  • Parameter sensitivity: The performance and bounds can depend on the chosen parameters ($\theta, \alpha, \beta$).
  • Computational complexity for multi-faceted systems: While they show it's not fundamentally harder, the complexity can increase multiplicatively with the number of facets.

The authors suggest future work in extending their local approach to weighted and multi-faceted affinity systems, and exploring applications in social network analysis and e-commerce. They also highlight the potential for their techniques to convert other polynomial-time clustering algorithms into local quasi-linear algorithms.

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 T. Chayes and Shang-Hua Teng},
  title = {{Finding Endogenously Formed Communities}},
  booktitle = {SODA},
  year = {2013},
  doi = {10.1137/1.9781611973105.55},
}

Loading related content...

Figure