计算机科学 ›› 2019, Vol. 46 ›› Issue (1): 51-56.doi: 10.11896/j.issn.1002-137X.2019.01.008

• 2018 年第七届中国数据挖掘会议 • 上一篇    下一篇

网络维数:一种度量复杂网络的新方法

刘胜久1,2, 李天瑞1,2, 刘小伟3   

  1. (西南交通大学信息科学与技术学院 成都611756)1
    (四川省云计算与智能技术高校重点实验室 成都611756)2
    (南昌师范学院数学与计算机科学系 南昌330032)3
  • 收稿日期:2018-06-29 出版日期:2019-01-15 发布日期:2019-02-25
  • 作者简介:刘胜久(1988-),男,博士后,主要研究方向为复杂网络、自然语言处理等,E-mail:liushengjiu2008@163.com;李天瑞(1969-),男,博士,教授,博士生导师,主要研究方向为智能信息处理、粗糙集与粒计算等,E-mail:trli@swjtu.edu.cn(通信作者);刘小伟(1978-),男,硕士,副教授,主要研究方向为复杂网络、智能信息处理、粗糙集等。
  • 基金资助:
    国家自然科学基金项目(61573292,61262058,61562063),江西省教育厅科技项目(GJJ171109,GJJ161241)资助

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, Fractal dimension, Network dimension, Self-similarity network

中图分类号: 

  • 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] 郑文萍, 刘美麟, 杨贵.
一种基于节点稳定性和邻域相似性的社区发现算法
Community Detection Algorithm Based on Node Stability and Neighbor Similarity
计算机科学, 2022, 49(9): 83-91. https://doi.org/10.11896/jsjkx.220400146
[2] 杨波, 李远彪.
数据科学与大数据技术课程体系的复杂网络分析
Complex Network Analysis on Curriculum System of Data Science and Big Data Technology
计算机科学, 2022, 49(6A): 680-685. https://doi.org/10.11896/jsjkx.210800123
[3] 何茜, 贺可太, 王金山, 林绅文, 杨菁林, 冯玉超.
比特币实体交易模式分析
Analysis of Bitcoin Entity Transaction Patterns
计算机科学, 2022, 49(6A): 502-507. https://doi.org/10.11896/jsjkx.210600178
[4] 王本钰, 顾益军, 彭舒凡, 郑棣文.
融合动态距离和随机竞争学习的社区发现算法
Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning
计算机科学, 2022, 49(5): 170-178. https://doi.org/10.11896/jsjkx.210300206
[5] 陈世聪, 袁得嵛, 黄淑华, 杨明.
基于结构深度网络嵌入模型的节点标签分类算法
Node Label Classification Algorithm Based on Structural Depth Network Embedding Model
计算机科学, 2022, 49(3): 105-112. https://doi.org/10.11896/jsjkx.201000177
[6] 赵学磊, 季新生, 刘树新, 李英乐, 李海涛.
基于路径连接强度的有向网络链路预测方法
Link Prediction Method for Directed Networks Based on Path Connection Strength
计算机科学, 2022, 49(2): 216-222. https://doi.org/10.11896/jsjkx.210100107
[7] 李家文, 郭炳晖, 杨小博, 郑志明.
基于信息传播的致病基因识别研究
Disease Genes Recognition Based on Information Propagation
计算机科学, 2022, 49(1): 264-270. https://doi.org/10.11896/jsjkx.201100129
[8] 穆俊芳, 郑文萍, 王杰, 梁吉业.
基于重连机制的复杂网络鲁棒性分析
Robustness Analysis of Complex Network Based on Rewiring Mechanism
计算机科学, 2021, 48(7): 130-136. https://doi.org/10.11896/jsjkx.201000108
[9] 胡军, 王雨桐, 何欣蔚, 武晖栋, 李慧嘉.
基于复杂网络的全球航空网络结构分析与应用
Analysis and Application of Global Aviation Network Structure Based on Complex Network
计算机科学, 2021, 48(6A): 321-325. https://doi.org/10.11896/jsjkx.200900112
[10] 王学光, 张爱新, 窦炳琳.
复杂网络上的非线性负载容量模型
Non-linear Load Capacity Model of Complex Networks
计算机科学, 2021, 48(6): 282-287. https://doi.org/10.11896/jsjkx.200700040
[11] 马媛媛, 韩华, 瞿倩倩.
基于节点亲密度的重要性评估算法
Importance Evaluation Algorithm Based on Node Intimate Degree
计算机科学, 2021, 48(5): 140-146. https://doi.org/10.11896/jsjkx.200300184
[12] 殷子樵, 郭炳晖, 马双鸽, 米志龙, 孙怡帆, 郑志明.
群智体系网络结构的自治调节:从生物调控网络结构谈起
Autonomous Structural Adjustment of Crowd Intelligence Network: Begin from Structure of Biological Regulatory Network
计算机科学, 2021, 48(5): 184-189. https://doi.org/10.11896/jsjkx.210200161
[13] 刘胜久, 李天瑞, 谢鹏, 刘佳.
带权图的多重分形度量
Measure for Multi-fractals of Weighted Graphs
计算机科学, 2021, 48(3): 136-143. https://doi.org/10.11896/jsjkx.200700159
[14] 龚追飞, 魏传佳.
基于改进AdaBoost算法的复杂网络链路预测
Link Prediction of Complex Network Based on Improved AdaBoost Algorithm
计算机科学, 2021, 48(3): 158-162. https://doi.org/10.11896/jsjkx.200600075
[15] 龚追飞, 魏传佳.
基于拓扑相似和XGBoost的复杂网络链路预测方法
Complex Network Link Prediction Method Based on Topology Similarity and XGBoost
计算机科学, 2021, 48(12): 226-230. https://doi.org/10.11896/jsjkx.200800026
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!