复杂网络中的层次结构挖掘

南京大学学报(自然科学版) ›› 2016, Vol. 52 ›› Issue (5): 861–.

复杂网络中的层次结构挖掘

余成进1，2，赵　姝1，2*，陈　洁1，2，张燕平1，2，段　震1，2

出版日期:2016-09-25 发布日期:2016-09-25
作者简介: 1.安徽大学计算机科学与技术学院，合肥，230601；2.安徽大学协同创新中心，合肥，230601
基金资助:
基金项目：国家“八六三”高技术研究发展计划基金(2015AA124102)，国家自然科学基金(61402006，61175046)，安徽省自然科学基金(1508085MF113)，安徽省高等学校省级自然科学基金重点项目(KJ2013A016)，教育部留学回国人员科研启动基金(第49批)
收稿日期：2016－08－24
*通讯联系人，Email：zhaoshuzs2002@hotmail.com

Hierarchical structure detection in complex network

Yu Chengjin1，2，Zhao Shu1，2*，Chen Jie1，2，Zhang Yanping1，2，Duan Zhen1，2

Online:2016-09-25 Published:2016-09-25
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

摘要/Abstract

摘要： 挖掘复杂网络中的层次结构对复杂网络的研究有着重要的意义．复杂网络中的社团结构往往具有层次性．过去的研究中，研究者更多的关注于层次社团结构，而很少关注于社团内部成员的层次结构．因此，提出一种基于模糊相容关系的层次结构挖掘算法(fuzzy tolerance relation based hierarchical structure detection algorithm，FHSD)，旨在挖掘层次社团结构以及社团内部成员层次结构．在该算法中，首先通过相似度函数计算节点之间的相似性从而获取一个满足模糊相容关系的相似度矩阵；其次，基于相似度矩阵获取对应的商空间链；然后，依据重叠节点对各社团的隶属度处理商空间链各层中的重叠节点，从而得到层次社团结构；最后，基于处理后的商空间链，获取对原始模糊相容的近似模糊等价关系，从而获取社团内部成员层次结构．在真实网络上的实验结果表明：(1)复杂网络中不仅存在层次社团结构，同时存在基于模糊相容关系的社团成员层次结构；(2)相比于当前主流的社团挖掘算法，FHSD挖掘出的社团结构具有最高的精准性(NMI accuracy)和较高的模块度值．

Abstract: Detecting hierarchical structure is crucial for the research of complex networks.Generally，the community structure of a complex network is hierarchical.In the past，researchers paid more attention to the hierarchical community structure，and rarely focused on the hierarchical structure of the community members.Therefore，the paper proposes a fuzzy tolerance relation based hierarchical structure detection algorithm(FHSD)which focus on detecting both hierarchical community structure and hierarchical structure of the community members.In FHSD，the algorithm firstly computes the similarity between nodes based on similarity function and then a matrix which satisfies the fuzzy tolerance relation can be obtained.Secondly，a corresponding chain of hierarchical tolerance relations can be gotten based on fuzzy tolerance relation matrix.Then，overlapping nodes in each layer of the hierarchical tolerance chain can be processed according to membership.And then，hierarchical community structure can be gotten.Finally，approximate fuzzy equivalence relation can be obtained from fuzzy tolerance relation which based on quotient space chain that has been handled，and we can furtherly get hierarchical structure of the community members.Experimental results on real networks show：(1)In the complex network，there exists not only the hierarchical community structure，but also the hierarchical structure of the community members based on fuzzy tolerance relation.(2)Compared to the current mainstream community detecting algorithms，the community structure detected by FHSD has the highest accuracy(NMI accuracy)and a higher modularity value.

余成进1，2，赵　姝1，2*，陈　洁1，2，张燕平1，2，段　震1，2. 复杂网络中的层次结构挖掘[J]. 南京大学学报(自然科学版), 2016, 52(5): 861–.

Yu Chengjin1，2，Zhao Shu1，2*，Chen Jie1，2，Zhang Yanping1，2，Duan Zhen1，2. Hierarchical structure detection in complex network[J]. Journal of Nanjing University(Natural Sciences), 2016, 52(5): 861–.

参考文献

