中国物理B ›› 2008, Vol. 17 ›› Issue (7): 2327-2332.doi: 10.1088/1674-1056/17/7/001

• •    下一篇

An estimation formula for the average path length of scale-free networks

曹宏铎1, 山秀明1, 任勇1, 李旲2   

  1. (1)Department of Electronic Engineering, Tsinghua University, Beijing 100084, China; (2)Department of Management Sciences, School of Business, SUN YAT-SEN University, Guangzhou 510275, China;Department of Electronic Engineering, Tsinghua University, Beijing 100084, China
  • 收稿日期:2007-09-12 修回日期:2007-12-26 出版日期:2008-07-09 发布日期:2008-07-09
  • 基金资助:
    Project supported by the National Natural Science Foundation of China (Grant Nos 60672142, 60772053 and 90304005).

An estimation formula for the average path length of scale-free networks

Li Ying(李旲)a)b), Cao Hong-Duo(曹宏铎)a),Shan Xiu-Ming(山秀明)b), and Ren Yong(任勇)b)   

  1. a Department of Management Sciences, School of Business, SUN YAT-SEN University, Guangzhou 510275, China; b Department of Electronic Engineering, Tsinghua University, Beijing 100084, China
  • Received:2007-09-12 Revised:2007-12-26 Online:2008-07-09 Published:2008-07-09
  • Supported by:
    Project supported by the National Natural Science Foundation of China (Grant Nos 60672142, 60772053 and 90304005).

PDF (PC)

918

赞

摘要： A universal estimation formula for the average path length of scale free networks is given in this paper. Different from other estimation formulas, most of which use the size of network, $N$, as the only parameter, two parameters including $N$ and a second parameter $\alpha $ are included in our formula. The parameter $\alpha $ is the power-law exponent, which represents the local connectivity property of a network. Because of this, the formula captures an important property that the local connectivity property at a microscopic level can determine the global connectivity of the whole network. The use of this new parameter distinguishes this approach from the other estimation formulas, and makes it a universal estimation formula, which can be applied to all types of scale-free networks. The conclusion is made that the small world feature is a derivative feature of a scale free network. If a network follows the power-law degree distribution, it must be a small world network. The power-law degree distribution property, while making the network economical, preserves the efficiency through this small world property when the network is scaled up. In other words, a real scale-free network is scaled at a relatively small cost and a relatively high efficiency, and that is the desirable result of self-organization optimization.

关键词: scale free network, power law, small world, power law exponent

Abstract: A universal estimation formula for the average path length of scale free networks is given in this paper. Different from other estimation formulas, most of which use the size of network, $N$, as the only parameter, two parameters including $N$ and a second parameter $\alpha $ are included in our formula. The parameter $\alpha $ is the power-law exponent, which represents the local connectivity property of a network. Because of this, the formula captures an important property that the local connectivity property at a microscopic level can determine the global connectivity of the whole network. The use of this new parameter distinguishes this approach from the other estimation formulas, and makes it a universal estimation formula, which can be applied to all types of scale-free networks. The conclusion is made that the small world feature is a derivative feature of a scale free network. If a network follows the power-law degree distribution, it must be a small world network. The power-law degree distribution property, while making the network economical, preserves the efficiency through this small world property when the network is scaled up. In other words, a real scale-free network is scaled at a relatively small cost and a relatively high efficiency, and that is the desirable result of self-organization optimization.

Key words: scale free network, power law, small world, power law exponent

中图分类号:  (Networks and genealogical trees)

  • 89.75.Hc
89.20.Hh (World Wide Web, Internet)