ESN中基于贪婪派系扩张的重叠社区发现
|
摘要
传统局部扩张方法在对企业社会化网络(ESN)中的重叠社区结构进行识别时,存在计算冗余与社区挖掘不彻底的问题。为此,提出一种基于贪婪派系扩张的重叠社区发现算法GFE。在原始ESN中寻找极大派系,根据派系间的关联程度计算其链接强度,将原始网络图转换成最大派系图。在最大化适应度函数的条件下,贪婪扩张最大派系图中的种子派系,以进行社区发现。在此基础上,比较社区差异度,合并近似重复的社区,从而优化重叠社区的层次结构。实验结果表明,GFE算法能有效发现ESN中的重叠社区结构,且运行效率高于CPM、LFM等算法。
There are problems of computational redundancy and incomplete community mining in traditional local expansion methods for identifying overlapping community structures in Enterprise Social Network(ESN).Therefore,an overlapping community discovery algorithm GFE based on greedy factional expansion is proposed.GFE algorithm searches for maximal factions in the original ESN,calculates their link strength according to the degree of association between factions,and converts the original network graph into the maximal faction graph.Under the condition of maximizing fitness function,the seed factions in the maximal faction graph are greedily expanded for community discovery.On this basis,the community differences are compared,and the similar duplicated communities are merged to optimize the hierarchical structure of overlapping community.Experimental results show that the GFE algorithm can effectively discover overlapping community structure in ESN,and the operation efficiency is higher than those of CPM, LFM and other algorithms.
There are problems of computational redundancy and incomplete community mining in traditional local expansion methods for identifying overlapping community structures in Enterprise Social Network(ESN).Therefore,an overlapping community discovery algorithm GFE based on greedy factional expansion is proposed.GFE algorithm searches for maximal factions in the original ESN,calculates their link strength according to the degree of association between factions,and converts the original network graph into the maximal faction graph.Under the condition of maximizing fitness function,the seed factions in the maximal faction graph are greedily expanded for community discovery.On this basis,the community differences are compared,and the similar duplicated communities are merged to optimize the hierarchical structure of overlapping community.Experimental results show that the GFE algorithm can effectively discover overlapping community structure in ESN,and the operation efficiency is higher than those of CPM, LFM and other algorithms.
引文
[1] BLONDEL V D,GUILLAUME J L,LAMBIOTTE R,et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics,2008(10):155-168.
[2] GUIMERà R,NUNES AMARAL L A.Functional carto-graphy of complex metabolic networks[J].Nature,2005,433(7028):895-900.
[3] 邓小龙,王柏,吴斌,等.基于信息熵的复杂网络社团划分建模和验证[J].计算机研究与发展,2012,49(4):725-734.
[4] SHANG Ronghua,BAI Jing,JIAO Licheng,et al.Commu-nity detection based on modularity and an improved genetic algorithm[J].Physica A:Statistical Mechanics and Its Applications,2013,392(5):1215-1231.
[5] LANCICHINETTI A,RADICCHI F,RAMASCO J J,et al.Finding statistically significant communities in networks[J].PLoS One,2011,6(4):e18961.
[6] LANCICHINETTI A,FORTUNATO S,KERTéSZ J.Detecting the overlapping and hierarchical community structure of complex networks[J].New Journal of Physics,2009,11(3):19-44.
[7] LEE C,REID F,MCDAID A,et al.Detecting highly overlapping community structure by greedy clique expansion[EB/OL].[2018-07-25].https://arxiv.org/pdf/1002.1827.pdf.
[8] 潘磊,金杰,王崇骏,等.社会网络中基于局部信息的边社区挖掘[J].电子学报,2012,40(11):2255-2263.
[9] WU Zhihao,LIN Youfang,GREGORY S,et al.Balanced multi-label propagation for overlapping community detection in social networks[J].Journal of Computer Sciences and Technology,2012,27(3):468-479.
[10] 刘世超,朱福喜,甘琳.基于标签传播概率的重叠社区发现算法[J].计算机学报,2016,39(4):717-729.
[11] 顾军华,霍士杰,王守彬,等.基于节点中心性和社区相似性的快速标签传播算法[J].计算机应用,2018,38(5):1320-1326.
[12] AHN Y Y,BAGROW J P,LEHMAN S.Link communities reveal multiscale complexity in networks[J].Nature,2010,466(7307):761-764.
[13] KIM Y,JEONG H.Map equation for link communities[J].Physical Review E,2011,84(2):026110.
[14] 朱牧,孟凡荣,周勇.基于链接密度聚类的重叠社区发现算法[J].计算机研究与发展,2013,50(12):2520-2530.
[15] 贺超波,汤庸,刘海,等.一种集成链接和属性信息的社区挖掘方法[J].计算机学报,2017,40(3):601-616.
[16] WEN Xuyun,CHEN Weineng,LIN Ying,et al.A maximal clique based multiobjective evolutionary algorithm for overlapping community detection[J].IEEE Transactions on Evolutionary Computation,2017,21(3):363-377.
[17] KANNAN R,ISHTEVA M,PARK H.Bounded matrix factorization for recommender system[J].Knowledge and Information Systems,2014,39(3):491-511.
[18] 吴松强,孙波,王路.集群中核心企业网络权力对配套企业合作行为的影响——关系资本的调节效应[J].科技进步与对策,2017,34(13):81-88.
[19] RADICCHI F,CASTELLANO C,CECCONI F,et al.Defining and identifying communities in networks[J].Proceedings of the National Academy of Sciences of the United States of America,2004,101(9):2658-2663.
[20] PALLA G,DERENYI I,FARKAS I,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814-818.
[21] WANG Jianxin,LI Min,CHEN Jianer,et al.A fast hierarchical clustering algorithm for functional modules discovery in protein interaction networks[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics,2011,8(3):607-620.
[22] XIE Jierui,SZYMANSKI B K,LIU Xiaoming.SLPA:uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process[C]//Proceedings of IEEE International Conference on Data Mining Workshops.Washington D.C.,USA:IEEE Computer Society,2011:344-349.
[23] LANCICHINETTI A,FORTUNATO S,RADICCHI F.Benchmark graphs for testing community detection algorithms[J].Physical Review E,2008,78(4):046110.
[24] ZHANG Pan.Evaluating accuracy of community detection using the relative normalized mutual information[EB/OL].[2018-07-25].https://arxiv.org/pdf/1501.03844.pdf.
[25] GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America,2002,99(12):7821-7826.
[26] LUSSEAU D.The emergent properties of a Dolphin social network[EB/OL].[2018-07-25].https://arxiv.org/ftp/cond-mat/papers/0307/0307439.pdf.
[27] NEWMAN M E J.Finding community structure in networks using the eigenvectors of matrices[J].Physical Review E,2006,74(3):036104.
[28] NELSON D L,MCEVOY C L,SCHREIBER T A.The university of south Florida free association,rhyme,and word fragment norms[J].Behavior Research Methods Instruments and Computers,2004,36(3):402-407.
[2] GUIMERà R,NUNES AMARAL L A.Functional carto-graphy of complex metabolic networks[J].Nature,2005,433(7028):895-900.
[3] 邓小龙,王柏,吴斌,等.基于信息熵的复杂网络社团划分建模和验证[J].计算机研究与发展,2012,49(4):725-734.
[4] SHANG Ronghua,BAI Jing,JIAO Licheng,et al.Commu-nity detection based on modularity and an improved genetic algorithm[J].Physica A:Statistical Mechanics and Its Applications,2013,392(5):1215-1231.
[5] LANCICHINETTI A,RADICCHI F,RAMASCO J J,et al.Finding statistically significant communities in networks[J].PLoS One,2011,6(4):e18961.
[6] LANCICHINETTI A,FORTUNATO S,KERTéSZ J.Detecting the overlapping and hierarchical community structure of complex networks[J].New Journal of Physics,2009,11(3):19-44.
[7] LEE C,REID F,MCDAID A,et al.Detecting highly overlapping community structure by greedy clique expansion[EB/OL].[2018-07-25].https://arxiv.org/pdf/1002.1827.pdf.
[8] 潘磊,金杰,王崇骏,等.社会网络中基于局部信息的边社区挖掘[J].电子学报,2012,40(11):2255-2263.
[9] WU Zhihao,LIN Youfang,GREGORY S,et al.Balanced multi-label propagation for overlapping community detection in social networks[J].Journal of Computer Sciences and Technology,2012,27(3):468-479.
[10] 刘世超,朱福喜,甘琳.基于标签传播概率的重叠社区发现算法[J].计算机学报,2016,39(4):717-729.
[11] 顾军华,霍士杰,王守彬,等.基于节点中心性和社区相似性的快速标签传播算法[J].计算机应用,2018,38(5):1320-1326.
[12] AHN Y Y,BAGROW J P,LEHMAN S.Link communities reveal multiscale complexity in networks[J].Nature,2010,466(7307):761-764.
[13] KIM Y,JEONG H.Map equation for link communities[J].Physical Review E,2011,84(2):026110.
[14] 朱牧,孟凡荣,周勇.基于链接密度聚类的重叠社区发现算法[J].计算机研究与发展,2013,50(12):2520-2530.
[15] 贺超波,汤庸,刘海,等.一种集成链接和属性信息的社区挖掘方法[J].计算机学报,2017,40(3):601-616.
[16] WEN Xuyun,CHEN Weineng,LIN Ying,et al.A maximal clique based multiobjective evolutionary algorithm for overlapping community detection[J].IEEE Transactions on Evolutionary Computation,2017,21(3):363-377.
[17] KANNAN R,ISHTEVA M,PARK H.Bounded matrix factorization for recommender system[J].Knowledge and Information Systems,2014,39(3):491-511.
[18] 吴松强,孙波,王路.集群中核心企业网络权力对配套企业合作行为的影响——关系资本的调节效应[J].科技进步与对策,2017,34(13):81-88.
[19] RADICCHI F,CASTELLANO C,CECCONI F,et al.Defining and identifying communities in networks[J].Proceedings of the National Academy of Sciences of the United States of America,2004,101(9):2658-2663.
[20] PALLA G,DERENYI I,FARKAS I,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814-818.
[21] WANG Jianxin,LI Min,CHEN Jianer,et al.A fast hierarchical clustering algorithm for functional modules discovery in protein interaction networks[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics,2011,8(3):607-620.
[22] XIE Jierui,SZYMANSKI B K,LIU Xiaoming.SLPA:uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process[C]//Proceedings of IEEE International Conference on Data Mining Workshops.Washington D.C.,USA:IEEE Computer Society,2011:344-349.
[23] LANCICHINETTI A,FORTUNATO S,RADICCHI F.Benchmark graphs for testing community detection algorithms[J].Physical Review E,2008,78(4):046110.
[24] ZHANG Pan.Evaluating accuracy of community detection using the relative normalized mutual information[EB/OL].[2018-07-25].https://arxiv.org/pdf/1501.03844.pdf.
[25] GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America,2002,99(12):7821-7826.
[26] LUSSEAU D.The emergent properties of a Dolphin social network[EB/OL].[2018-07-25].https://arxiv.org/ftp/cond-mat/papers/0307/0307439.pdf.
[27] NEWMAN M E J.Finding community structure in networks using the eigenvectors of matrices[J].Physical Review E,2006,74(3):036104.
[28] NELSON D L,MCEVOY C L,SCHREIBER T A.The university of south Florida free association,rhyme,and word fragment norms[J].Behavior Research Methods Instruments and Computers,2004,36(3):402-407.