计算机科学

计算机科学 ›› 2023, Vol. 50 ›› Issue (11A): 230100122-7.doi: 10.11896/jsjkx.230100122

• 大数据&数据科学 • 上一篇    下一篇

基于子图特征的节点排序算法

陈端兵1, 杨志杰1, 曾卓1, 傅彦1, 周俊临1, 赵俊严2   

  1. 1 电子科技大学大数据研究中心 成都 611731
    2 北京特种车辆研究所 北京 100072
  • 发布日期:2023-11-09
  • 通讯作者: 陈端兵(dbchen@uestc.edu.cn)
  • 基金资助:
    国家自然科学基金重点项目(T2293771);教育部哲学社会科学研究重大课题(21JZD055)

Node Ranking Algorithm Based on Subgraph Features

CHEN Duanbing1, YANG Zhijie1, ZENG Zhuo1, FU Yan1, ZHOU Junlin1, ZHAO Junyan2   

  1. 1 Big Data Research Center,University of Electronic Science and Technology of China,Chengdu 611731,China
    2 Beijing Special Vehicle Institute,Beijing 100072,China
  • Published:2023-11-09
  • About author:CHEN Duanbing,born in 1971,Ph.D,professor.His main research interests include big data mining and complex networks.
  • Supported by:
    Major Program of National Natural Science Foundation of China(T2293771) and Key Research Project of Philo-sophy and Social Sciences of the Ministry of Education(21JZD055).

PDF (PC)

520

摘要： 复杂网络理论已被广泛应用于各个领域,节点重要性排序研究是复杂网络领域的重要分支。复杂网络中节点重要性排序及重要节点挖掘对分析和理解复杂网络的结构与功能具有重要意义。众多学者针对复杂网络的关键节点识别和节点重要性排序问题进行了深入研究,取得了大量研究成果。但随着人工智能的发展和数据体量的飞速增长,复杂网络规模呈指数级增长,传统算法的准确性和泛化性已经无法满足现实需求。文中基于节点的二阶邻域信息,提出了一种基于子图特征的节点重要性排序(Subgraph Feature Extraction Rank,SFE Rank)的机器学习模型。利用二阶邻域信息,建立局部子图的含权邻接矩阵,通过矩阵特征分解提取能够有效反映节点局部特征信息的向量表征,在此基础上,建立机器学习模型,用于学习节点子图特征向量和节点重要性的关联关系。在9个真实网络上进行实验,结果表明,相比已有的节点重要性排序方法,所提方法具有更优的排序效果和更好的泛化性能。

关键词: 复杂网络, 重要节点, 特征提取, 子图特征, 机器学习

Abstract: Complex network theory has been widely applied in various fields,and node ranking is an important branch in the complex networks.Node ranking and critical node mining are significant for analyzing and understanding the structure and function of complex networks.Many scholars have conducted in-depth researches on critical nodes identification and ranking in complex networks,and have achieved great success.However,with the development of artificial intelligence and rapid growth of data,the size of complex networks grows exponentially.The accuracy and generalization of traditional algorithms can no longer meet the real demand.A machine learning model on node ranking(subgraph feature extraction rank) based on subgraph features of the second-order neighborhood information of nodes is proposed in this paper.A weighted adjacency matrix of local subgraphs is established using the second-order neighborhood information firstly.Then,vector representations that can effectively reflect the local feature of nodes are extracted through matrix feature decomposition.Finally,a machine learning model is established to train the correlation between node’s subgraph feature vector and its influence.Experimental results on nine real networks show that the proposed method has better performance and generalization compared with benchmark node ranking methods.

Key words: Complex networks, Critical nodes, Feature extraction, Subgraph features, Machine learning

中图分类号: 

  • TP301
