Clusters or communities can provide a coarse-grained description of complex systems at multiple scales, but their detection remains challenging in practice. Community detection methods often define communities as dense subgraphs, or subgraphs with few connections in-between, via concepts such as the cut, conductance, or modularity. Here we consider another perspective built on the notion of local dominance, where low-degree nodes are assigned to the basin of influence of high-degree nodes, and design an efficient algorithm based on local information. Local dominance gives rises to community centers, and uncovers local hierarchies in the network. Community centers have a larger degree than their neighbors and are sufficiently distant from other centers. The strength of our framework is demonstrated on synthesized and empirical networks with ground-truth community labels. The notion of local dominance and the associated asymmetric relations between nodes are not restricted to community detection, and can be utilised in clustering problems, as we illustrate on networks derived from vector data.
翻译:群集或社区可以提供多种规模的复杂系统的粗略描述,但发现这些系统仍具有实际挑战性。社区探测方法往往通过切割、导演或模块化等概念,将社区定义为密集的子集,或彼此之间联系很少的子集。这里我们考虑基于地方主导概念的另一个观点,即将低度节点指定给高度节点影响盆地,并根据当地信息设计一种高效的算法。地方主导产生社区中心,发现网络中的当地等级。社区中心比其邻居大,距离其他中心很远。我们框架的强弱表现在带有地面真相社区标签的合成和实证网络上。地方主导概念和节点之间相关的不对称关系不局限于社区探测,可以在集群问题上加以利用,正如我们从病媒数据产生的网络所说明的那样。