Computer Science ›› 2019, Vol. 46 ›› Issue (1): 51-56.doi: 10.11896/j.issn.1002-137X.2019.01.008

• CCDM2018 • Previous Articles     Next Articles

Network Dimension:A New Measure for Complex Networks

LIU Sheng-jiu1,2, LI Tian-rui1,2, LIU Xiao-wei3   

  1. (School of Information Science and Technology,Southwest Jiaotong University,Chengdu 611756,China)1
    (Sichuan Key Lab of Cloud Computing and Intelligent Technique,Chengdu 611756,China)2
    (Department of Mathematics and Computer Science,Nanchang Normal University,Nanchang 330032,China)3
  • Received:2018-06-29 Online:2019-01-15 Published:2019-02-25

Abstract: How to measure complex networks has always received much attention.This paper proposed a new method based on the analysis of fractal dimension of self-similarity complex networks,named network dimension,to measure complex networks.Network dimension is expressed as the division of logarithm of the sum of edges’ weights and logarithm of the sum of nodes’ weights of complex networks.The weights of both edge and node are extended to real and complex number fields.The calculation methods of network dimensions of weighted networks with different types of weights were presented.Finally,several representative classical complex network models were taken as examples to discuss some properties of the proposed network dimension.

Key words: Complex network, Self-similarity network, Fractal dimension, Network dimension

CLC Number: 

  • TP391
