计算机科学 ›› 2019, Vol. 46 ›› Issue (1): 51-56.doi: 10.11896/j.issn.1002-137X.2019.01.008
刘胜久1,2, 李天瑞1,2, 刘小伟3
LIU Sheng-jiu1,2, LI Tian-rui1,2, LIU Xiao-wei3
摘要: 如何对复杂网络进行刻画与度量,一直是人们关注的热点。在研究自相似复杂网络分形维数的基础上,提出了一种度量复杂网络的新方法——网络维数,即复杂网络边权重和的对数值与节点权重和的对数值的比值,可以将边权重及点权重推广到实数域和复数域;同时给出了不同类型权重对应的网络维数的计算方法;最后以几个代表性的经典复杂网络模型为例,讨论了所提出的网络维数的若干性质。
中图分类号:
[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 |
|