基于商空间的多层粒化社区发现方法

南京大学学报(自然科学版) ›› 2017, Vol. 53 ›› Issue (4): 764–.

基于商空间的多层粒化社区发现方法

段　震1，2，闵　星1，2，王倩倩2，3，陈　洁1，2，张燕平1，2，赵　姝1，2*

出版日期:2017-08-02 发布日期:2017-08-02
作者简介: 1.安徽大学计算机科学与技术学院，合肥，230601；2.安徽大学协同创新中心，合肥，230601；3．安徽大学国际商学院，合肥，230012
基金资助:
基金项目：国家自然科学基金(61402006，61602003)，安徽省自然科学基金(1508085MF113，1708085QF156，1708085MF163)，安徽省高等学校省级自然科学基金重点项目(KJ2016A016)，教育部留学回国人员科研启动基金(第49批)
收稿日期：2017－06－09
*通讯联系人，E－mail：zhaoshuzs2002@hotmail.com

Multilayer granulation community detection method based on quotient space

Duan Zhen1，2，Min Xing1，2，Wang Qianqian2，3，Chen Jie1，2，Zhang Yanping1，2，Zhao Shu1，2*

Online:2017-08-02 Published:2017-08-02
About author: 1.School of Computer Science and Technology，Anhui University，Hefei，230601，China；
2．Center of Information Support and Assurance Technology，Anhui University，Hefei，230601，China；
3．School of Business，Anhui University，Hefei，230012，China

摘要/Abstract

摘要： 社区发现旨在挖掘复杂网络的社区结构，现有的社区发现方法普遍存在着划分速度和精度不均衡的问题．商空间理论是一种粒度计算理论，通过粒度变换来降低问题求解复杂度，同时保持问题求解精度．提出一种基于商空间的多层粒化社区发现方法(multilayer granulation community detection method based on quotient space，MGQS)．该方法首先通过快速粒化操作对复杂网络进行多层次粒化，形成逐层粒化、逐层抽象的多粒度商空间，再依据所求问题选择最佳粒层作为最终划分结果．在公用数据集上的系列实验结果表明，相比于其他算法，该方法既能快速划分不同类型和规模的网络，也能获取多粒度的社区结构并根据所求问题选择最佳粒层，取得较高的模块度值和NMI值．

Abstract: Community detection aims at mining the community structures of complex networks.The existing community detection methods don’t have a tradeoff between speed and accuracy.In order to reduce the complexity of problem and hold the accuracy of results，the quotient space theory is introduced in this paper.Quotient space theory is one of the granular computing theories in which different granular spaces can be transformed for problem solving.A method based on quotient space，named MGQS(multilayer granulation community detection method based on quotient space)，is proposed for multilayer granulation community detection.Firstly，fast granulation operation for network is given.Fast granulation operation includes discourse domain(refers to node in the network)granulation and structure(refers to edge in the network)granulation.The complex network is granulated into different granular networks from thin to coarse，and a multi－granularity quotient space with layer by layer granulation and layer by layer abstraction is formed.Then，according to the object of problem，the optimal granular layer is selected as the final results.Compared to other algorithms，the results of a series of experiments on the public data sets show that，the proposed method MGQS not only can quickly partition the network of different types and scale，but also can obtain the multi－granularity community structure.The optimal granular layer，higher modularity and NMI values can be obtained according to the object of problem.

段　震1，2，闵　星1，2，王倩倩2，3，陈　洁1，2，张燕平1，2，赵　姝1，2*. 基于商空间的多层粒化社区发现方法[J]. 南京大学学报(自然科学版), 2017, 53(4): 764–.

Duan Zhen1，2，Min Xing1，2，Wang Qianqian2，3，Chen Jie1，2，Zhang Yanping1，2，Zhao Shu1，2*. Multilayer granulation community detection method based on quotient space[J]. Journal of Nanjing University(Natural Sciences), 2017, 53(4): 764–.

参考文献

