计算机科学 ›› 2019, Vol. 46 ›› Issue (11A): 348-353.

• 网络与通信 • 上一篇    下一篇

一种面向多维复杂网络的节点传播重要性算法

张昕, 王慧慧, 严沛, 郭阳   

  1. (辽宁大学信息学院 沈阳110004)
  • 出版日期:2019-11-10 发布日期:2019-11-20
  • 通讯作者: 王慧慧(1992-),女,硕士生,主要研究方向为复杂网络,E-mail:meng210021@163.com。
  • 作者简介:张昕(1979-),男,博士,副教授,CCF会员,主要研究方向为数据挖掘、复杂网络。
  • 基金资助:
    本文受国家自然科学基金项目(61472169),辽宁省发改委工程实验室项目(2016-294),辽宁省博士科研启动基金项目(20170520323)资助。

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

中图分类号: 

  • 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] 戴彩艳, 何菊, 胡孔法, 丁有伟, 李新霞. 基于衰减系数建立动态蛋白质网络模型进行关键蛋白质预测[J]. 计算机科学, 2020, 47(6A): 29-33.
[2] 马学彬,李爱丽,张晓娟,贾磊磊,肖静. 稀疏机会网络中基于固定中继节点与消息相关性的缓存管理策略[J]. 计算机科学, 2016, 43(Z11): 296-300.
[3] 秦李,杨子龙,黄曙光. 复杂网络的节点重要性综合评价[J]. 计算机科学, 2015, 42(2): 60-64.
[4] 张翼,刘玉华,许凯华,骆珍荣. 一种基于互信息的复杂网络节点重要性评估方法[J]. 计算机科学, 2011, 38(6): 88-89.
[5] . 复杂网络中重要性节点发掘综述[J]. 计算机科学, 2007, 34(12): 1-5.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 .
[2] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[3] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[4] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[5] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 .
[6] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 .
[7] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 .
[8] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 .
[9] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 .
[10] 王振朝,侯欢欢,连蕊. 抑制CMT中乱序程度的路径优化方案[J]. 计算机科学, 2018, 45(4): 122 -125 .