Global efficiency estimation method of complex network based on fractal property

Sheng ZHANG; Weikai DAI; Feng WU; Wenxiang LAN

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

您当前的位置：

首页 >

文章列表页 >

Global efficiency estimation method of complex network based on fractal property

Correspondences | 更新时间：2024-06-05

- Global efficiency estimation method of complex network based on fractal property
- Journal on Communications Vol. 41, Issue 7, Pages: 204-212(2020)
- 作者机构：
  
  南昌航空大学信息工程学院，江西南昌 330063
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(61661037);Science and Technology Project of Jiangxi Province Education Department(GJJ170575);Nanchang Hangkong University Graduate Innovation Special Foundation(YC2018018)
- DOI：10.11959/j.issn.1000-436x.2020118
  CLC： O157.5
- Online First：2020-07，
  
  Published：25 July 2020
- 稿件说明：
移动端阅览
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：

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.

Views

1134

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Topology control based on dynamic graph embedding in Internet of vehicles

Link prediction method based on the similarity of high path

Key node identification algorithm for complex network based on improved grey wolf optimization

Connectivity analysis of IoV based on scale-free network

Link prediction method based on matching degree of resource transmission for complex network

Related Author

Zhenjiang DONG

Mengting CHEN

Xiaoxuan HU

Jin QI

Jiazheng YIN

Yanfei SUN

Renyong CHI

Bao WU

Related Institution

College of Computer, Nanjing University of Posts and Telecommunications

School of Communications and Information Engineering, Nanjing University of Posts and Telecommunications

School of Internet of Things, Nanjing University of Posts and Telecommunications

Jiangsu Engineering Research Center of HPC and Intelligent Processing

China Institute for Small and Medium Enterprises, Zhejiang University of Technology

AI问答

⁰