计算机科学 ›› 2017, Vol. 44 ›› Issue (12): 23-27.doi: 10.11896/j.issn.1002-137X.2017.12.004

• 第四届CCF大数据学术会议 • 上一篇    下一篇

一种基于关联关系的有向网络关键节点挖掘算法

梁莹莹,黄岚,王喆   

  1. 吉林大学计算机科学与技术学院 长春130012;符号计算与知识工程教育部重点实验室吉林大学 长春130012,吉林大学计算机科学与技术学院 长春130012;符号计算与知识工程教育部重点实验室吉林大学 长春130012;吉林大学珠海学院计算机系教育部符号计算与知识工程实验室 珠海519041,吉林大学计算机科学与技术学院 长春130012;符号计算与知识工程教育部重点实验室吉林大学 长春130012
  • 出版日期:2018-12-01 发布日期:2018-12-01
  • 基金资助:
    本文受国家自然科学基金项目(61373051,61472159),吉林省电子商务关键支撑技术工程实验室创新能力项目资助

Key Nodes Mining Algorithm Based on Association with Directed Network

LIANG Ying-ying, HUANG Lan and WANG Zhe   

  • Online:2018-12-01 Published:2018-12-01

摘要: 关键节点在网络中的重要程度高于其他大部分节点,关键节点挖掘是网络分析的重要研究内容,对网络结构和网络中的关系等研究而言都具有非常重要的意义。已有的关键节点挖掘算法从不同的侧重点进行节点关键性评价,文中基于网络中节点的局部性信息,结合节点与其一阶邻居节点的关联关系,提出了一种有向网络关键节点挖掘算法。该算法在关注节点所处局部环境的同时考虑关联节点间的关联强度及重要性影响,根据局部重要性和关联重要性共同进行关键节点的评价。在实验网络上的影响力传播实验表明,相比于经典的度中心性等关键节点评价算法,所提算法挖掘得到的关键节点对影响力的传播能力更强,说明了算法的准确性。

关键词: 有向网络,中心性,关联关系,关键节点,影响力传播

Abstract: The importance of key nodes in the network is higher than most other nodes,and key nodes mining is an important research area of network analysis.It is of great significance for study of network,such as study of network structure,network relations and so on.Many key nodes mining algorithms evaluate key nodes from different emphases.In this paper,we proposed a key nodes mining algorithm based on association with directed network,combining nodes’ partial information and association with neighbors in the network.This algorithm calculates the local centrality of nodes at first.In addition,it also calculates the association centrality between associated nodes based on nodes’ local centrality and the strength of association at the same time.In order to measure the accuracy of the key nodes mining algorithm,we designed influence propagation experiment to test the algorithm.Results show that compared with the classical centrality and other key nodes mining algorithms,key nodes mined by our algorithm have higher ability to spread influence in experimental network,which also illustrates the accuracy of our algorithm.

Key words: Directed network,Centrality,Association,Key nodes,Influence propagation

