基于分形特性的复杂网络全局效率估计方法

张胜; 戴维凯; 吴锋; 蓝文祥

doi:10.11959/j.issn.1000-436x.2020118

您当前的位置：

首页 >

文章列表页 >

基于分形特性的复杂网络全局效率估计方法

学术通信 | 更新时间：2024-06-05

- 基于分形特性的复杂网络全局效率估计方法
- Global efficiency estimation method of complex network based on fractal property
- 通信学报 2020年41卷第7期页码：204-212
- 作者机构：
  
  南昌航空大学信息工程学院，江西南昌 330063
- 作者简介：
  
  [ "张胜（1968- ），男，湖北黄冈人，博士，南昌航空大学副教授，主要研究方向为复杂系统、复杂网络、无线传感器网络等" ]
  [ "戴维凯（1994- ），男，广东惠州人，南昌航空大学硕士生，主要研究方向为复杂网络、分形理论等" ]
  [ "吴锋（1996- ），男，湖北黄冈人，南昌航空大学硕士生，主要研究方向为复杂网络、无线传感器网络、分形理论等" ]
  [ "蓝文祥（1996- ），男，江西高安人，南昌航空大学硕士生，主要研究方向为复杂网络、分形理论等" ]
- 基金信息：
  
  国家自然科学基金资助项目(61661037);江西省教育厅科技基金资助项目(GJJ170575);南昌航空大学研究生创新专项资金资助项目(YC2018018)
- DOI：10.11959/j.issn.1000-436x.2020118
  中图分类号： O157.5
- 网络出版日期：2020-07，
  
  纸质出版日期：2020-07-25
- 稿件说明：
移动端阅览
张胜, 戴维凯, 吴锋, 等. 基于分形特性的复杂网络全局效率估计方法[J]. 通信学报, 2020,41(7):204-212.

Sheng ZHANG, Weikai DAI, Feng WU, et al. Global efficiency estimation method of complex network based on fractal property[J]. Journal on communications, 2020, 41(7): 204-212.
张胜, 戴维凯, 吴锋, 等. 基于分形特性的复杂网络全局效率估计方法[J]. 通信学报, 2020,41(7):204-212. DOI： 10.11959/j.issn.1000-436x.2020118.

Sheng ZHANG, Weikai DAI, Feng WU, et al. Global efficiency estimation method of complex network based on fractal property[J]. Journal on communications, 2020, 41(7): 204-212. DOI： 10.11959/j.issn.1000-436x.2020118.

摘要

针对大型网络中效率计算时间复杂度高、计算耗时长的问题，提出一种基于分形特性的网络效率估计方法。利用复杂网络拓扑结构的分形特性，分析网络效率与节点关联和的关系，用部分节点关联和来估计网络全局效率。此外，为了快速判断复杂网络的分形特性，提出基于节点关联和的分形特性判别方法。在构造网络和真实网络中进行实验分析，结果表明，所提方法能准确有效地估算网络全局效率，比原始的网络效率计算方法可缩减不低于90%的计算时间。

Abstract

A method of network efficiency estimation based on fractal property was proposed for solving the problems of high complexity and time-consuming calculation of efficiency in large scale networks.Considering the fractal properties of complex network topology

the relationship between network efficiency and node correlation sum was analyzed

and the global network efficiency was estimated by partial nodes.Besides

to rapidly find the fractal properties of complex networks

a fractal property discrimination method based on node correlation sum was proposed.The experimental analysis in the construction network and the real-world network show that the proposed method can accurately and effectively estimate the global efficiency of the network

which reduces the calculation time by at least 90% compared with the original method.

关键词

Keywords

references

BARABÁSI A L , PÓSFAI M . Network science [M ] . Cambridge : Cambridge University PressPress , 2016 .

LATORA V , MARCHIORI M . Efficient behavior of small-world networks [J ] . Physical Review Letters , 2001 , 87 ( 19 ): 3 - 6 .

HÉBERT-DUFRESNE L , ALLARD A , YOUNG J , et al . Global efficiency of local immunization on complex networks [J ] . Scientific Reports , 2013 ,( 3 ):2171.

AVENA-KOENIGSBERGER A , MISIC B , SPORNS O . Communication dynamics in complex brain networks [J ] . Nature Reviews Neuroscience , 2018 , 19 ( 1 ): 17 - 33 .

BEATY R E , KAUFMAN S B , BENEDEK M , et al . Personality and complex brain networks:the role of openness to experience in default network efficiency [J ] . Human brain mapping , 2016 , 37 ( 2 ): 773 - 779 .

周漩 , 张凤鸣 , 周卫平 , 等 . 利用节点效率评估复杂网络功能鲁棒性 [J ] . 物理学报 , 2012 , 61 ( 19 ): 1 - 7 .

ZHOU X , ZHANG F P , ZHOU W P , et al . Evaluating complex network functional robustness by node efficiency [J ] . Acta Physica Sinica , 2012 , 61 ( 19 ): 1 - 7

EK B , VERSCHNEIDER C , NARAYAN D A . Efficiency of star-like graphs and the Atlanta subway network [J ] . Physica A:Statistical Mechanics and Its Applications , 2013 , 392 ( 21 ): 5481 - 5489 .

ZHANG L , QIN J , HE Y , et al . Network-level optimization method for road network maintenance programming based on network efficiency [J ] . Journal of Central South University , 2015 , 22 ( 12 ): 4882 - 4889 .

LATORA V , MARCHIORI M . Economic small-world behavior in weighted networks [J ] . The European Physical Journal B-Condensed Matter and Complex Systems , 2003 , 32 ( 2 ): 249 - 263 .

