Communities in Preference Networks: Refined Axioms and Beyond

摘要

Borgs et al. [2016] investigated essential requirements for communities in preference networks. They defined six axioms on community functions, i.e., community detection rules. Though having elegant properties, the practicality of this axiomsystem is compromised by the intractability of checking twocritical axioms, so no nontrivial consistent community functionwas reported in [Borgs et al., 2016]. By adapting the two axioms in a natural way, we propose two new axioms that are efficiently-checkable. We show that most of the desirable properties of the original axiom system are preserved. More importantly, the new axioms provide a general approach to constructing consistent community functions. We further find a natural consistent community function that is also enumerable and samplable, answering an open problem in the literature.