[1] NEWMAN M.Networks:An Introduction[M].Oxford University Press,Inc.2010.
[2] CALLAWAY D S,NEWMAN M E,STROGATZ S H,et al.Network robustness and fragility:percolation on random graphs[J].Physical Review Letters,2000,5(85):5468-5471.
[3] CRUCITTI P,LATORA V,MARCHIORI M,et al.Error and attack tolerance of complex networks[J].Nature,2000,6(6794):542-542.
[4] WENG J,LIM E P,JIANG J,et al.TwitterRank:finding topic-sensitive influential twitterers[C]∥International Conference on Web Search and Web Data Mining(WSDM 2010).New York,Ny,Usa,February,2010:261-270.
[5] BODENDORF F,KAISERISER C.Detecting opinion leadersand trends in online social networks[C]∥ACM Workshop on Social Web Search and Mining.ACM,2009:65-68.
[6] GAO C,LAN X,ZHANG X,et al.A bio-inspired methodology of identifying influential nodes in complex networks[J].Plos One,2013,8(6):e66732.
[7] FREEMAN L C.Centrality in Social Networks:I.ConceptualClarification[J].Social Networks,1979,1(3):215-239.
[8] SABIDUSSI G.The centrality index of a graph[J].Psycho-metrika,1966,1(4):581-603.
[9] REN X L,LV L Y.Review of ranking nodes in complex net- works[J].Chinese Science Bulletin (Chin Ver),2014,9:1175-1197.(in Chinese) 任晓龙,吕琳媛.网络重要节点排序方法综述[J].科学通报,2014,9(13):1175-1197.
[10] LIU J G,REN Z M,GUO Q,et al.Node importance ranking of complex networks[J].Acta Physica Sinica,2013,2(17):178901.(in Chinese) 刘建国,任卓明,郭强,等.复杂网络中节点重要性排序的研究进展[J].物理学报,2013(17):178901.
[11] KITSAK M,GALLOS L K,HAVLIN S,et al.Identification of influential spreaders in complex networks[J].Nature Physics,2010,6(11):888-893.
[12] CHEN D,LV L,SHANG M S,et al.Identifying influentialnodes in complex networks[J].Physica a:Statistical Mechanics and Its Applications,2012,1(4):1777-1787.
[13] REN Z M,SHAO F,LIU J G,et al.Node importance measurement based on the degree and clustering coefficient information[J].Acta Physica Sinica,2013,2(12):128901.(in Chinese) 任卓明,邵凤,刘建国,等.基于度与集聚系数的网络节点重要性度量方法研究[J].物理学报,2013,2(12):128901.
[14] ZHOU X,ZHANG F M,LI K W,et al.Finding vital node by node importanceevaluation matrix in complex networks[J].Acta Physica Sinica,2012,1(5):50201.(in Chinese) 周漩,张凤鸣,李克武,等.利用重要度评价矩阵确定复杂网络关键节点[J].物理学报,2012,1(5):50201.
[15] ZHAO Y H,WANG Z L,ZHENG J,et al.Finding most vital node by node importance contribution matrix in communication netwoks[J].Journal of Beijing University of Aeronautics and Astronautics,2009,5(9):1076-1079.(in Chinese) 赵毅寰,王祖林,郑晶,等.利用重要性贡献矩阵确定通信网中最重要节点[J].北京航空航天大学学报,2009,5(9):1076-1079.
[16] Lü L,ZHANG Y C,YEUNG C H,et al.Leaders in social networks,the delicious case[J].PloS One,2011,6(6):e21202.
[17] CHEN D B,GAO H,Lü L,et al.Identifying Influential Nodes in Large-Scale Directed Networks:The Role of Clustering[J].Plos One,2013,8(10):e77455.
[18] KLEIN A,AHLF H,SHARMA V.Social activity and structural centrality in online social networks[J].Telematics & Informa-tics,2015,2(2):321-332.
[19] SHAO F,GUO Q,ZENG S Q,et al.Research Progress of the Microblog System Structures[J].Journal of University of Electronic Science and Technology of China,2014(2):174-183.(in Chinese) 邵凤,郭强,曾诗奇,等.微博系统网络结构的研究进展[J].电子科技大学学报,2014(2):174-183.
[20] Lü L,ZHOU T.Link prediction in complex networks:A survey[J].Physica A Statistical Mechanics & Its Applications,2011,0(6):1150-1170.
[21] BORGATTI S P,MEHRA A,BRASS D J,et al.Network analysis in the social sciences[J].Science,2009,3(5916):892-895.
[22] KOSSINETS G.Effects of missing data in social networks[J].Social Networks,2010,8(3):247-268.
[23] WU X D,LI Y,LI L.Influence Analysis of Online Social Networks[J].Chinese Journal of Computers,2014,7(4):735-752.(in Chinese) 吴信东,李毅,李磊.在线社交网络影响力分析[J].计算机学报,2014,7(4):735-752.
[24] LIN D.An Information-Theoretic Definition of Similarity[C]∥Fifteenth International Conference on Machine Learning.Morgan Kaufmann Publishers Inc.,1998:296-304.
[25] KEMPE D,KLEINBERG J,TARDOS .Maximizing the spread of influence through a social network[C]∥Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2003:137-146.
[26] http://konect.uni-koblenz.de/networks/moreno_taro.
[27] http://konect.uni-koblenz.de/networks/moreno_highschool.
[28] http://konect.uni-koblenz.de/networks/moreno_innovation.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!