带权图的多重分形研究

doi:10.13232/j.cnki.jnju.2020.01.010

南京大学学报(自然科学版) ›› 2020, Vol. 56 ›› Issue (1): 85–97.doi: 10.13232/j.cnki.jnju.2020.01.010

带权图的多重分形研究

刘胜久^1,²,李天瑞^1,²(),珠杰³,刘佳^1,²

1. 西南交通大学信息科学与技术学院，成都，611756
2. 四川省云计算与智能技术高校重点实验室，成都，611756
3. 西藏大学信息科学技术学院，拉萨，850000

收稿日期:2019-06-28 出版日期:2020-01-30 发布日期:2020-01-10
通讯作者: 李天瑞 E-mail:trli@swjtu.edu.cn
基金资助:
国家自然科学基金(61573292)

Research on multi⁃fractals of weighted graphs

Shengjiu Liu^1,²,Tianrui Li^1,²(),Jie Zhu³,Jia Liu^1,²

1. School of Information Science and Technology，Southwest Jiaotong University，Chengdu，611756，China
2. Sichuan Key Lab of Cloud Computing and Intelligent Technique，Chengdu，611756，China
3. School of Information Science and Technology，Tibetan University，Lhasa，850000，China

Received:2019-06-28 Online:2020-01-30 Published:2020-01-10
Contact: Tianrui Li E-mail:trli@swjtu.edu.cn

摘要/Abstract

摘要：

自相似特性是复杂网络研究的重点，分形维数是度量其自相似特性的重要工具.针对带权图中节点权重与边权重可以为正实数、负实数、纯虚数及复数等多种不同数值的情形，给出各种不同带权图的多重分形维数，讨论了带权图的多重分形特性.研究表明，在不同类型的带权图中，除节点权重及边权重均为正实数的情形之外，其他类型的带权图均具有多重分形特性.最后分析了这些带权图多重分形维数的性质.

关键词: 复杂网络, 带权图, 自相似, 分形理论, 多重分形

Abstract:

Self?similarity is one focus of research on complex network，while fractal dimension is an important tool for measuring its self?similarity. For the case that both node weight and edge weight in weighted graphs can value among positive real number，negative real number，pure imaginary number and complex number，and so on，this paper purposes fractal dimensions for various weighted graphs and discusses their multi?fractals. It is shown that 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. Finally，the properties of the multi?fractal dimensions of these weighted graphs are analyzed.

Key words: complex network, weighted graph, self?similarity, fractal theory, multi?fractals

中图分类号:

TP391

刘胜久,李天瑞,珠杰,刘佳. 带权图的多重分形研究[J]. 南京大学学报(自然科学版), 2020, 56(1): 85–97.

Shengjiu Liu,Tianrui Li,Jie Zhu,Jia Liu. Research on multi⁃fractals of weighted graphs[J]. Journal of Nanjing University(Natural Sciences), 2020, 56(1): 85–97.

图/表 5

表1

节点权重为正实数的四种不同类型带权图分形维数统计表"

编号	节点权重	边权重	分形维数
1	正实数 $f (v)$	正实数 $f (e)$	$1 l g ∑ v ∈ V f (v) l g ∑ e ∈ E f (e)$ (6)
2		负实数 $- f (e)$	$1 l g ∑ v ∈ V f (v) l g e i π ∑ e ∈ E f (e)$ (7)
3		纯虚数 $i f (e)$	$1 l g ∑ v ∈ V f (v) l g e i π 2 ∑ e ∈ E f (e)$ (8)
4		复数 $(a + b i) f (e)$	$1 l g ∑ v ∈ V f (v) l g a 2 + b 2 e i t a n - 1 b a ∑ e ∈ E f (e)$ (9)

表1

表2

节点权重为负实数的四种不同类型带权图分形维数统计表"

