x

## 留言板

 引用本文:
 Citation:

## Average path length of Internet with power law degree distribution

Li Ying, Shan Xiu-Ming, Ren Yong
PDF
• #### 摘要

针对具有幂律度分布的复杂网络的平均最短路径长度进行了研究.给出了一个计算因特网平 均最短路径长度的公式.提出因特网的整体构造实质是以最小代价换取最大收益，从此出 发通过对因特网这类复杂网络平均最短路径长度影响因素分析，推断出网络最短路径长度分 布P(l)的基本性质，进而构造了一个只含参数α的P(l)的简洁形式，直接打通了拓扑具有幂 律度分布的因特网的度分布P(k)与网络最短路径长度分布P(l)之间的关系.然后说明了导出 的公式的物理意义，即参数α代表网络节点连接方式和网络的总边数对平均最短路径长 度的影响.此公式意味着只要掌握幂律P(k)～k-α中α值，就可以直接计算相应网 络的平均最短路径长度.通过对已知数据的计算，验证了公式的有效性.阐明了参数 α对网络设计的重要性和对网络功能的影响.

#### Abstract

The average path length of Internet with power law degree distribution is stud ied in this paper. The main work is to give a formula to compute the average pat h length . The essential of Internet or many other complex networks is to realize the least cost (the smallest total number of edges) and the best benefi t (the short average path length), which can be expressed as two optimization fa ctors to minimize the average degree and the average path length . By analyzing the main factor affecting , we find the main property of p ath length distribution P(l), and then give a formula of P(l) only inclu ding one parameter α. This work shows that P(l) and a direct relation with P(k),and α represent the effective link between nodes and the tota l number of networks on . This formula makes it possible that if we get the α of P(k)～k-α, we can calculate easily. The simulati on shows the formula is quite exact. Our method is successful. In the end, we di scuss that the parameter αis very important for Internet design.

#### 作者及机构信息

###### 1. 清华大学电子工程系,北京　100084
• 基金项目: 国家自然科学基金(批准号：90204004和90304005)资助的课题.

#### 施引文献

•  [1] 阮逸润, 老松杨, 汤俊, 白亮, 郭延明. 基于引力方法的复杂网络节点重要度评估方法. 物理学报, 2022, 71(17): 176401. doi: 10.7498/aps.71.20220565 [2] 阮逸润, 老松杨, 王竣德, 白亮, 陈立栋. 基于领域相似度的复杂网络节点重要度评估算法. 物理学报, 2017, 66(3): 038902. doi: 10.7498/aps.66.038902 [3] 闵磊, 刘智, 唐向阳, 陈矛, 刘三(女牙). 基于扩展度的复杂网络传播影响力评估算法. 物理学报, 2015, 64(8): 088901. doi: 10.7498/aps.64.088901 [4] 郭进利, 祝昕昀. 超网络中标度律的涌现. 物理学报, 2014, 63(9): 090207. doi: 10.7498/aps.63.090207 [5] 郭进利. 非均齐超网络中标度律的涌现富者愈富导致幂律分布吗?. 物理学报, 2014, 63(20): 208901. doi: 10.7498/aps.63.208901 [6] 余晓平, 裴韬. 手机通话网络度特征分析. 物理学报, 2013, 62(20): 208901. doi: 10.7498/aps.62.208901 [7] 田立新, 贺莹环, 黄益. 一种新型二分网络类局域世界演化模型. 物理学报, 2012, 61(22): 228903. doi: 10.7498/aps.61.228903 [8] 张聪, 沈惠璋, 李峰, 杨何群. 复杂网络中社团结构发现的多分辨率密度模块度. 物理学报, 2012, 61(14): 148902. doi: 10.7498/aps.61.148902 [9] 周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜. 利用重要度评价矩阵确定复杂网络关键节点. 物理学报, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201 [10] 闫小勇, 王明生. 增长速度对合作网络参与者节点度分布的影响. 物理学报, 2010, 59(2): 851-858. doi: 10.7498/aps.59.851 [11] 赵清贵, 孔祥星, 侯振挺. 简易广义合作网络度分布的稳定性. 物理学报, 2009, 58(10): 6682-6685. doi: 10.7498/aps.58.6682 [12] 郭进利. 新节点的边对网络无标度性影响. 物理学报, 2008, 57(2): 756-761. doi: 10.7498/aps.57.756 [13] 刘 慧, 张 军. 基于节点相关性的网络不动点理论研究. 物理学报, 2007, 56(4): 1952-1957. doi: 10.7498/aps.56.1952 [14] 郭进利, 汪丽娜. 幂律指数在1与3之间的一类无标度网络. 物理学报, 2007, 56(10): 5635-5639. doi: 10.7498/aps.56.5635 [15] 闫 栋, 祁国宁. 大规模软件系统的无标度特性与演化模型. 物理学报, 2006, 55(8): 3799-3804. doi: 10.7498/aps.55.3799 [16] 张培培, 何 阅, 周 涛, 苏蓓蓓, 常 慧, 周月平, 汪秉宏, 何大韧. 一个描述合作网络顶点度分布的模型. 物理学报, 2006, 55(1): 60-67. doi: 10.7498/aps.55.60 [17] 郭进利. 供应链型网络中双幂律分布模型. 物理学报, 2006, 55(8): 3916-3921. doi: 10.7498/aps.55.3916 [18] 刘　锋, 山秀明, 任　勇, 张　军, 马正新. 计算机网络的长程相关特性. 物理学报, 2004, 53(2): 373-378. doi: 10.7498/aps.53.373 [19] 刘锋, 任勇, 山秀明. 互联网络数据包传输的一种简单元胞自动机模型. 物理学报, 2002, 51(6): 1175-1180. doi: 10.7498/aps.51.1175 [20] 袁坚, 任勇, 刘锋, 山秀明. 复杂计算机网络中的相变和整体关联行为. 物理学报, 2001, 50(7): 1221-1225. doi: 10.7498/aps.50.1221
##### 计量
• 文章访问数:  7177
• PDF下载量:  1418
• 被引次数: 0
##### 出版历程
• 收稿日期:  2004-05-20
• 修回日期:  2004-06-25
• 刊出日期:  2004-11-16

/