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)$:
- Voting: Members cast "votes" for their top $\theta|S|$ preferences.
- Internal Density ($\alpha$): Every member of the community receives a high fraction of votes from fellow members.
- 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.
Local Search
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