[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] Newman M E J．Detecting community structure in networks.The European Physical Journal B Condensed Matter and Complex Systems，2004，38(2)：321－330.
[3] Marta S P，Roger G，Moreira A A，et al.Extracting the hierarchical organization of complex systems.Proceedings of the National Academy of Sciences of the United States of America，2007，104(39)：15224－15229.
[4] Yang B，Di J，Liu J，et al.Hierarchical community detection with applications to realworld network analysis.Data & Knowledge Engineering，2013，83(90)：20－38.
[5] Blondel V D，Guillaume J L，Lambiotte R，et al.Fast unfolding of communities in large networks.Journal of Statistical Mechanics Theory & Experiment，2008，30(2)：155－168.
[6] Roger G，Amaral L A N．Functional cartography of complex metabolic networks.Nature，2005，433(7028)：895－900.
[7] Flake G W，Lawrence S，Giles C L，et al.Selforganization and identification of Web communities.IEEE Computer，2002，35(3)：66－70.
[8] Chen F，Li K．Detecting hierarchical structure of community members in social networks.KnowledgeBased Systems，2015，87(C)：3－15.
[9] Kernighan B W，Lin S．An efficient heuristic procedure for partitioning graphs.Bell Labs Technical Journal，1970，49(2)：291－307.
[10] Pothen A，Simon H D，Liou K P．Partitioning sparse matrices with eigenvectors of graphs.SIAM Journal on Matrix Analysis & Applications，1990，11(3)：430－452.
[11] Newman M E．Fast algorithm for detecting community structure in networks.Physical Review E Statistical Nonlinear & Soft Matter Physics，2004，69(6)：066133－066133.
[12] Blondel V D，Guillaume J L，Lambiotte R，et al.Fast unfolding of communities in large networks.Journal of Statistical Mechanics Theory & Experiment，2008，30(2)：155－168.
[13] Jin D，Liu D Y，Yang B，et al.Fast complex network clustering algorithm using local detection.Acta Electronica Sinica，2011，39(11)：2540－2546.
[14] Andrea L，Santo F．Community detection algorithms：A comparative analysis.Physical Review E Statistical Nonlinear & Soft Matter Physics，2009，80(5 Pt 2)：2142－2152.
[15] Shen H，Cheng X，Cai K，et al.Detect overlapping and hierarchical community structure in networks.Physica A Statistical Mechanics & Its Applications，2009，388(8)：1706－1712.
[16] Li Z，Zhang X S，Wang R S，et al.Discovering link communities in complex networks by an integer programming model and a genetic algorithm.Plos One，2013，8(12)：e83739－e83739.
[17] YongYeol A，Bagrow J P，Sune L．Link communities reveal multiscale complexity in networks.Nature，2010，466(7307)：761－764.
[18] 王国胤，张清华，胡　军．粒计算研究综述．智能系统学报，2007，2(6)：8－26.(Wang G Y，Zhang Q H，Hu J．An overview of granular computing.CAAI Transactions on Intelligent Systems，2007，2(6)：8－26)．
[19] 陶　华，唐旭清．基于模糊邻近关系的聚类结构分析．计算机科学，2013，40(1)：257－261.(Tao H，Tang X Q．Clustering structural analysis on fuzzy proximity relation.Computer Science，2013，40(1)：257－261.)
[20] 王伦文，张贤骥，张　铃．基于模糊相容关系的聚类粒度分析．系统仿真2014，26(7)：1492－1496.(Wang L W，Zhang X J，Zhang L．Granular analysis in clustering based on fuzzy tolerance relation.Journal of System Simulation，2014，26(7)：1492－1496.)
[21] Zhang L，Zhang Y，Zhao S．The optimal approximation of fuzzy tolerance relation.In：International Conference on Rough Sets and Knowledge Technology.Springer Berlin Heidelberg，2011：591－599.
[22] Zhao S，Zhang L，Xu X，et al.Hierarchical description of uncertain information.Information Sciences，2014，268(1)：133－146.
[23] Zhang L，Zhang B．Fuzzy tolerance quotient spaces and fuzzy subsets.Science China Information Sciences，2010，53(4)：704－714.
[24] He F，Zhang Y，Zhou X，et al.Multigranularitybased routing algorithm for dynamic networks.Journal of Networks，2014，9(5)：1333－1338.
[25] Seol K，Kim J D，Baik D K．Common neighbour similaritybased approach to support intimacy measurement in social networks.Journal of Information Science，2016，42(2)：128－137.
[26] Gupta A K，Sardana N．Significance of clustering coefficient over jaccard index.In：2015 Eighth International Conference on Contemporary Computing(IC3)．Noida，India：IEEE，2015：463－466.
[27] Adamic L A，Adar E．Friends and neighbors on the Web.Foreign Affairs，2003，31(2)：38－41.
[28] Zhou T，Lv L，Zhang Y C．Predicting missing links via local information.Physics of Condensed Matter，2009，71(4)：623－630.
[29] Zhu X，Tian H，Cai S，et al.Predicting missing links via significant paths.Europhysics Letters，2014，106(1)：18008.
[30] Dongen S．A cluster algorithm for graphs.Information Systems，2000：1－40.
[31] Raghavan U N，Albert R，Kumara S．Near linear time algorithm to detect community structures in largescale networks.Physical Review E，2007，76(3)：036106.
[32] Shao J，Han Z，Yang Q，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.
[33] Steinhaeuser K，Chawla N V．Identifying and evaluating community structure in complex networks.Pattern Recognition Letters，2010，31(5)：413－421.
[34] Zachary W W．An information flow model for conflict and fission in small groups.Journal of Anthropological Research，1977：452－473.
[35] Lusseau D．The emergent properties of a dolphin social network.Proceedings of the Royal Society of London B：Biological Sciences，2003，270(Suppl 2)：S186－S188.
[36] Girvan M，Newman M E J．Community structure in social and biological networks.Proceedings of the National Academy of Sciences，2002，99(12)：7821－7826.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed