  We provide the first social choice theory approach to the question of what
constitutes a community in a social network. Inspired by the classic
preferences models in social choice theory, we start from an abstract social
network framework, called preference networks; these consist of a finite set of
members where each member has a total-ranking preference of all members in the
set.
  Within this framework, we develop two complementary approaches to
axiomatically study the formation and structures of communities. (1) We apply
social choice theory and define communities indirectly by postulating that they
are fixed points of a preference aggregation function obeying certain desirable
axioms. (2) We directly postulate desirable axioms for communities without
reference to preference aggregation, leading to eight natural community axioms.
  These approaches allow us to formulate and analyze community rules. We prove
a taxonomy theorem that provides a structural characterization of the family of
community rules that satisfies all eight axioms. The structure is actually
quite beautiful: these community rules form a bounded lattice under the natural
intersection and union operations. Our structural theorem is complemented with
a complexity result: while identifying a community by the most selective rule
of the lattice is in P, deciding if a subset is a community by the most
comprehensive rule of the lattice is coNP-complete. Our studies also shed light
on the limitations of defining community rules solely based on preference
aggregation: any aggregation function satisfying Arrow's IIA axiom, or based on
commonly used aggregation schemes like the Borda count or generalizations
thereof, lead to communities which violate at least one of our community
axioms. Finally, we give a polynomial-time rule consistent with seven axioms
and weakly satisfying the eighth axiom.
