Abstract
This paper establishes a formal axiomatic framework for defining communities in social networks by leveraging social choice theory. By conceptualizing a community as a fixed point of a preference aggregation function—where a group collectively "votes" for its own members—the authors provide a principled alternative to traditional structural heuristics. The study introduces eight fundamental axioms for community rules, proves a taxonomy theorem characterizing the mathematical structure of these rules as a bounded lattice, and explores the computational complexity and impossibility results inherent in preference-based community identification.
Introduction
In the field of network analysis, the definition of a "community" has long been a subject of debate. Most existing methodologies rely on structural heuristics, such as identifying clusters with higher edge density internally than externally. While computationally useful, these methods often lack a rigorous theoretical foundation. This paper addresses this gap by asking a fundamental question: If we knew the individual preferences of every member in a network, what mathematical properties must a group satisfy to be considered a stable and fair community?
By framing community identification as a problem of social choice—the mathematics of voting and preference aggregation—the authors move beyond simple edge-counting toward a more principled understanding of social cohesion. They propose that a community is essentially a "fixed point" where the collective preference of the group reinforces its own membership.
Methodology: Preference Networks and Fixed Points
The researchers introduce the concept of Preference Networks, where every member of a set $V$ provides a total ranking of all other members. Within this framework, they explore two complementary paths for defining communities:
1. The Fixed-Point Approach
A community is defined as a subset $S$ that, when its members' preferences are combined using an aggregation function (a voting rule), ranks the members of $S$ as the top $|S|$ candidates. In this model, a community is a group that "votes itself into power."
2. The Axiomatic Approach
To ensure these rules behave logically, the authors propose eight "desirable" axioms that any community rule should satisfy. Key axioms include:
- Group Stability: No subgroup within the community can be replaced by outsiders that the rest of the community collectively prefers.
- Self-Approval: The group must collectively prefer its own members over any other group of the same size.
- Monotonicity: If a community member's rank is improved in the individual preferences of others, the group should remain a community.
- Embedding: A community identified in a small network should remain a community if that network is embedded into a larger one, provided the members' relative preferences for each other remain high.
Key Insights and The Taxonomy Theorem
One of the paper's central contributions is the Taxonomy Theorem. The authors prove that the set of all community rules satisfying their eight axioms forms a bounded lattice. This mathematical structure implies that there is a hierarchy of rules ranging from the "most selective" (the Clique Rule) to the "most comprehensive" (the Comprehensive Rule). Every other valid rule sits between these two extremes, providing a complete map of possible community definitions under this axiomatic framework.
The "Arrogant Member" Problem
The research reveals a surprising tension between traditional social choice and community stability. Many standard voting systems, such as the Borda count or any system satisfying Arrow’s "Independence of Irrelevant Alternatives" (IIA), fail as community rules. For instance, a single "arrogant" member who ranks outsiders very highly can prevent a cohesive group from being recognized as a community under traditional rules. This suggests that community identification requires a different logic than standard democratic voting.
Results and Computational Complexity
The paper highlights a significant divide in the computational effort required to identify communities:
- The Clique Rule: Identifying communities under this strict rule is computationally straightforward and can be achieved in polynomial time.
- The Comprehensive Rule: Deciding if a subset satisfies the most inclusive rule is coNP-complete, indicating a high level of computational difficulty.
Furthermore, the authors provide an impossibility result: no fixed-point rule based on an aggregation function satisfying Arrow's IIA can satisfy all eight community axioms. This formalizes the inherent difficulty in balancing individual preference consistency with collective group stability.
Conclusion and Future Work
While this paper provides a robust theoretical foundation, it acknowledges a primary limitation: the model assumes complete preference information, where every member has a total ranking of everyone else. Real-world social networks are typically sparse, with many missing links and unknown preferences.
The authors suggest that this axiomatic framework serves as a necessary first step toward more practical applications, such as inferring missing links in sparse data or developing algorithms for overlapping communities. By bridging the gap between social choice theory and network science, this work offers a new lens through which to view the fundamental nature of human association.
Summary updated