Computer Science ›› 2017, Vol. 44 ›› Issue (12): 23-27.doi: 10.11896/j.issn.1002-137X.2017.12.004

Previous Articles     Next Articles

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.

No related articles found!
Full text



No Suggested Reading articles found!