Computer Science

Computer Science ›› 2023, Vol. 50 ›› Issue (11A): 230100122-7.doi: 10.11896/jsjkx.230100122

• Big Data & Data Science • Previous Articles     Next Articles

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)

517

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

CLC Number: 

  • 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.
[1] LI Ke, YANG Ling, ZHAO Yanbo, CHEN Yonglong, LUO Shouxi. EGCN-CeDML:A Distributed Machine Learning Framework for Vehicle Driving Behavior Prediction [J]. Computer Science, 2023, 50(9): 318-330.
[2] HUANG Shuxin, ZHANG Quanxin, WANG Yajie, ZHANG Yaoyuan, LI Yuanzhang. Research Progress of Backdoor Attacks in Deep Neural Networks [J]. Computer Science, 2023, 50(9): 52-61.
[3] WANG Yao, LI Yi. Termination Analysis of Single Path Loop Programs Based on Iterative Trajectory Division [J]. Computer Science, 2023, 50(9): 108-116.
[4] LIU Xiang, ZHU Jing, ZHONG Guoqiang, GU Yongjian, CUI Liyuan. Quantum Prototype Clustering [J]. Computer Science, 2023, 50(8): 27-36.
[5] WANG Yu, WANG Zuchao, PAN Rui. Survey of DGA Domain Name Detection Based on Character Feature [J]. Computer Science, 2023, 50(8): 251-259.
[6] LI Yang, LI Zhenhua, XIN Xianlong. Attack Economics Based Fraud Detection for MVNO [J]. Computer Science, 2023, 50(8): 260-270.
[7] ZHU Boyu, CHEN Xiao, SHA Letian, XIAO Fu. Two-layer IoT Device Classification Recognition Model Based on Traffic and Text Fingerprints [J]. Computer Science, 2023, 50(8): 304-313.
[8] LU Xingyuan, CHEN Jingwei, FENG Yong, WU Wenyuan. Privacy-preserving Data Classification Protocol Based on Homomorphic Encryption [J]. Computer Science, 2023, 50(8): 321-332.
[9] WANG Xiya, ZHANG Ning, CHENG Xin. Review on Methods and Applications of Text Fine-grained Emotion Recognition [J]. Computer Science, 2023, 50(6A): 220900137-7.
[10] WANG Dongli, YANG Shan, OUYANG Wanli, LI Baopu, ZHOU Yan. Explainability of Artificial Intelligence:Development and Application [J]. Computer Science, 2023, 50(6A): 220600212-7.
[11] WANG Jinjin, CHENG Yinhui, NIE Xin, LIU Zheng. Fast Calculation Method of High-altitude Electromagnetic Pulse Environment Based on Machine Learning [J]. Computer Science, 2023, 50(6A): 220500046-5.
[12] FU Xiong, NIE Xiaohan, WANG Junchang. Study on Android Fake Application Detection Method Based on Interface Similarity [J]. Computer Science, 2023, 50(6A): 220300114-7.
[13] LIU Hongyi, WANG Rui, WU Guanfeng, ZHANG Yang. Diesel Engine Fault Diagnosis Based on Kernel Robust Manifold Nonnegative Matrix Factorizationand Fusion Features [J]. Computer Science, 2023, 50(6A): 220400128-8.
[14] YIN Xingzi, PENG Ningning, ZHAN Xueyan. Filtered Feature Selection Algorithm Based on Persistent Homology [J]. Computer Science, 2023, 50(6): 159-166.
[15] HUANG Xundi, PANG Xiongwen. Review of Intelligent Device Fault Diagnosis Based on Deep Learning [J]. Computer Science, 2023, 50(5): 93-102.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.