An Approximation Algorithm for Average Path Length in A Small-World Network Model
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.
文章引用: 张 科 , 赵海兴 , 李 峰 (2014) 一种确定性小世界网络模型平均路径长度的逼近方法。 应用数学进展， 3， 22-28. doi: 10.12677/AAM.2014.31004
 Newman, M.E.J. (2000) Models of the small world. Journal of Statistical Physics, 101, 819-941.
 Albert, R. and Barabási, A.-L. (2002) Statistical mechanics of complex networks. Reviews of Modern Physics, 74, 47-97.
 Newman, M.E.J. (2003) The structure and function of complex networks. SIAM Review, 45, 167-256.
 Yu, S., Huang, D., Singer, W. and Nikolic, D. (2008) A small world of neuronal synchrony. Cerebral Cortex, 18, 2891-2901.
 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.
 Cohen, R. and Havlin, S. (2003) Scale-free networks are ultrasmall. Physical Review Letters, 90, Article ID: 058701.
 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.
 Watts, D.J. and Strogatz, S.H. (1998) Collective dynamics of “small-world” networks. Nature, 393, 440-442.
 Condamin, S., Benichou, O., Tejedor, V., Voituriez, R. and Klafter, J. (2007) First-passage times in complex scale-invariant media. Nature, 450, 77-80.
 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.
 Dorogovtsev, S.N., Mendes, J.F.F. and Samukhin, A.N. (2003) Metric structure of random networks. Nuclear Physics, 653, 307-338.
 Lovejoy, W.S. and Loch, C.H. (2003) Minimal and maximal characteristic path lengths in connected sociomatrices. Social Networks, 25, 333347.
 Fronczak, A., Fronczak, P. and Holyst, J.A. (2004) Average path length in random networks. Physical Review E, 70, Article ID: 056110.
 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.
 Fekete, A.,Vattay, G. and Posfai, M. (2009) Shortest path discovery of complex networks. Physical Review E, 79, Article ID: 065101.
 Smythe, R.T. and Mahmoud, H. (1995) A survey of recursive trees. Theorya Imovirnosty ta Matemika Statystika, 51, 1-27.
 章忠志, 周水庚, 方锦清 (2008) 复杂网络确定性模型研究的最新进展. 复杂系统与复杂性科学, 4, 29-46.
 Jung, S., Kim, S. and Kahng, B. (2002) A geometric fractal growth model scale free networks. Physical Review E, 65, Article ID: 056101.
 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.
 Lu, Z.M. and Guo, S.Z. (2012) A small-world network derived from the deterministic uniform recursive tree. Physica A, 391, 87-92.