[1]LÜ L,ZHOU T.Link prediction in complex networks:A survey[J].Physica A:statistical mechanics and its applications,2011,390(6):1150-1170.
[2]LU L Y,ZHOU T.Link Prediction[M].Beijing:Higher Education Press,2013.
[3]REN X L,LU L Y.Review of ranking nodes in complex networks[J].Science Bulletin,2014,59(13):1175-1197.
[4]ZHU J F,CHEN D B,ZHOU T,et al.A survey on mining relatively important nodes in network science[J].Journal of University of Electronic Science and Technology of China,2019,48(4):595-603.
[5]HE N,LI D Y,GAN W Y,et al.Mining vital nodes in complex networks[J].Computer Science,2007,34(12):1-5.
[6]KITSAK M,GALLOS L K,HAVLIN S,et al.Identification of influential spreaders in complex networks[J].Nature Physics,2010,6:888-893.
[7]LÜ L,ZHOU T,ZHANG Q M,et al.The H-index of a network node and its relation to degree and coreness[J].Nature Communications,2016,7(1):1-7.
[8]FREEMAN L C.Centrality in social networks conceptual clarification[J].Social networks,1978,1(3):215-239.
[9]FREEMAN L C.A Set of Measures of Centrality Based on Betweenness[J].Sociometry,1977,40(1):35-41.
[10]BRIN S,PAGE L.The anatomy of a large-scale hypertextualweb search engine[J].Computer Networks and ISDN systems,1998,30(1-7):107-117.
[11]LÜ L,ZHANG Y C,YEUNG C H,et al.Leaders in social networks,the delicious case[J].PLoS One,2011,6(6):e21202.
[12]ZHAO N,LI J,WANG J,et al.Relatively important nodes mi-ning method based on neighbor layer diffuse[J].Journal of University of Electronic Science and Technology of China,2021,50(1):121-126.
[13]FREEMAN L C,BORGATTI S P,WHITE D R.Centrality in valued graphs:A measure of betweenness based on network flow[J].Social Networks,1991,13(2):141-154.
[14]ESTRADA E,HIGHAM D J,HATANO N.Communicabilitybetweenness in complex networks[J].Physica A Statistical Mechanics & Its Applications,2009,388(5):764-774.
[15]NEWMAN M.A measure of betweenness centrality based onrandom walks[J].Social Networks,2003,27(1):39-54.
[16]WANG　A.Research on node importance evaluation methodbased on complex network structure features[D].Beijing:People’s Public Security University of China,2020.
[17]ZHAO J,WANG Y,DENG Y.Identifying influential nodes in complex networks from global perspective[J].Chaos,Solitons &Fractals,2020,133:109637.
[18]CHEN D B,SUN H L,TANG Q,et al.Identifying influential spreaders in complex networks by propagation probability dynamics[J].Chaos An Interdisciplinary Journal of NonlinearScience,2019,29(3):033120.
[19]PAN K,YIN C L,WANG L,et al.Identifying critical nodesbased on feature engineering[J].Journal of University of Electronic Science and Technology of China,2021,50(6):930-937.
[20]XUE Y,DENG Y.Entailment for intuitionistic fuzzy sets based on generalized belief structures[J].International Journal of Intelligent Systems,2020,35(6):963-982.
[21]YU E,WANG Y,FU Y,et al.Identifyingcritical nodes in complex networks via graph convolutional networks[J].Knowledge-Based Systems,2020,198:105893.
[22]MUNOZ J,REZAEI A A,JALILI M,et al.Deep learning based bi-level approach for proactive loan prospecting[J].Expert Systems with Applications,2021,185:115607.
[23]REZAEI A A,MUNOZ J,JALILI M,et al.Machine learning-based approach for vital node identification in complex networks[J].Expert Systems with Applications,2023,214:119086.
[24]XIE L X,SUN H H,YANG H Y,et al.Key node recognition in complex networks based on the K-shell method[J].J Tsinghua Univ(Sci & Technol),2022,62(5):849-861.
[25]GU Y R,ZHU Z Y.Node ranking in complex networks based on LeaderRank and modes similarity[J].Journal of University of Electronic Science and Technology of China,2017,46(2):441-448.
[26]LIU J C,MA T C,YUE M L.HHa Centrality Algorithm:A Node Centrality Algorithm Based on the H-Index and Ha-Index[J].Library and Information Service,2021,65(20):92-100.
[27]WANG L M.Identification of vital nodes in complex networks based on deep reinforcement learning[D].Bengbu:Anhui University of Finance and Economics,2020.
[28]YANG S,HU B,ZHANG Z,et al.Inductive link prediction with interactive structure learning on attributed graph[C]//Machine Learning and Knowledge Discovery in Databases.Research Track:European Conference,2021:383-398.
[29]LIU L L,SONG X Y,CHEN Y B.Link prediction in opportu-nistic networks based on networks representation learning[J].Journal of Beijing University of Posts and Telecommunications,2022,45(4):64-69.
[30]TAN S Y,QI M Z,WU J,et al.Link predictability of complex network from spectrum perspective[J].Acta Physica Sinica,2020,69(8):188-197.
[31]HUANG H B,YANG L M,WANG J X,et al.Identificationtechnique of essential nodes in protein networks based on combined parameters[J].Acta Automatica Sinica,2008,34(11):1388-1395.
[32]HU G,NIU Q,XU L P,et al.The model to analyses of node importance order structure evolution based on network hyperlink information entropy[J].Acta Electronica Sinica,2022,50(11):2638-2644.
[33]ZHENG W P,WU Z K,YANG G.A novel algorithm for identi-fying critical nodes in networks based on local centrality[J].Journal of Computer Research and Development,2019,56(9):1872-1880.
[34]LUO J,YAN G H,ZHANG M,et al.Research on node importance fused multi-information for multi-relational social networks[J].Journal of Computer Research and Development,2020,57(5):954-970.
[35]GAO C,JIANG S H,WANG Z,et al.A novel method to identify influential stations based on dynamic passenger flows[J].Scientia Sinica Informationis,2021,51(9):1490-1506.
[36]ZHOU M Y,WU X Y,CAO Y,et al.A novel method to identify multiple influential nodes in complex networks[J].Scientia Sinica Informationis,2019,49(10):1333-1342.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发