编号	节点权重	边权重	分形维数
1	负实数 $- f (v)$	正实数 $f (e)$	$1 l g e i π ∑ v ∈ V f (v) l g ∑ e ∈ E f (e)$ (15)
2		负实数 $- f (e)$	$1 l g e i π ∑ v ∈ V f (v) l g e i π ∑ e ∈ E f (e)$ (16)
3		纯虚数 $i f (e)$	$1 l g e i π ∑ v ∈ V f (v) l g e i π 2 ∑ e ∈ E f (e)$ (17)
4		复数 $(a + b i) f (e)$	$1 l g e i π ∑ v ∈ V f (v) l g a 2 + b 2 e i t a n - 1 b a ∑ e ∈ E f (e)$ (18)

表2

表3

节点权重为纯虚数的四种不同类型带权图分形维数统计表"

编号	节点权重	边权重	分形维数
1	纯虚数 $i f (v)$	正实数 $f (e)$	$1 l g e i π 2 ∑ v ∈ V f (v) l g ∑ e ∈ E f (e)$ (32)
2		负实数 $- f (e)$	$1 l g e i π 2 ∑ v ∈ V f (v) l g e i π ∑ e ∈ E f (e)$ (33)
3		纯虚数 $i f (e)$	$1 l g e i π 2 ∑ v ∈ V f (v) l g e i π 2 ∑ e ∈ E f (e)$ (34)
4		复数 $(a + b i) f (e)$	$1 l g e i π 2 ∑ v ∈ V f (v) l g a 2 + b 2 e i t a n - 1 b a ∑ e ∈ E f (e)$ (35)

表3

表4

节点权重为复数的四种不同类型带权图分形维数统计表"

编号	节点权重	边权重	分形维数
1	复数 $(a + b i) f (v)$	正实数 $f (e)$	$1 l g a 2 + b 2 e i t a n - 1 b a ∑ v ∈ V f (v) l g ∑ e ∈ E f (e)$ (45)
2		负实数 $- f (e)$	$1 l g a 2 + b 2 e i t a n - 1 b a ∑ v ∈ V f (v) l g e i π ∑ e ∈ E f (e)$ (46)
3		纯虚数 $i f (e)$	$1 l g a 2 + b 2 e i t a n - 1 b a ∑ v ∈ V f (v) l g e i π 2 ∑ e ∈ E f (e)$ (47)
4		复数 $(a + b i) f (e)$	$1 l g a 2 + b 2 e i t a n - 1 b a ∑ v ∈ V f (v) l g a 2 + b 2 e i t a n - 1 b a ∑ e ∈ E f (e)$ (48)

表4

表5

16种不同类型带权图多重分形统计表"

编号	节点权重	边权重	多重分形维数分布	备注
1	正实数 $f (v)$	正实数 $f (e)$	-	单分形
2		负实数 $- f (e)$	直线	平行于虚轴
3		纯虚数 $i f (e)$	直线
4		复数 $(a + b i) f (e)$	直线
5	负实数 - $f (v)$	正实数 $f (e)$	圆	经过原点
6		负实数 $- f (e)$	直线系/圆系	整个复平面
7		纯虚数 $i f (e)$	直线系/圆系
8		复数 $(a + b i) f (e)$	直线系/圆系
9	纯虚数 $i f (v)$	正实数 $f (e)$	圆	经过原点
10		负实数 $- f (e)$	直线系/圆系	整个复平面
11		纯虚数 $i f (e)$	直线系/圆系
12		复数 $(a + b i) f (e)$	直线系/圆系
13	复数 $(a + b i) f (v)$	正实数 $f (e)$	圆	经过原点
14		负实数 $- f (e)$	直线系/圆系	整个复平面
15		纯虚数 $i f (e)$	直线系/圆系
16		复数 $(a + b i) f (e)$	直线系/圆系

表5

参考文献 16

1	Erdos P，Renyi A. On random graphs I. Publicationes Mathematicae，1959，6：290-297.
2	Watts D J，Strogatz S H. Collective dynamics of 'small?world' networks. Nature，1998，393：440-442.
3	Newman M E J，Watts D J. Renormalization group analysis of the small?world network model. Physics Letter A. 1999，293：341-346.
4	Barabasi A L，Albert R. Emergence of scaling in random networks. Science，1999，286：509-512.
5	熊文海，高齐圣，张嗣瀛. 复杂网络的邻接矩阵及其特征谱. 武汉理工大学学报(交通科学与工程版)，2009，33(1)：83-86.
	Xiong W H，Gao Q S，Zhang S YAdjacency matrix and spectral density of complex networks. Journal of Wuhan University of Technology(Transportation Science & Engineering)，2009，33(1)：83-86.