[1]ERDOS P,RENYI A.On random graphs[J].Publications Mathe-maticae,1959,6(4):290-297.<br /> [2]WATTS D J,STROGATZ S H.Collective dynamics of ‘small-world’ networks[J].Nature,1998,393(6684):440-442.<br /> [3]NEWMAN M E J,WATTS D J.Renormalization group analysis of the small-world network model[J].Physics Letter A,1999,263(4-6):341-346.<br /> [4]BARABASI A L,ALBERT R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512.<br /> [5]LIU S J,LI T R,HONG X J,et al.Complex network construction based on matrix operation[J].Scientia Sinica Informationis,2016,46(5):610-626.(in Chinese)<br /> 刘胜久,李天瑞,洪西进,等.基于矩阵运算的复杂网络构建方法研究[J].中国科学:信息科学,2016,46(5):610-626.<br /> [6]LIU S J,LI T R,HONG X J,et al.Hypernetwork model and its properties[J].Journal of Frontiers of Computer Science and Technology,2017,11(2):194-211.(in Chinese)<br /> 刘胜久,李天瑞,洪西进,等.超网络模型构建及特性分析[J].计算机科学与探索,2017,11(2):194-211.<br /> [7]ZHU D Z,WU J,TAN Y J,et al.Degree-Rank function:A new statistic characteristic of complex network[J].Complex System and Complex Science,2006,3(4):28-34.(in Chinese)<br /> 朱大智,吴俊,谭跃进,等.度秩函数——一个新的复杂网络统计特征[J].复杂系统与复杂性科学,2006,3(4):28-34.<br /> [8]XU Z B,WANG J Y,ZHANG D S,et al.Fractal Dimension Description of Complexity of fault network in coal mines[J].Journal of China Coal Socity,1996,21(4):358-363.(in Chinese)<br /> 徐志斌,王继尧,张大顺,等.煤矿断层网络复杂程度的分维描述[J].煤炭学报,1996,21(4):358-363.<br /> [9]ZHENG X,CHEN J P,SHAO J L,et al.Analysis on topological properties of Beijing urban public transit based on complex network theory[J].Acta Physica Sinica,2012,61(19):95-105.(in Chinese)<br /> 郑啸,陈建平,邵佳丽,等.基于复杂网络理论的北京公交网络拓扑性质分析[J].物理学报,2012,61(19):95-105.<br /> [10]张先迪,李正良.图论及其应用[M].北京:高等教育出版社,2005.<br /> [11]NEWMAN M E J.The structure and function of complex networks[J].SIAM Review,2003,45(2):167-256.<br /> [12]MANDELBROT B.How long is the coast of britain? Statistical self-similarity and fractional dimension[J].Science,1967,156(3775):636-638.<br /> [13]BALKA R,BUCZOLICH Z,ELEKES M.A new fractal dimension:The topological Hausdorff dimension[J].Advances in Mathematics,2015,274(1):881-927.<br /> [14]SREENIVASAN K R,MENEVEAU C.The fractal facets of turbulence[J].Journal of Fluid Mechanics,1986,173(173):357-386.<br /> [15]HARTE D.Multifractals:Theory and Applications[M].Chapman & Hall/CRC,2001.<br /> [16]SONG C M,HAVLIN S,MAKSE H A.Self-similarity of complex networks[J].Nature,2005,433(7024):392-395.<br /> [17]SONG C M,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 & Experiment,2007,2007(3):297-316.<br /> [18]KIM J S,GOH K I,SALVI G,et al.Fractality in complex networks:critical and supercritical skeletons[J].Physical Review E,2007,75(2):016110.<br /> [19]ZHOU W X,JIANG Z Q,SORNETTE D.Exploring self-similarity of complex cellular networks:The edge-covering method with simulated annealing and log-periodic sampling[J].Physica a Statistical Mechanics & Its Applications,2006,375(2):741-752.<br /> [20]GAO L,HU Y,DI Z.Accuracy of the ball-covering approach for fractal dimensions of complex networks and a rank-driven algorithm[J].Physical Review E Statistical Nonlinear &Soft Matter Physics,2008,78(4 Pt 2):046109.<br /> [21]LIU J L,YU Z G,ANH V.Topological properties and fractal analysis of a recurrence network constructed from fractional Brownian motions[J].Physical Review E Statistical Nonlinear &Soft Matter Physics,2014,89(3):032814.<br /> [22]WEI D J,LIU Q,ZHANG H X,et al.Box-covering algorithm for fractal dimension of weighted networks[J].Scientific Report,2013,3(6157):3049.<br /> [23]LIU S J,LI T R,HONG X J,et al.Supernetwork based on matrix operation and its properties [J].CAAI Transactions on Intelligent Systems,2018,13(3):359-365.(in Chinese)<br /> 刘胜久,李天瑞,洪西进,等.基于矩阵运算的超网络构建方法研究及特性分析[J].智能系统学报,2018,13(3):359-365.
[1] YANG Chao, LIU Zhi. Study on Complex Network Cascading Failure Based on Totally Asymmetric Simple Exclusion Process Model [J]. Computer Science, 2020, 47(9): 265-269.
[2] ZHANG Meng-yue, HU Jun, YAN Guan, LI Hui-jia. Analysis of China’s Patent Application Concern Based on Visibility Graph Network [J]. Computer Science, 2020, 47(8): 189-194.
[3] ZHANG Qing-qi, LIU Man-dan. Multi-objective Five-elements Cycle Optimization Algorithm for Complex Network Community Discovery [J]. Computer Science, 2020, 47(8): 284-290.
[4] WANG Hui, LE Zi-chun, GONG Xuan, WU Yu-kun, ZUO Hao. Review of Link Prediction Methods Based on Feature Classification [J]. Computer Science, 2020, 47(8): 302-312.
[5] DONG Ming-gang, GONG Jia-ming and JING Chao. Multi-obJective Evolutionary Algorithm Based on Community Detection Spectral Clustering [J]. Computer Science, 2020, 47(6A): 461-466.
[6] YUAN Rong, SONG Yu-rong, MENG Fan-rong. Link Prediction Method Based on Weighted Network Topology Weight [J]. Computer Science, 2020, 47(5): 265-270.
[7] MA Yang, CHENG Guang-quan, LIANG Xing-xing, LI Yan, YANG Yu-ling, LIU Zhong. Improved SDNE in Weighted Directed Network [J]. Computer Science, 2020, 47(4): 233-237.
[8] ZHANG Hu, ZHOU Jing-jing, GAO Hai-hui, WANG Xin. Network Representation Learning Method on Fusing Node Structure and Content [J]. Computer Science, 2020, 47(12): 119-124.
[9] RUAN Zi-rui,RUAN Zhong-yuan,SHEN Guo-jiang. Study of TASEP Model Based on Road Networks [J]. Computer Science, 2020, 47(1): 265-269.
[10] ZHAO Lei, ZHOU Jin-he. ICN Energy Efficiency Optimization Strategy Based on Content Field of Complex Networks [J]. Computer Science, 2019, 46(9): 137-142.
[11] CHEN Hang-yu, LI Hui-jia. Analysis of Characteristics and Applications of Chinese Aviation Complex Network Structure [J]. Computer Science, 2019, 46(6A): 300-304.
[12] LIU Xiao-dong, WEI Hai-ping, CAO Yu. Modeling and Stability Analysis for SIRS Model with Network Topology Changes [J]. Computer Science, 2019, 46(6A): 375-379.
[13] ZHANG Sen, LIU Wen-qi, ZHAO Ning. Research of Consensus in Multi-agent Systems on Complex Network [J]. Computer Science, 2019, 46(4): 95-99.
[14] SHAN Na, LI Long-jie, LIU Yu-yang, CHEN Xiao-yun. Link Prediction Based on Correlation of Nodes’ Connecting Patterns [J]. Computer Science, 2019, 46(12): 20-25.
[15] BIN Sheng, SUN Geng-xin. Collaborative Filtering Recommendation Algorithm Based on Multi-relationship Social Network [J]. Computer Science, 2019, 46(12): 56-62.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] . [J]. Computer Science, 2018, 1(1): 1 .
[2] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[3] 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 .
[4] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[5] 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 .
[6] 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 .
[7] 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 .
[8] 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 .
[9] 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 .
[10] 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 .