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:
- Voting: Every member of $S$ "votes" for their top $\theta|S|$ preferred individuals.
- Self-Determination: A group is considered a $(\theta, \alpha, \beta)$ self-determined community if:
- Internal Support ($\alpha$): Every member inside the group receives a high fraction of votes from their peers.
- 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