6	Song C，Jalvin S，Makse H A. Self?similarity of complex networks. Nature，2005，433：392-395.
7	Andre M B. On a class of fractal matrices (I) Excess?Matrices and their self?similar properties. International Journal of Bifurcation and Chaos，1992，2(4)：841-860.
8	刘胜久，李天瑞，洪西进等. 基于矩阵运算的复杂网络构建方法. 中国科学：信息科学，2016，46(5)：610-626.
	Liu S J，Li T R，Horong S J，et al. Complex network construction based on matrix operation. Scientia Sinica Informationis，2016，46(5)：610-626.
9	刘胜久，李天瑞，刘小伟. 网络维数：一种度量复杂网络的新方法. 计算机科学，2019，46(1)：51-56.
	Liu S J，Li T R，Liu X WNetwork network dimension：a new measure for complex networks. Computer Science，2019，46(1)：51-56.
10	张先迪，李正良. 图论及其应用. 北京：高等教育出版社，2005，297.
11	Balka R，Buczolich Z，Elekes M. A new fractal dimension：the topological Hausdorff dimension. Advances in Mathematics，2015，274(1)：881-927.
12	Sreenivasan K R，Meneveau C. The fractal facets of turbulence. Journal of Fluid Mechanics，1986，173(173)：357-386.
13	Harte D. Multifractals：theory and applications. Chapman & Hall/CRC，2001，364.
14	赵静湉，陈彦光，李双成. 京津冀城市用地形态的双分形特征及其演化. 地理科学进展，2019，38(1)：77-87.
	Zhao J T，Chen Y G，Li S CBi?fractal structure and evolution of the Beijing?Tianjin?Hebei region urban land?use patterns. Progress in Geography，2019，38(1)：77-87.
15	Song Y Q，Liu J L,Yu Z G，et al. Multifractal analysis of weighted networks by a modified sandbox algorithm. Scientific Reports，2015(5)：17628.
16	Liu J L，Wang J，Yu Z G，et al. Fractal and multifractal analyses of bipartite networks. Scientific Reports，2017(7)：45588.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

[1]	郑文萍,刘韶倩,穆俊芳. 一种基于相对熵的随机游走相似性度量模型[J]. 南京大学学报(自然科学版), 2019, 55(6): 984-999.
[2]	马娜, 范敏, 李金海. 复杂网络下的概念认知学习[J]. 南京大学学报(自然科学版), 2019, 55(4): 609-623.
[3]	钱　峰1，2，张　蕾1，2，赵　姝1*，陈　洁1，张燕平1. 基于加权树的层次社团划分算法[J]. 南京大学学报(自然科学版), 2018, 54(4): 696-.
[4]	底晓强1,2* , 刘永霞1. 基于自相似流的星上虚拟信道调度算法研究[J]. 南京大学学报(自然科学版), 2018, 54(3): 515-521.
[5]	张泽华1*，段力畑1，段　富1，张　楠2. 基于局部结构特征的重叠社区挖掘研究进展[J]. 南京大学学报(自然科学版), 2017, 53(3): 537-.
[6]	宾　晟*，孙更新. 基于多子网复合复杂网络模型的多关系社交网络重要节点发现算法[J]. 南京大学学报(自然科学版), 2017, 53(2): 378-.
[7]	张燕平1,2，汪洋1,2，赵姝1,2, 段震1,2**. 基于覆盖的社团发现算法[J]. 南京大学学报(自然科学版), 2013, 49(5): 539-545.

带权图的多重分形研究

Research on multi⁃fractals of weighted graphs

RichHTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 16

相关文章 7

Metrics

本文评价

推荐阅读 6