计算机科学 ›› 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: Weighted graph, Complex network, Fractal theory, Fractal dimension, Multi-fractals, Measure, Cardinality

中图分类号: 

  • 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] 龚追飞, 魏传佳. 基于改进AdaBoost算法的复杂网络链路预测[J]. 计算机科学, 2021, 48(3): 158-162.
[2] 梁伟, 段晓东, 徐健锋. 基于差异性度量的基础聚类三支过滤算法[J]. 计算机科学, 2021, 48(1): 136-144.
[3] 杨超, 刘志. 基于TASEP模型的复杂网络级联故障研究[J]. 计算机科学, 2020, 47(9): 265-269.
[4] 张梦月, 胡军, 严冠, 李慧嘉. 基于可见性图网络的中国专利申请关注度分析[J]. 计算机科学, 2020, 47(8): 189-194.
[5] 张清琪, 刘漫丹. 复杂网络社区发现的多目标五行环优化算法[J]. 计算机科学, 2020, 47(8): 284-290.
[6] 王慧, 乐孜纯, 龚轩, 武玉坤, 左浩. 基于特征分类的链路预测方法综述[J]. 计算机科学, 2020, 47(8): 302-312.
[7] 董明刚, 弓佳明, 敬超. 基于谱聚类的多目标进化社区发现算法研究[J]. 计算机科学, 2020, 47(6A): 461-466.
[8] 袁榕, 宋玉蓉, 孟繁荣. 一种基于加权网络拓扑权重的链路预测方法[J]. 计算机科学, 2020, 47(5): 265-270.
[9] 余航, 魏炜, 谭征, 刘惊雷. 基于信任系统的条件偏好协同度量框架[J]. 计算机科学, 2020, 47(4): 74-84.
[10] 李鑫超, 李培峰, 朱巧明. 一种基于改进向量投影距离的知识图谱表示方法[J]. 计算机科学, 2020, 47(4): 189-193.
[11] 马扬, 程光权, 梁星星, 李妍, 杨雨灵, 刘忠. 有向加权网络中的改进SDNE算法[J]. 计算机科学, 2020, 47(4): 233-237.
[12] 王毛妮, 彭长根, 何文竹, 丁兴, 丁红发. 基于图论与互信息量的差分隐私度量模型[J]. 计算机科学, 2020, 47(4): 270-277.
[13] 杨洁,王国胤,李帅. 基于边界域的邻域知识距离度量模型[J]. 计算机科学, 2020, 47(3): 61-66.
[14] 张虎, 周晶晶, 高海慧, 王鑫. 融合节点结构和内容的网络表示学习方法[J]. 计算机科学, 2020, 47(12): 119-124.
[15] 邵阳雪, 孟伟, 孔德珍, 韩林轩, 刘扬. 基于深度学习的特种车辆跨模态检索方法[J]. 计算机科学, 2020, 47(12): 205-209.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 宫法明,朱朋海. 基于自适应隐马尔可夫模型的石油领域文档分词[J]. 计算机科学, 2018, 45(6A): 97 -100 .
[2] 王飞,易绵竹,谭新. 基于本体语义网络的语言理解模型[J]. 计算机科学, 2018, 45(6A): 101 -105 .
[3] 宫法明,李翛然. 基于Neo4j的海量石油领域本体数据存储研究[J]. 计算机科学, 2018, 45(6A): 549 -554 .
[4] 王顺,康达周,江东宇. 本体映射综述[J]. 计算机科学, 2017, 44(9): 1 -10 .
[5] 王旭阳,尉醒醒. 基于本体和局部共现的查询扩展方法[J]. 计算机科学, 2017, 44(1): 214 -218 .
[6] 王立,王欣,马朝东. 一种基于本体KNN的分布式缓存数据交换策略[J]. 计算机科学, 2016, 43(Z11): 316 -319 .
[7] 宋华珠,段文军,刘翔. 基于HBase的本体存储模型[J]. 计算机科学, 2016, 43(6): 39 -43 .
[8] 柯昌博,黄志球,肖甫. 基于本体概念相似度的软件构件检索方法[J]. 计算机科学, 2017, 44(12): 144 -149 .
[9] 毕娅, 原惠群, 初叶萍, 刘慧. 大数据环境下基于公共服务平台的资源多级智能寻租与匹配策略和价值创造[J]. 计算机科学, 2019, 46(2): 42 -49 .
[10] 许飞翔,叶霞,李琳琳,曹军博,王馨. 基于SA-BP算法的本体概念语义相似度综合计算[J]. 计算机科学, 2020, 47(1): 199 -204 .