Computer Science ›› 2019, Vol. 46 ›› Issue (11A): 348-353.

• Network & Communication • Previous Articles     Next Articles

Node Propagation Importance Algorithm for Multi-dimensional Complex Networks

ZHANG Xin, WANG Hui-hui, YAN Pei, GUO Yang   

  1. (School of Information,Liaoning University,Shenyang 110004,China)
  • Online:2019-11-10 Published:2019-11-20

Abstract: How to measure node importance in the network topology has always been a research hotspot in the field of complex networks.Most of the existing researches are oriented to single dimensional networks.Therefore,aiming at the fact that there is often a multi dimensional coexistence in real-world network structure,the definition of dimensional similarity was proposed to measure the relationship between dimensions.Considering the impact of information attenuation on node importance in actual process of information propagation,the definition of propagation attenuation rate is given.The value of attenuation coefficient is determined by propagation non-destructive assumption on a fully connected single dimensional network and corresponding algorithm.And the node importance algorithm is given further.The small network characteristics of the complex network are utilized in the given algorithm to limit the maximum propagation hops,so that the algorithm takes into account both time efficiency and accuracy.The experimental results on the real network show that the proposed algorithm has certain advantages in accuracy and time efficiency compared with traditional node degree and node betweenness methods.

Key words: Multidimensional network, Node importance, Dimensional similarity, Attenuation rate, Maximum propagation hops

CLC Number: 

  • TP301
[1]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社有限公司,2006.
[2]COSTA L F,OLIVEIRA JR O N,TRAVIESO G,et al.Analyzing and modeling real-world phenomena with complex networks:a survey of applications[J].Advances in Physics,2011,60(3):329-412.
[3]PEROZZI B,AL-RFOU R,SKIENA S.Deepwalk:Online learning of social representations[C]∥Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2014:701-710.
[4]周涛,柏文洁,汪秉宏,等.复杂网络研究概述[J].物理,2005,34(1).
[5]FREEMAN L C.A set of measures of centrality based on betweenness[J].Sociometry,1977:35-41.
[6]BOCCALETTI S,BIANCONI G,CRIADO R,et al.The structure and dynamics of multilayer networks[J].Physics Reports,2014,544(1):1-122.
[7]YU H,LIU Z,LI Y J.Key nodes in complex networks identified by multi-attribute decision-making method[J].2013.
[8]MENICHETTI G,REMONDINI D,PANZARASA P,et al.Weighted multiplex networks[J].PloS one,2014,9(6):e97857.
[9]SHCHUROV A A.A multilayer model of computer networks[J].arXiv:1509.00721,2015.
[10]BERLINGERIO M,COSCIA M,GIANNOTTI F,et al.Foundations of multidimensional network analysis[C]∥2011 International Conference on Advances in Social Networks Analysis and Mining (ASONAM).IEEE,2011:485-489.
[11]杨建祥,王朝坤,王萌,等.全动态多维网络局部介数中心度算法[J].计算机学报,2015(9):254-4164[12]BERLINGERIO M,COSCIA M,GIANNOTTI F,et al.Multidimensional networks:foundations of structural analysis[J].World Wide Web,2013,16(5/6):567-593.
[13]WATTS D J,STROGATZ S H.Collective dynamics of ‘small-world’networks[J].Nature,1998,393(6684):440.
[14]HENDRY J B.Rural Vietnam:The Small World of Khanh Hau[M].Routledge,2017.
[15]BO S,GUO-PING J,YU-RONG S,et al.Rapid identifying high-influence nodes in complex networks[J].Chinese Physics B,2015,24(10):100101.
[16]XU B,QI J,ZHOU C,et al.Hybrid self-adaptive algorithm for community detection in complex networks[J].Mathematical Problems in Engineering,2015,2015.
[17]SUH B,CONVERTINO G,CHI E H,et al.The singularity is not near:slowing growth of Wikipedia[C]∥International Symposium on Wikis and Open Collaboration.DBLP,2009:1-10.
[18]LOZANO S,ARENAS A,SÁNCHEZ A.Mesoscopic structure conditions the emergence of cooperation on social networks[J].Plos One,2008,3(4):e1892.
[1] LUO Jian-zhen,CAI Jun ,LIU Yan,ZHAO Hui-min. Caching and Replacing Strategy in Information-centric Network Based on Content Popularity and Community Importance [J]. Computer Science, 2018, 45(7): 116-121.
[2] MA Xue-bin, LI Ai-li, ZHANG Xiao-juan, JIA Lei-lei and XIAO Jing. Buffer Management Based on Stationary Relay Nodes and Message Correlation in Sparse Opportunistic Networks [J]. Computer Science, 2016, 43(Z11): 296-300.
[3] QIN Li, YANG Zi-long and HUANG Shu-guang. Synthesis Evaluation Method for Node Importance in Complex Networks [J]. Computer Science, 2015, 42(2): 60-64.
[4] ZHANG Yi,LIU Yu-hua,XU Kai-hua,LUO Zhen-rong. Evaluation Method for Node Importance Based on Mutual Information in Complex Networks [J]. Computer Science, 2011, 38(6): 88-89.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[2] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[5] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .