计算机科学 ›› 2021, Vol. 48 ›› Issue (3): 136-143.doi: 10.11896/jsjkx.200700159

• 数据库&大数据&数据科学 • 上一篇    下一篇

带权图的多重分形度量

刘胜久, 李天瑞, 谢鹏, 刘佳   

  1. 西南交通大学信息科学与技术学院 成都611756
    四川省云计算与智能技术高校重点实验室 成都611756
  • 收稿日期:2020-07-26 修回日期:2020-08-28 出版日期:2021-03-15 发布日期:2021-03-05
  • 通讯作者: 李天瑞(trli@swjtu.edu.cn)
  • 作者简介:liushengjiu2008@163.com
  • 基金资助:
    国家自然科学基金(61573292)

Measure for Multi-fractals of Weighted Graphs

LIU Sheng-jiu, LI Tian-rui, XIE Peng, LIU Jia   

  1. School of Information Science and Technology,Southwest Jiaotong University,Chengdu 611756,China
    Sichuan Key Lab of Cloud Computing and Intelligent Technique,Chengdu 611756,China
  • Received:2020-07-26 Revised:2020-08-28 Online:2021-03-15 Published:2021-03-05
  • About author:LIU Sheng-jiu,born in 1988,Ph.D,post Ph.D.His main research interests include complex network,natural language processing,data mining,etc.
    LI Tian-rui,born in 1969,Ph.D,professor,Ph.D supervisor,is a member of China Computer Federation.His main research interests include data mining and knowledge discovery,granular computing and rough sets,cloud computing and big data,etc.
  • Supported by:
    National Natural Science Foundation of China (61573292).

摘要: 分形维数及多重分形是分形理论的重要研究内容。复杂网络的多重分形已经得到了较为深入的研究,但对复杂网络多重分形的度量目前并没有可行的方法。带权图是复杂网络研究的重要对象,其中的节点权重及边权重可以为正实数、负实数、纯虚数及复数等多种不同的类型。除节点权重及边权重均为正实数的情形外,其他类型的带权图都具有多重分形特性,且均具有无穷多个复数形式的网络维数。通过对带权图多重分形的研究,文中给出了15种具有多重分形特性的带权图多重分形维数的模所构成的集合,并采用集合的势对带权图的多重分形特性进行度量。研究表明,15种带权图多重分形维数的模所构成的集合均是可数集,其中有2种集合是2重集合,另外13种集合是通常意义上的集合,而且所有的集合均是等势的,其势均为0

关键词: 带权图, 度量, 多重分形, 分形理论, 分形维数, 复杂网络, 基数

Abstract: Fractal dimension and multi-fractal are important research contents of fractal theory.The multi-fractal of complex networks has been studied in depth,while there is no feasible method to measure the multi-fractal of complex networks.Weighted graph is an important research object of complex network.Both node weight and edge weight in weighted graphs can be positive real number,negative real number,pure imaginary number and complex number,and so on.Among all types of weighted graphs,except the weighted graphs with both node weight and edge weight being positive real numbers,other types of weighted graphs share multi-fractals and append with infinity complex network dimensions.Through the study of multi-fractals of weighted graphs,this paper presents modulus of infinity complex network dimensions of all 15 weighted graphs that share multi-fractal,and measures multi-fractal of them by cardinality of sets obtained from modulus of infinity complex network dimensions of them.It shows that all sets obtained from modulus of infinity complex network dimensions of weighted graphs share multi-fractal are countable sets,while 2 are multisets,and the other 13 are ordinary sets.Moreover,all sets,regardless of multisets or ordinary sets,are equipotent with cardinality of 0.

Key words: Cardinality, Complex network, Fractal dimension, Fractal theory, Measure, Multi-fractals, Weighted graph

中图分类号: 

  • TP393