[1]　Girvan M，Newman M E J．Community structure in social and biological networks.Proceedings of the National Academy of Sciences of the United States of America，2002，99(12)：7821－7826.
[2] 刘大有，金　弟，何东晓等．复杂网络社区挖掘综述．计算机研究与发展，2013，50(10)：2140－2154.(Liu D Y，Jin D，He D X，et al.Community mining in complex networks.Journal of Computer Research and Development，2013，50(10)：2140－2154.)
[3] Newman M E J．Fast algorithm for detecting community structure in networks.Physical Review E，2004，69(6)：066133.
[4] Newman M E J．Modularity and community structure in networks.Proceedings of the National Academy of Sciences of the United States of America，2006，103(23)：8577－8582.
[5] Shi J B，Malik J．Normalized cuts and image segmentation.IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22(8)：888－905.
[6] Karypis G，Kumar V．A fast and high quality multilevel scheme for partitioning irregular graphs.SIAM Journal on Scientific Computing，1998，20(1)：359－392.
[7] van Dongen S．A cluster algorithm for graphs.Information Systems(INS)，Report INS－R0010，2000：1－40.
[8] Rosvall M，Bergstrom C T．Maps of random walks on complex networks reveal community structure.Proceedings of the National Academy of Sciencesof the United States of America，2008，105(4)：1118－1123.
[9] Shao J，Han ZC，Yang Q L，et al.Community detection based on distance dynamics.In：Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Sydney，Australia：ACM，2015：1075－1084.
[10] Ronhovde P，Nussinov Z．Local multiresolution order in community detection.Journal of Statistical Mechanics：Theory and Experiment，2015，2015(1)：P01001.
[11] Newman M E J．Community detection in networks：Modularity optimization and maximum likelihood are equivalent.arXiv：1606.02319，2016.　
[12] Raghavan U N，Albert R，Kumara S．Near linear time algorithm to detect community structures in large－scale networks.Physical Review E，2007，76(3)：036106.
[13] Ahn Y Y，Bagrow J P，Lehmann S．Link communities reveal multiscale complexity in networks.Nature，2010，466(7307)：761－764.
[14] Soundarajan S，Hopcroft J E．Use of local group information to identify communities in networks.ACM Transactions on Knowledge Discovery from Data，2015，9(3)：21.
[15] Chen M M，Kuzmin K，Szymanski B K．Community detection via maximization of modularity and its variants.IEEE Transactions on Computational Social Systems，2014，1(1)：46－65.
[16] Ferreira L N，Zhao L．Time series clustering via community detection in networks.Information Sciences，2016，326：227－242.
[17] Blondel V D，Guillaume J L，Lambiotte R，et al.Fast unfolding of communities in large networks.Journal of Statistical Mechanics：Theory and Experiment，2008，2008(10)：P10008.
[18] Hobbs J R．Granularity.In：Proceedings of the 9thInternational Joint Conference on Artificial Intelligence.Los Angeles，CA，USA：Morgan Kaufmann Publishers Inc.，1985：432－435.
[19] Zadeh L A．Fuzzy logic＝ computing with words.IEEE Transactions on Fuzzy Systems，1996，4(2)：103－111.
[20] Pawlak Z．Rough sets：Theoretical aspects of reasoning about data.Boston，MA，USA：Kluwer Academic Publishers，1991，1－9.
[21] 张燕平，罗　斌，姚一豫等．商空间与粒计算：结构化问题求解理论与方法．北京：科学出版社，2010，91－94.
[22] 张　钹，张　铃．问题求解理论及应用．北京：清华大学出版社，1990，1－32.
[23] 张　铃，张　钹．问题求解理论及应用：商空间粒度计算理论及应用．第2版．北京：清华大学出版社，2007，3－27.
[24] Zachary W W．An information flow model for conflict and fission in small groups.Journal of Anthropological Research，1977，33(4)：452－473.　
[25] Lusseau D．The emergent properties of a dolphin social network.Proceedings of the Royal Society B：Biological Sciences，2003，270(Suppl 2)：S186－S188.
[26] Leskovec J，Kleinberg J，Faloutsos C．Graph evolution：Densification and shrinking diameters.ACM Transactions on Knowledge Discovery from Data(TKDD)，2007，1(1)：2.
[27] Cho E，Myers S A，Leskovec J．Friendship and mobility：User movement in location－based social networks.In：Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.San Diego，CA，USA：ACM，2011：1082－1090.
[28] Yang J，Leskovec J．Defining and evaluating network communities based on ground－truth.In：Proceedings of the 2012 IEEE 12th International Conference on Data Mining(ICDM)．Brussels，Belgium：IEEE，2012：745－754.
[29] Leskovec J，Lang K J，Dasgupta A，et al.Community structure in large networks：Natural cluster sizes and the absence of large well－defined clusters.Internet Mathematics，2009，6(1)：29－123.
[30] Steinhaeuser K，Chawla N V．Identifying and evaluating community structure in complex networks.Pattern Recognition Letters，2010，31(5)：413－421.
[31] Danon L，Díaz－Guilera A，Duch J，et al.Comparing community structure identification.Journal of Statistical Mechanics：Theory and Experiment，2005，2005(9)：P09008.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed