|本期目录/Table of Contents|

[1]余成进,赵 姝*,陈 洁,等.复杂网络中的层次结构挖掘[J].南京大学学报(自然科学),2016,52(5):861.[doi:10.13232/j.cnki.jnju.2016.05.012]
 Yu Chengjin,Zhao Shu*,Chen Jie,et al.Hierarchical structure detection in complex network[J].Journal of Nanjing University(Natural Sciences),2016,52(5):861.[doi:10.13232/j.cnki.jnju.2016.05.012]
点击复制

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

《南京大学学报(自然科学)》[ISSN:0469-5097/CN:32-1169/N]

卷:
52
期数:
2016年第5期
页码:
861
栏目:
出版日期:
2016-10-01

文章信息/Info

Title:
Hierarchical structure detection in complex network
作者:
余成进12赵 姝12*陈 洁12张燕平12段 震12
1.安徽大学计算机科学与技术学院,合肥,230601;2.安徽大学协同创新中心,合肥,230601
Author(s):
Yu Chengjin12Zhao Shu12*Chen Jie12Zhang Yanping12Duan Zhen12
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
关键词:
层次结构模糊相容关系社团发现商空间链
Keywords:
hierarchical structurefuzzy tolerance relationcommunity detectionquotient space chain
分类号:
TP301
DOI:
10.13232/j.cnki.jnju.2016.05.012
文献标志码:
A
摘要:
挖掘复杂网络中的层次结构对复杂网络的研究有着重要的意义.复杂网络中的社团结构往往具有层次性.过去的研究中,研究者更多的关注于层次社团结构,而很少关注于社团内部成员的层次结构.因此,提出一种基于模糊相容关系的层次结构挖掘算法(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.

参考文献/References:

[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 real­world 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.Self­organization 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.Knowledge­Based 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]  Yong­Yeol 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.Multi­granularity­based routing algorithm for dynamic networks.Journal of Networks,2014,9(5):1333-1338.
[25]  Seol K,Kim J D,Baik D K.Common neighbour similarity­based 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 large­scale 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.

相似文献/References:

备注/Memo

备注/Memo:
基金项目:国家“八六三”高技术研究发展计划基金(2015AA124102),国家自然科学基金(61402006,61175046),安徽省自然科学基金(1508085MF113),安徽省高等学校省级自然科学基金重点项目(KJ2013A016),教育部留学回国人员科研启动基金(第49批)
收稿日期:2016-08-24
*通讯联系人,E­mail:zhaoshuzs2002@hotmail.com
更新日期/Last Update: 2016-09-25