Fast Heuristic Algorithm for Multi-scale Hierarchical Community Detection
Fast Heuristic Algorithm for Multi-scale Hierarchical Community Detection
复制标题
DOI：
10.1145/3110025.3110125
复制
发表时间：
2017-07
期刊：
影响因子：
--
通讯作者：
Eduar Castrillo;Elizabeth León Guzman;Jonatan Gómez
中科院分区：
文献类型：
--
作者：
Eduar Castrillo;Elizabeth León Guzman;Jonatan Gómez
复杂网络构成了许多复杂系统的主干，例如社会网络。在复杂网络中检测社区结构是一项具有挑战性且计算代价昂贵的任务。本文提出了一种基于聚类分层聚类技术的多尺度分层社区快速启发式检测算法HAMUHI-CODE。我们在经典余弦相似度的基础上定义了一种新的顶点结构相似度，通过去除一些顶点来提高识别聚类间边缘的概率。然后，我们将提出的结构相似度用于一种新的聚类分层算法中，该算法不像经典方法那样只合并具有最大相似度的聚类，而是将任何不符合参数化社区定义的聚类与其最相似的相邻聚类合并。该算法同时计算所有相似的聚类，并检查每个聚类是否满足参数化的群体定义。它是在线性时间复杂度下完成的，就迭代中的簇的数量而言。由于复杂网络是一个稀疏图，我们的方法HAMUHI-CODE在最坏情况下（如果集群成对合并）的输入大小方面具有超线性时间复杂度，使其适合应用于大规模复杂网络。为了测试我们算法的特性和效率，我们在现实世界和合成基准网络上进行了广泛的实验，将其与几种最先进的基线算法进行了比较。
Complex networks constitute the backbones of many complex systems such as social networks. Detecting the community structure in a complex network is both a challenging and a computationally expensive task. In this paper, we present the HAMUHI-CODE, a novel fast heuristic algorithm for multiscale hierarchical community detection inspired on an agglomerative hierarchical clustering technique. We define a new structural similarity of vertices based on the classical cosine similarity by removing some vertices in order to increase the probability of identifying inter-cluster edges. Then we use the proposed structural similarity in a new agglomerative hierarchical algorithm that does not merge only clusters with maximal similarity as in the classical approach, but merges any cluster that does not meet a parameterized community definition with its most similar adjacent cluster. The algorithm computes all the similar clusters at the same time is checking if each cluster meets the parameterized community definition. It is done in linear time complexity in terms of the number of cluster in the iteration. Since a complex network is a sparse graph, our approach HAMUHI-CODE has a super-linear time complexity with respect to the size of the input in the worst-case scenario (if the clusters merge in pairs), making it suitable to be applied on large-scale complex networks. To test the properties and the efficiency of our algorithm we have conducted extensive experiments on real world and synthetic benchmark networks by comparing it to several baseline state-of-the-art algorithms.