[1]ERDO S,RENYI A.On random graphs I[J].PublicationesMathematicae,1959,6:290-297.
[2]WATTS D J,STROGATZ S H.Collective dynamics of ‘small-world’ networks[J].Nature,1998,393:440-442.
[3]NEWMAN M E J,WATTS D J.Renormalization group analysis of the small-world network model[J].Physics Letter A,1999,293:341-346.
[4]BARABASI A L,ALBERT R.Emergence of scaling in random networks[J].Science,1999,286:509-512.
[5]SONG C,JALVIN S,MAKSE H A.Self-similarity of complex networks[J].Nature,2005,433:392-395.
[6]LIU S J,LI T R,HONG S J,et al.Complex network construction based on matrix operation[J].Scientia Sinica Informationis,2016,46(5):610-626.
[7]LIU S J,LI T R,LIU X W.Network network dimension:A new measure for complex networks[J].Computer Science,2019,46(1):51-56.
[8]LIU S J,LI T R,ZHU J,et al.Research on multi-fractals ofweighted graph[J].Journal of Nanjing University(Natural Scien-ces),2020,56(1):85-97.
[9]ZHANG X D,LI Z L.Graph Theory and Its Applications[M].Beijing:Higher Education Press,2005.
[10]MANDELBROT B.Les Objets Fractals:Forme,Hasard et Di-mension[M].Paris and Montreal:Flammarion,1975.
[11]HUREWICZ W,WALLMAN H.Dimension Theory[M].Princeton:Princeton University Press,1948.
[12]BALKA R,BUCZOLICH Z,ELEKES M.A new fractal dimension:The topological Hausdorff dimension[J].Advances in Mathematics,2015,274(1):881-927.
[13]MAULDIN R D,WILLIAMS S C.On the Hausdorff dimension of some graphs[J].Transactions of the American Mathematical Society,1986,298:793-803.
[14]SREENIVASAN K R,MENEVEAU C.The fractal facets ofturbulence[J].Journal of Fluid Mechanics,1986,173(173):357-386.
[15]LIANG J J,LI G S,ZHANG Z H,et al.Calculation Method for Fractal Dimension of Spherical Flames[J].Journal of Combustion Science and Technology,2016,22(1):26-32.
[16]HARTE D.Multifractals:Theory and Applications[M].Chap-man & Hall/CRC,2001.
[17]ZHAO J T,CHEN Y G,LI S C.Bi-fractal structure and evolution of the Beijing-Tianjin-Hebei region urban land-use patterns[J].Progress in Geography,2019,38(1):77-87.
[18]CHEN Y G.Monofractal,multifractals,and self-affine fractals in urban studies[J].Progress in Geography,2019,38(1):38-49.
[19]LIU J L,WANG J,YU Z G,et al.Fractal and multifractal analyses of bipartite networks[J].Scientific Reports,2017(7):45588.
[20]SONG Y Q,LIU J L,YU Z G,et al.Multifractal analysis of weighted networks by a modified sandbox algorithm[J].Scientific Reports,2015(5):17628.
[1] 郑文萍, 刘美麟, 杨贵.
一种基于节点稳定性和邻域相似性的社区发现算法
Community Detection Algorithm Based on Node Stability and Neighbor Similarity
计算机科学, 2022, 49(9): 83-91. https://doi.org/10.11896/jsjkx.220400146
[2] 姜胜腾, 张亦弛, 罗鹏, 刘月玲, 曹阔, 赵海涛, 魏急波.
语义通信系统的性能度量指标分析
Analysis of Performance Metrics of Semantic Communication Systems
计算机科学, 2022, 49(7): 236-241. https://doi.org/10.11896/jsjkx.211200071
[3] 杨波, 李远彪.
数据科学与大数据技术课程体系的复杂网络分析
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
[4] 侯夏晔, 陈海燕, 张兵, 袁立罡, 贾亦真.
一种基于支持向量机的主动度量学习算法
Active Metric Learning Based on Support Vector Machines
计算机科学, 2022, 49(6A): 113-118. https://doi.org/10.11896/jsjkx.210500034
[5] 何茜, 贺可太, 王金山, 林绅文, 杨菁林, 冯玉超.
比特币实体交易模式分析
Analysis of Bitcoin Entity Transaction Patterns
计算机科学, 2022, 49(6A): 502-507. https://doi.org/10.11896/jsjkx.210600178
[6] 王宇飞, 陈文.
基于DECORATE集成学习与置信度评估的Tri-training算法
Tri-training Algorithm Based on DECORATE Ensemble Learning and Credibility Assessment
计算机科学, 2022, 49(6): 127-133. https://doi.org/10.11896/jsjkx.211100043
[7] 王本钰, 顾益军, 彭舒凡, 郑棣文.
融合动态距离和随机竞争学习的社区发现算法
Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning
计算机科学, 2022, 49(5): 170-178. https://doi.org/10.11896/jsjkx.210300206
[8] 陈世聪, 袁得嵛, 黄淑华, 杨明.
基于结构深度网络嵌入模型的节点标签分类算法
Node Label Classification Algorithm Based on Structural Depth Network Embedding Model
计算机科学, 2022, 49(3): 105-112. https://doi.org/10.11896/jsjkx.201000177
[9] 赵学磊, 季新生, 刘树新, 李英乐, 李海涛.
基于路径连接强度的有向网络链路预测方法
Link Prediction Method for Directed Networks Based on Path Connection Strength
计算机科学, 2022, 49(2): 216-222. https://doi.org/10.11896/jsjkx.210100107
[10] 李家文, 郭炳晖, 杨小博, 郑志明.
基于信息传播的致病基因识别研究
Disease Genes Recognition Based on Information Propagation
计算机科学, 2022, 49(1): 264-270. https://doi.org/10.11896/jsjkx.201100129
[11] 冯霞, 胡志毅, 刘才华.
跨模态检索研究进展综述
Survey of Research Progress on Cross-modal Retrieval
计算机科学, 2021, 48(8): 13-23. https://doi.org/10.11896/jsjkx.200800165
[12] 杨杏丽.
分类学习算法的性能度量指标综述
Survey for Performance Measure Index of Classification Learning Algorithm
计算机科学, 2021, 48(8): 209-219. https://doi.org/10.11896/jsjkx.200900216
[13] 穆俊芳, 郑文萍, 王杰, 梁吉业.
基于重连机制的复杂网络鲁棒性分析
Robustness Analysis of Complex Network Based on Rewiring Mechanism
计算机科学, 2021, 48(7): 130-136. https://doi.org/10.11896/jsjkx.201000108
[14] 王辉, 朱国宇, 申自浩, 刘琨, 刘沛骞.
基于用户偏好和位置分布的假位置生成方法
Dummy Location Generation Method Based on User Preference and Location Distribution
计算机科学, 2021, 48(7): 164-171. https://doi.org/10.11896/jsjkx.200800069
[15] 胡军, 王雨桐, 何欣蔚, 武晖栋, 李慧嘉.
基于复杂网络的全球航空网络结构分析与应用
Analysis and Application of Global Aviation Network Structure Based on Complex Network
计算机科学, 2021, 48(6A): 321-325. https://doi.org/10.11896/jsjkx.200900112
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!