基于共邻节点相似度的加权网络社区发现方法
|
摘要
为实现加权网络的准确划分,发现真实的社区结构,提出一种基于模块度和共邻节点相似性的层次聚类社区划分方法IEM.首先,定义两节点间基于共邻节点的相似度.之后,基于该度量快速聚合当前节点和与其关联紧密度最强的邻居节点以形成初始社区,并进行社区扩展.最后,以最大化网络模块度为目标进行社区合并以优化划分结果.算法通过形成初始社区、扩展社区、合并社区三步,实现了加权网络合理有效的社区划分.以加权模块度作为社区划分质量的评价标准,在多个数据集上的实验结果表明,IEM算法优于加权CN、加权AA、加权RA.同时,与CRMA算法相比,IEM算法对加权网络社区划分的有效性和正确性更高.
In order to divide communities accurately in weighted networks,a hierarchical clustering method IEM based on the similarity and modularity is proposed.Firstly,the similarity of the two nodes is defined based on attributes of their common neighbors.Then,the most closely related nodes are clustered fastly according to their similarity to form the initial community and expand it.Lastly,these communities are merged with the goal of maxmizing the modularity so as to optimize division results.The algorithm achieves more reasonable and effective community division for weighted network by three steps of initializing,expanding and merging communities.Correctness and effectiveness of the algorithm are verified through experiments on many weighted networks using weighted modularity as evaluation index.Results show that IEM is superior to weighted CN,weighted AA and weighted RA.Moreover,it can achieve the higher quality of community division in weighted networks compared with CRMA algorithm.
In order to divide communities accurately in weighted networks,a hierarchical clustering method IEM based on the similarity and modularity is proposed.Firstly,the similarity of the two nodes is defined based on attributes of their common neighbors.Then,the most closely related nodes are clustered fastly according to their similarity to form the initial community and expand it.Lastly,these communities are merged with the goal of maxmizing the modularity so as to optimize division results.The algorithm achieves more reasonable and effective community division for weighted network by three steps of initializing,expanding and merging communities.Correctness and effectiveness of the algorithm are verified through experiments on many weighted networks using weighted modularity as evaluation index.Results show that IEM is superior to weighted CN,weighted AA and weighted RA.Moreover,it can achieve the higher quality of community division in weighted networks compared with CRMA algorithm.
引文
[1]Newman M E J.Analysis of weighted networks[J].Phys Rev E,2004,70:56133.
[2]任迎伟,李静.创业过程组织社会网络动态演进机理研究[J].四川大学学报:哲学社会科学版,2013,188:104.
[3]郭崇慧,张娜.基于共邻矩阵的复杂网络社区结构划分方法[J].系统工程理论与实践,2010,30:1077.
[4]Jaho E,Karaliopoulos M,Stavrakakis I.ISCoDe:a framework for interest similarity-based community detection in social networks[C]//Proceedings of2011IEEE Conference on Computer Communications Workshops.Shanghai,China:IEEE INFO-COM,2011.
[5]Subramani K,Velkov A,Ntoutsi I,et al.Densitybased community detection in social networks[C]//Proceedings of 2011IEEE 5th International Conference on Internet Multimedia Systems Architecture and Application.Bangalore,India:IEEE IMSAA,2011.
[6]Liu R F,Feng S,Shi R S,et al.Weighted graph clustering for community detection of large social networks[J].Procedia Comput Sci,2014,31:85.
[7]Sharma T.Finding communities in weighted signed social networks[C]//Proceedings of IEEE/ACMInternational Conference on Advances in Social Networks Analysis and Mining.Istanbul,Turkey:IEEE ASONAM,2012.
[8]Lu Z,Wen Y,Cao G.Community detection in weighted networks:algorithms and applications[C]//Proceedings of 2013 IEEE International Conference on Pervasive Computing and Communications.San Dieg:IEEE,2013,26:179.
[9]Han H,Wang J,Wang H.A new algorithm to detect community structures on weighted network[C]//Proceedings of 2010International Conference on Computational Intelligence and Software Engineerin.Wuhan:IEEE,2010:1.
[10]王坤,吕光宏,梁召伟,等.基于相似度的加权复杂网络社区发现方法[J].四川大学学报:自然科学版,2014,51:1170.
[11]王佳嘉.动态复杂网络社区发现算法研究及应用[D].大连:大连理工大学,2014.
[12]Chen D,Shang M,Lv Z,et al.Detecting overlapping communities of weighted via a local algorithm[J].Phys Stat Mech Appl,2010,389:4177.
[13]林旺群,卢风顺,丁兆云,等.基于带权图的层次化社区并行计算方法[J].软件学报,2012,3:1517.
[14]王书凯.基于交互模块度的带权图网络社区发现[D].昆明:云南大学,2014.
[15]詹培森.加权复杂网络的局部社区发现算法并行化研究与实现[D].广州:华南理工大学,2013.
[16]姚宏亮,罗明伟,李俊照,等.复合加权股票网络的活跃性层次聚类[J].计算机科学与探索,2014,8:207.
[17]Saha T,Domeniconi C,Rangwala H.Detection of communities and bridges in weighted networks[C]//Proceedings of Machine Learning&Data Mining in Pattern Recognition.New York,USA:Petra Perner,2011.
[18]赵健,安健.群智感知服务中一种面向有向加权网络的社区发现算法[J].计算机应用研究,2014,31:3795.
[19]季大祥.社交网络中的社团发现与度量研究[D].济南:山东大学,2014.
[20]姚尊强.加权复杂网络的分析和预测[D].青岛:青岛理工大学,2012.
[21]Guo J F,Liu M M,Liu L L,et al.An improved community discovery algorithm in weighted social networks[J].ICIC Express Lett,2016,10:35.
[22]Yang B,Liu J M.An autonomy oriented computing approach to distributed network community mining[C]//Proceedings of the First International Conference on Self-Adaptive and Self-Organizing Systems.Boston,USA:IEEE SASO,2007.
[23]刘旭.基于目标函数优化的复杂网络社区结构发现[D].长沙:国防科技大学,2012.
[2]任迎伟,李静.创业过程组织社会网络动态演进机理研究[J].四川大学学报:哲学社会科学版,2013,188:104.
[3]郭崇慧,张娜.基于共邻矩阵的复杂网络社区结构划分方法[J].系统工程理论与实践,2010,30:1077.
[4]Jaho E,Karaliopoulos M,Stavrakakis I.ISCoDe:a framework for interest similarity-based community detection in social networks[C]//Proceedings of2011IEEE Conference on Computer Communications Workshops.Shanghai,China:IEEE INFO-COM,2011.
[5]Subramani K,Velkov A,Ntoutsi I,et al.Densitybased community detection in social networks[C]//Proceedings of 2011IEEE 5th International Conference on Internet Multimedia Systems Architecture and Application.Bangalore,India:IEEE IMSAA,2011.
[6]Liu R F,Feng S,Shi R S,et al.Weighted graph clustering for community detection of large social networks[J].Procedia Comput Sci,2014,31:85.
[7]Sharma T.Finding communities in weighted signed social networks[C]//Proceedings of IEEE/ACMInternational Conference on Advances in Social Networks Analysis and Mining.Istanbul,Turkey:IEEE ASONAM,2012.
[8]Lu Z,Wen Y,Cao G.Community detection in weighted networks:algorithms and applications[C]//Proceedings of 2013 IEEE International Conference on Pervasive Computing and Communications.San Dieg:IEEE,2013,26:179.
[9]Han H,Wang J,Wang H.A new algorithm to detect community structures on weighted network[C]//Proceedings of 2010International Conference on Computational Intelligence and Software Engineerin.Wuhan:IEEE,2010:1.
[10]王坤,吕光宏,梁召伟,等.基于相似度的加权复杂网络社区发现方法[J].四川大学学报:自然科学版,2014,51:1170.
[11]王佳嘉.动态复杂网络社区发现算法研究及应用[D].大连:大连理工大学,2014.
[12]Chen D,Shang M,Lv Z,et al.Detecting overlapping communities of weighted via a local algorithm[J].Phys Stat Mech Appl,2010,389:4177.
[13]林旺群,卢风顺,丁兆云,等.基于带权图的层次化社区并行计算方法[J].软件学报,2012,3:1517.
[14]王书凯.基于交互模块度的带权图网络社区发现[D].昆明:云南大学,2014.
[15]詹培森.加权复杂网络的局部社区发现算法并行化研究与实现[D].广州:华南理工大学,2013.
[16]姚宏亮,罗明伟,李俊照,等.复合加权股票网络的活跃性层次聚类[J].计算机科学与探索,2014,8:207.
[17]Saha T,Domeniconi C,Rangwala H.Detection of communities and bridges in weighted networks[C]//Proceedings of Machine Learning&Data Mining in Pattern Recognition.New York,USA:Petra Perner,2011.
[18]赵健,安健.群智感知服务中一种面向有向加权网络的社区发现算法[J].计算机应用研究,2014,31:3795.
[19]季大祥.社交网络中的社团发现与度量研究[D].济南:山东大学,2014.
[20]姚尊强.加权复杂网络的分析和预测[D].青岛:青岛理工大学,2012.
[21]Guo J F,Liu M M,Liu L L,et al.An improved community discovery algorithm in weighted social networks[J].ICIC Express Lett,2016,10:35.
[22]Yang B,Liu J M.An autonomy oriented computing approach to distributed network community mining[C]//Proceedings of the First International Conference on Self-Adaptive and Self-Organizing Systems.Boston,USA:IEEE SASO,2007.
[23]刘旭.基于目标函数优化的复杂网络社区结构发现[D].长沙:国防科技大学,2012.