An Axiomatic Approach to Community Detection

Inspired by social choice theory in voting and other contexts [2], we provide the first axiomatic approach to community identication in social and information networks. We start from an abstract framework, called preference networks [3], which, for each member, gives their ranking of all the other members of the network. This preference model enables us to focus on the fundamental conceptual question: What constitutes a community in a social network? Within this framework, we axiomatically study the formation and structures of communities in two different ways. First, we apply social choice theory and define communities indirectly by postulating that they are fixed points of a preference aggregation function obeying certain desirable axioms. Second, we directly postulate six desirable axioms for communities to satisfy, without reference to preference aggregation. For the second approach, we prove a taxonomy theorem that provides a structural characterization of the family of axiom-conforming community rules as a lattice. We complement this structural theorem with a complexity result, showing that, while for some rules in the lattice, community characterization is straightforward, it is coNPcomplete to characterize subsets according to others. Our study also sheds light on the limitations of defining community rules solely based on preference aggregation, namely that many aggregation functions lead to communities which violate at least one of our community axioms. These include any aggregation function satisfying Arrow’s \independence of irrelevant alternatives” axiom, as well as commonly used aggregation schemes like the Borda count or generalizations thereof. Finally, we give a polynomial-time rule consistent with five axioms and weakly satisfying the sixth axiom.