Representative community divisions of networks
Representative community divisions of networks
复制标题
DOI：
10.1038/s42005-022-00816-3
复制
发表时间：
2022-02-17
影响因子：
5.5
通讯作者：
Newman, M. E. J.
中科院分区：
文献类型：
--
作者：
Kirkley, Alec;Newman, M. E. J.
用于检测网络中的社区结构的方法通常旨在识别网络节点到社区的单个最佳划分，通常通过优化某些目标函数，但是在现实世界的应用中，可能存在具有接近全局最优的客观分数的许多竞争性分区，并且可以通过检查这样的高-而不是只看一个最优值。然而，这样的集合可能很难解释，因为它的大小很容易达到数百或数千个分区。在本文中，我们提出了一种方法来分析大型分区集，将它们分成组相似的分区，然后确定一个原型分区作为每个组的代表。由此产生的一组原型分区提供了一个简洁的，可解释的总结的形式和多样性的社区结构在任何网络。社区检测是网络数据分析中的一项常见任务，但目前大多数社区检测算法要么只提供单个分区，要么提供大量合理的分区，这两种算法都不能对可能的结构进行可解释的总结。在这里，作者提供了一个解决这个问题的算法的形式，基于最小描述长度的原则，确定最小集的原型，高度代表性的分区的网络，简洁地总结了似是而非的社区结构。
Methods for detecting community structure in networks typically aim to identify a single best partition of network nodes into communities, often by optimizing some objective function, but in real-world applications there may be many competitive partitions with objective scores close to the global optimum and one can obtain a more informative picture of the community structure by examining a representative set of such high-scoring partitions than by looking at just the single optimum. However, such a set can be difficult to interpret since its size can easily run to hundreds or thousands of partitions. In this paper we present a method for analyzing large partition sets by dividing them into groups of similar partitions and then identifying an archetypal partition as a representative of each group. The resulting set of archetypal partitions provides a succinct, interpretable summary of the form and variety of community structure in any network. We demonstrate the method on a range of example networks.Community detection is a common task in the analysis of network data but most current community detection algorithms provide either only a single partition or a very large number of plausible ones, neither of which gives an interpretable summary of the possible structures. Here the authors provide a solution to this problem, in the form of an algorithm based on the minimum description length principle that identifies minimal sets of archetypal, highly representative partitions of a network that succinctly summarize the plausible community structures.