基于边信任度的混合参数自适应重叠社区发现算法
|
摘要
网络中的社区结构有助于简化网络拓扑结构分析,揭示系统内部的规律,能够为信息推荐和信息传播控制提供有力的支撑.网络重叠社区结构与真实生活更加接近,但其分析较非重叠社区结构更加困难.因此,针对重叠社区发现问题,在对网络的边进行峰值聚类的基础上提出了一种基于边信任度的混合参数的自适应重叠社区发现算法.定义了网络边的邻居边集合及与其邻居边之间的信任度函数,通过信息传递获取边的总信息量,并且基于此引入混合参数的概念.基于k-means算法使用混合参数对网络中的边进行聚类,即将网络中的边划分为核心边集与非核心边集,每个核心边作为一个聚类中心.根据非核心边到核心边的距离将所有非核心边划分至距离其最近的聚类中心所在社区.再根据网络中边与节点的关系实现重叠节点发现,最终实现重叠社区的发现.该算法的优点是每条边通过独立地完成信息扩散找到社区的结构,相比于传统的峰值聚类算法,不需要人为设置相关参数,实现重叠社区的自适应发现.为验证算法的可行性,对算法复杂度进行了分析,并且使用两种社区划分评价指标——标准化互信息和模块度,分别在人工数据集及6种真实数据集上进行实验,通过与其他算法进行对比分析,实验结果表明该算法更具可行性和有效性.
The community structure in a network simplifies the analysis of the network topology,reveals the internal rules of the system,and provides strong support for information recommendation and information dissemination control. The overlapping community structure of the network is closer to real-life scenario,but its analysis is more difficult than the non-overlapping community. Therefore,to solve the overlapping community detection,based on the peak clustering,an adaptive overlapping community detection algorithm based on the mixing parameter with the trust degree of edge is proposed. In this study,the neighbor edge set of the network and the trust function between the edge and its neighbors are defined,and the total information of the edge is obtained through information transfer. Based on this concept,the concept of mixing parameters is introduced. Then,based on the k-means algorithm,clustering is performed using the mixed parameter,i.e.,the edges in the network are divided into a core edge set and a non-core edge set,and each core edge acts as a clustering center. According to the distance from the non-core edge to the core edge,the non-core edges are divided into the community of the nearest cluster center. According to the relation between edges and nodes in the network,overlapping node discovery is achieved. Ultimately the overlapping communities are detected. The advantage of this algorithm is that each edge finds the structure of the community by independently completing information transfer. Moreover,compared to the traditional peak clustering algorithm,the proposed algorithm does not need to set parameters;therefore,adaptive detection of overlapping communities is achieved. To verify the feasibility of our algorithm,the complexity of the algorithm is analyzed. The two evaluation indices of the community detection,normalized mutual information and modularity,are used to experiment on the artificial dataset and the six real datasets respectively. In comparison to other algorithms,the experimental results show that the proposed algorithm is more feasible and effective.
The community structure in a network simplifies the analysis of the network topology,reveals the internal rules of the system,and provides strong support for information recommendation and information dissemination control. The overlapping community structure of the network is closer to real-life scenario,but its analysis is more difficult than the non-overlapping community. Therefore,to solve the overlapping community detection,based on the peak clustering,an adaptive overlapping community detection algorithm based on the mixing parameter with the trust degree of edge is proposed. In this study,the neighbor edge set of the network and the trust function between the edge and its neighbors are defined,and the total information of the edge is obtained through information transfer. Based on this concept,the concept of mixing parameters is introduced. Then,based on the k-means algorithm,clustering is performed using the mixed parameter,i.e.,the edges in the network are divided into a core edge set and a non-core edge set,and each core edge acts as a clustering center. According to the distance from the non-core edge to the core edge,the non-core edges are divided into the community of the nearest cluster center. According to the relation between edges and nodes in the network,overlapping node discovery is achieved. Ultimately the overlapping communities are detected. The advantage of this algorithm is that each edge finds the structure of the community by independently completing information transfer. Moreover,compared to the traditional peak clustering algorithm,the proposed algorithm does not need to set parameters;therefore,adaptive detection of overlapping communities is achieved. To verify the feasibility of our algorithm,the complexity of the algorithm is analyzed. The two evaluation indices of the community detection,normalized mutual information and modularity,are used to experiment on the artificial dataset and the six real datasets respectively. In comparison to other algorithms,the experimental results show that the proposed algorithm is more feasible and effective.
引文
[1]Chen Y,Zhao P,Li P,et al.Finding communities by their centers[J].Scientific Reports,2016,6:24017-1-8.
[2]Huang L,Wang G,Wang Y,et al.A link density cluster ing algorithm based on automatically selecting density peaks for overlapping community detection[J].International Journal of Modern Physics B,2016,30(24):165-167.
[3]Zhou X,Liu Y,Zhang J,et al.An ant colony based algorithm for overlapping community detection in complex networks[J].Physica A Statistical Mechanics&Its Applications,2015,427:289-301.
[4]Ahn Y Y,Bagrow J P,Lehmann S.Link communities reveal multiscale complexity in networks[J].Nature,2010,466(7307):761-764.
[5]Shi C,Cai Y,Fu D,et al.A link clustering based over lapping community detection algorithm[J].Data&Knowledge Engineering,2013,87(9):394-404.
[6]Zhang X K,Tian X,Li Y N,et al.Label propagation algorithm based on edge clustering coefficient for community detection in complex networks[J].International Journal of Modern Physics B,2014,28(30):1450216-1-15.
[7]Hu Y,Li M,Zhang P,et al.Community detection by signaling on complex networks[J].Physical Review EStatistical Nonlinear&Soft Matter Physics,2008,78(2):016115.
[8]Clauset A,Newman M E,Moore C.Finding community structure in very large networks[J].Physical Review EStatistical Nonlinear&Soft Matter Physics,2004,70:066111-1-6.
[9]Danon L,Díazguilera A,Duch J,et al.Comparing community structure identification[J].Journal of Statistical Mechanics Theory&Experiment,2005,2005(9):09008-1-10.
[10]Nicosia V,Mangioni G,Carchiolo V,et al.Extending the definition of modularity to directed graphs with overlapping communities[J].Journal of Statistical Mechanics:Theory&Experiment,2009(3):3166-3168.
[11]Gregory S.Finding overlapping communities in networks by label propagation[J].New Journal of Physics,2010,12(10):2011-2024.
[12]Palla G,Derényi I,Farkas I,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814-818.
[13]Lancichinetti A,Fortunato S.Benchmarks for testing com munity detection algorithms on directed and weighted graphs with overlapping communities[J].Physical Review E Statistical Nonlinear&Soft Matter Physics,2009,80:016118-1-8.
[14]Zachary W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research,1977,33(4):452-473.
[15]Lusseau D.The emergent properties of a dolphin social network[J].Proceedings Biological Sciences,2003,270(Suppl 2):186-188.
[16]Girvan M,Newman M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.
[17]Newman M E J,Girvan M.Finding and evaluating community structure in networks[J].Physical Review EStatistical Nonlinear&Soft Matter Physics,2004,69(2):026113-1-15.
[18]Guimera R,Danon L,Diaz-Guilera A,et al.Selfsimilar community structure in a network of human interactions[J].Physical Review E,2003,68(6):065103.
[19]Bogu?áM,Pastor-Satorras R,Díaz-Guilera A,et al.Models of social networks based on social distance attacment[J].Physical Review E,2004,70(5):056122-1-8.
[2]Huang L,Wang G,Wang Y,et al.A link density cluster ing algorithm based on automatically selecting density peaks for overlapping community detection[J].International Journal of Modern Physics B,2016,30(24):165-167.
[3]Zhou X,Liu Y,Zhang J,et al.An ant colony based algorithm for overlapping community detection in complex networks[J].Physica A Statistical Mechanics&Its Applications,2015,427:289-301.
[4]Ahn Y Y,Bagrow J P,Lehmann S.Link communities reveal multiscale complexity in networks[J].Nature,2010,466(7307):761-764.
[5]Shi C,Cai Y,Fu D,et al.A link clustering based over lapping community detection algorithm[J].Data&Knowledge Engineering,2013,87(9):394-404.
[6]Zhang X K,Tian X,Li Y N,et al.Label propagation algorithm based on edge clustering coefficient for community detection in complex networks[J].International Journal of Modern Physics B,2014,28(30):1450216-1-15.
[7]Hu Y,Li M,Zhang P,et al.Community detection by signaling on complex networks[J].Physical Review EStatistical Nonlinear&Soft Matter Physics,2008,78(2):016115.
[8]Clauset A,Newman M E,Moore C.Finding community structure in very large networks[J].Physical Review EStatistical Nonlinear&Soft Matter Physics,2004,70:066111-1-6.
[9]Danon L,Díazguilera A,Duch J,et al.Comparing community structure identification[J].Journal of Statistical Mechanics Theory&Experiment,2005,2005(9):09008-1-10.
[10]Nicosia V,Mangioni G,Carchiolo V,et al.Extending the definition of modularity to directed graphs with overlapping communities[J].Journal of Statistical Mechanics:Theory&Experiment,2009(3):3166-3168.
[11]Gregory S.Finding overlapping communities in networks by label propagation[J].New Journal of Physics,2010,12(10):2011-2024.
[12]Palla G,Derényi I,Farkas I,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814-818.
[13]Lancichinetti A,Fortunato S.Benchmarks for testing com munity detection algorithms on directed and weighted graphs with overlapping communities[J].Physical Review E Statistical Nonlinear&Soft Matter Physics,2009,80:016118-1-8.
[14]Zachary W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research,1977,33(4):452-473.
[15]Lusseau D.The emergent properties of a dolphin social network[J].Proceedings Biological Sciences,2003,270(Suppl 2):186-188.
[16]Girvan M,Newman M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.
[17]Newman M E J,Girvan M.Finding and evaluating community structure in networks[J].Physical Review EStatistical Nonlinear&Soft Matter Physics,2004,69(2):026113-1-15.
[18]Guimera R,Danon L,Diaz-Guilera A,et al.Selfsimilar community structure in a network of human interactions[J].Physical Review E,2003,68(6):065103.
[19]Bogu?áM,Pastor-Satorras R,Díaz-Guilera A,et al.Models of social networks based on social distance attacment[J].Physical Review E,2004,70(5):056122-1-8.