BOMPARD E , WU D , XUE F . Structural vulnerability of power systems:a topological approach [J ] . Electric Power Systems Research , 2011 , 81 ( 7 ): 1334 - 1340 .

WANG S , DU Y , DENG Y . A new measure of identifying influential nodes:efficiency centrality [J ] . Communications in Nonlinear Science and Numerical Simulation , 2017 ( 47 ): 151 - 163 .

WANG Y , WANG S , DENG Y . A modified efficiency centrality to identify influential nodes in weighted networks [J ] . Pramana , 2019 , 92 ( 4 ):68.

HOUGARDY S . The Floyd-Warshall algorithm on graphs with negative cycles [J ] . Information Processing Letters , 2010 , 110 ( 8-9 ): 279 - 281 .

SONG C , HAVLIN S , MAKSE H A . Self-similarity of complex networks [J ] . Nature , 2005 , 433 ( 7024 ): 392 - 395 .

SONG C , HAVLIN S , MAKSE H A . Origins of fractality in the growth of complex networks [J ] . Nature Physics , 2006 , 2 ( 4 ): 275 - 281 .

DUAN S , WEN T , JIANG W . A new information dimension of complex network based on Rényi entropy [J ] . Physica A:Statistical Mechanics and Its Applications , 2019 ( 516 ): 529 - 542 .

LEI M , LIU L , WEI D . An improved method for measuring the complexity in complex networks based on structure entropy [J ] . IEEE Access , 2019 ,( 7 ): 159190 - 159198 .

ROSENBERG E . Maximal entropy coverings and the information dimension of a complex network [J ] . Physics Letters A , 2017 , 381 ( 6 ): 574 - 580 .

ZHANG Q , LI M , DENG Y . Measure the structure similarity of nodes in complex networks based on relative entropy [J ] . Physica A:Statistical Mechanics and Its Applications , 2018 ( 491 ): 749 - 763 .

SHANKER O . Defining dimension of a complex network [J ] . Modern Physics Letters B , 2007 , 21 ( 6 ): 321 - 326 .

SHANKER O . Graph zeta function and dimension of complex network [J ] . Modern Physics Letters B , 2007 , 21 ( 11 ): 639 - 644 .

WEI D , WEI B , ZHANG H , et al . A generalized volume dimension of complex networks [J ] . Journal of Statistical Mechanics:Theory and Experiment , 2014 , 2014 ( 10 ):P10039.

WEN T , JIANG W . An information dimension of weighted complex networks [J ] . Physica A:Statistical Mechanics and Its Applications. , 2018 ( 501 ): 388 - 399 .

PU J , CHEN X , WEI D , et al . Identifying influential nodes based on local dimension [J ] . Europhysics Letters , 2014 , 107 ( 1 ):10010.

BIAN T , DENG Y . Identifying influential nodes in complex networks:A node information dimension approach [J ] . Chaos:an Interdisciplinary Journal of Nonlinear Science , 2018 , 28 ( 4 ):43109.

WEN T , DENG Y . Identification of influencers in complex networks by local information dimensionality [J ] . Information Sciences , 2020 ( 512 ): 549 - 562 .

WEN T , PELUSI D , DENG Y . Vital spreaders identification in complex networks with multi-local dimension [J ] . Knowledge-Based Systems , 2020 :105717.

关世杰 , 赵海 . 互联网中路由级和IP级拓扑分形特征分析 [J ] . 通信学报 , 2013 , 34 ( 11 ): 162 - 170 .

GUAN S J , ZHAO H . Analysis of fractal characteristic of internet router-level and IP-level topology [J ] . Journal on Communications , 2013 , 34 ( 11 ): 162 - 170 .

DIJKSTRA E W . A note on two problems in connexion with graphs [J ] . Numerische Mathematik , 1959 , 1 ( 1 ): 269 - 271 .

SONG C , GALLOS L K , HAVLIN S , et al . How to calculate the fractal dimension of a complex network:the box covering algorithm [J ] . Journal of Statistical Mechanics:Theory and Experiment , 2007 , 2007 ( 3 ):P03006.

LACASA L , GÓMEZ-GARDEÑES J . Correlation dimension of complex networks [J ] . Physical Review Letters , 2013 , 110 ( 16 ): 1 - 5 .

WANG X , LIU Z , WANG M . The correlation fractal dimension of complex networks [J ] . International Journal of Modern Physics C , 2013 , 24 ( 5 ):1350033.

姜建国 , 曹建中 , 高玉明 . 信号与系统分析基础 [M ] . 北京 : 清华大学出版社 , 2006 .

JIANG J G , CAO J Z , GAO Y M . Fundamentals of signal and system analysis [M ] . Beijing : Tsinghua University PressPress , 2006 .

EK B , VERSCHNEIDER C , NARAYAN D A . Global efficiency of graphs [J ] . AKCE International Journal of Graphs and Combinatorics , 2015 , 12 ( 1 ): 1 - 13 .

ACHARD S , BULLMORE E . Efficiency and cost of economical brain functional networks [J ] . PLOS Computational Biology , 2007 , 3 ( 2 ):e17.

CLAUSET A , SHALIZI C R , NEWMAN M E J . Power-law distributions in empirical data [J ] . SIAM Review , 2009 , 51 ( 4 ): 661 - 703 .

KITSAK M , HAVLIN S , PAUL G , et al . Betweenness centrality of fractal and nonfractal scale-free model networks and tests on real networks Maksim [J ] . Physical Review E , 2007 , 75 ( 5 ):056115.

浏览量

429

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于动态图嵌入的车联网拓扑控制

基于高阶路径相似度的复杂网络链路预测方法

基于改进灰狼优化的复杂网络重要节点识别算法

基于无标度网络的车联网连通性研究

基于资源传输匹配度的复杂网络链路预测方法