An Axiomatic Approach to Community Detection
An Axiomatic Approach to Community Detection
复制标题
社区检测的公理方法
DOI：
10.1145/2840728.2840748
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
S. Teng
中科院分区：
文献类型：
--
作者：
C. Borgs;J. Chayes;Adrian Marple;S. Teng
受投票和其他背景下的社会选择理论的启发，我们提供了社会网络中社区认同的第一个公理化方法。我们从一个抽象的框架开始，称为偏好网络，对于每个成员，给出他们对网络中所有其他成员的排名。这种完全信息偏好模型使我们能够关注基本的概念问题：社会网络中的社区是由什么构成的？在这个框架内，我们以两种不同的方式研究社区的形成和结构。首先，我们运用社会选择理论，通过假设社区是遵循某些理想公理的偏好聚合函数的不动点来间接定义社区。其次，我们直接假设了六个理想的公理，社区满足，没有参考偏好聚合。对于第二种方法，我们证明了一个分类定理，该定理提供了作为格的符合公理的群体规则族的美丽结构表征。我们用一个复杂度结果补充了这个结构定理，表明对于晶格中的某些规则，群体表征是直接的，而对于其他规则，子集的表征是conp完全的。我们的研究还揭示了仅仅基于偏好聚合来定义社区规则的局限性，即许多聚合函数导致的社区至少违反了我们的社区公理之一。这些包括任何满足阿罗“无关选择的独立性”公理的聚合函数，以及常用的聚合方案，如Borda计数或其推广。最后，给出了一个与五个公理相一致且弱满足第六个公理的多项式时间规则。
Inspired by social choice theory in voting and other contexts, we provide the first axiomatic approach to community identification in a social network. We start from an abstract framework, called preference networks, which, for each member, gives their ranking of all the other members of the network. This complete-information 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 define 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 beautiful 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 coNP-complete to characterize subsets according to others. Our study also sheds light on the limitations of defining 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.