一种确定性小世界网络模型平均路径长度的逼近方法
An Approximation Algorithm for Average Path Length in A Small-World Network Model
DOI: 10.12677/AAM.2014.31004, PDF, HTML,    国家自然科学基金支持
作者: 张 科：青海师范大学数学系，西宁；赵海兴, 李 峰：青海师范大学计算机学院，西宁
关键词: 图论；平均路径长度；小世界网络；Graph Theory; Small-World Network; Average Path Length
摘要: 确定性小世界网络是复杂网络中的一个重要的研究分支。2008年，章忠志等人(Eur.Phys.J.B 63)在复杂网络的视角下对确定性均匀递归树作了详尽地分析，得到了其拓扑属性。尽管确定性均匀递归树的平均路径长度表现出了网络大小的对数规模，但是它的聚类系数为零。2012年，陆哲明等人(Physica A 391)通过在确定性均匀递归树的基础上以一个简单的规则添加一些边得到一个确定性小世界网络模型。本文根据网络模型的结构用分析的方法给出了文献Physica A 391中的模型的平均路径长度的逼近方法。
Abstract: Deterministic small-world network is an important branch of study of complex networks. In 2008, Zhang et al. in Eur.Phys.J.B 63 have offered detailed topological characteristics of the deterministic uniform recursive tree from the viewpoint of complex network. They derived topological characteristics of the deterministic uniform recursive tree. It shows a logarithmic scaling with the size of the network, however, its clustering coefficient is zero. In 2012, Lu, et al. in Physica A 391, based on the deterministic uniform recursive tree, by a simple rule to add some edges, got a deterministic small-world network model. In this paper, using an approximation algorithm based on the network construction, we show explicitly the average path length of the model constructed in Physica A 391.
文章引用：张科, 赵海兴, 李峰. 一种确定性小世界网络模型平均路径长度的逼近方法[J]. 应用数学进展, 2014, 3(1): 22-28. http://dx.doi.org/10.12677/AAM.2014.31004

参考文献

[1] Newman, M.E.J. (2000) Models of the small world. Journal of Statistical Physics, 101, 819-941.
[2] Albert, R. and Barabási, A.-L. (2002) Statistical mechanics of complex networks. Reviews of Modern Physics, 74, 47-97.
[3] Newman, M.E.J. (2003) The structure and function of complex networks. SIAM Review, 45, 167-256.
[4] Yu, S., Huang, D., Singer, W. and Nikolic, D. (2008) A small world of neuronal synchrony. Cerebral Cortex, 18, 2891-2901.
[5] Chung, F. and Lu, L. (2002) The average distances in random graphs with given expected degrees. Proceedings of the National Academy of Sciences of USA, 99, 15879-15882.
[6] Cohen, R. and Havlin, S. (2003) Scale-free networks are ultrasmall. Physical Review Letters, 90, Article ID: 058701.
[7] Dorogovtsev, S.N., Mendes, J.F.F. and Oliveira, J.G. (2006) Degree-dependent intervertex separation in complex networks. Physical Review E, 73, Article ID: 056122.
[8] Watts, D.J. and Strogatz, S.H. (1998) Collective dynamics of “small-world” networks. Nature, 393, 440-442.
[9] Condamin, S., Benichou, O., Tejedor, V., Voituriez, R. and Klafter, J. (2007) First-passage times in complex scale-invariant media. Nature, 450, 77-80.
[10] Nishikawa, T., Motter, A.E., Lai, Y.-C. and Hoppensteadt, F.C. (2003) Heterogeneity in oscillator networks: Are smaller worlds easier to synchronize? Physical Review Letters, 91, Article ID: 014101.
[11] Dorogovtsev, S.N., Mendes, J.F.F. and Samukhin, A.N. (2003) Metric structure of random networks. Nuclear Physics, 653, 307-338.
[12] Lovejoy, W.S. and Loch, C.H. (2003) Minimal and maximal characteristic path lengths in connected sociomatrices. Social Networks, 25, 333347.
[13] Fronczak, A., Fronczak, P. and Holyst, J.A. (2004) Average path length in random networks. Physical Review E, 70, Article ID: 056110.
[14] Holyst, J.A., Sienkiewicz, J., Fronczak, A., Fronczak, P. and Suchecki, K. (2005) Universal scaling of distances in complex networks. Physical Review E, 72, Article ID: 026108.
[15] Fekete, A.,Vattay, G. and Posfai, M. (2009) Shortest path discovery of complex networks. Physical Review E, 79, Article ID: 065101.
[16] Smythe, R.T. and Mahmoud, H. (1995) A survey of recursive trees. Theorya Imovirnosty ta Matemika Statystika, 51, 1-27.
[17] 章忠志, 周水庚, 方锦清 (2008) 复杂网络确定性模型研究的最新进展. 复杂系统与复杂性科学, 4, 29-46.
[18] Jung, S., Kim, S. and Kahng, B. (2002) A geometric fractal growth model scale free networks. Physical Review E, 65, Article ID: 056101.
[19] Zhang, Z.Z., Zhou, S.G., Qi, Y. and Guan, J.H. (2008) Topologies and Laplacian spectra of a deterministic uniform recursive tree. European Physical Journal B, 63, 507-513.
[20] Lu, Z.M. and Guo, S.Z. (2012) A small-world network derived from the deterministic uniform recursive tree. Physica A, 391, 87-92.

为你推荐