Simulation and Measurement of Complex Network Growth: the Interplay of Uniform and Preferential Attachment

• Autorzy: Luo H. , Horadam K.
• Języki publikacji: EN

Abstrakty

EN

The main discovery of the paper is the introduction and study of a new U-P complex network model, which aims to describe and analyze many common-featured real-world complex networks. This model employs a new functional form of the network growth rule: a linear combination of preferential and uniform attachment. In particular, the degree distribution of the model is first studied by using the computer simulation method, while the exact solution is also obtained analytically.

Słowa kluczowe

EN

complex networks; scale-free; small-world; preferential attachment

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 84, nr 1
• Strony: 61--79
• Opis fizyczny: bibliogr. 27 poz., tab., wykr.

Twórcy

autor

Luo H.

autor

Horadam K.

• School of mathematical and Geospatial Sciences, RMIT University, Melbourne VIC 3001, Australia,

Bibliografia

• [1] Albert, R. and Barab´asi, A.-L., Statistical mechanics of complex networks, Reviews of Modern Physics, 74, 47-97 (2002).
• [2] Albert, R., Barab´asi, A.-L., and Bianconi, G., Power-law distribution of the World Wide Web, Seience 287 2115a (2000).
• [3] Barabási, A.-L., Emergence of scaling in random networks, Science 286, 509-512 (1999).
• [4] Barabási, A.-L., Albert, R. and Jeong, H., Scale-free characteristics of random networks: the topology of the World Wide Web, Physica A, Vol 281, 69-77 (2000).
• [5] Bender, E. A. and Canfield, E.R., The asymptotic number of labeled graphs with given degree sequences, Journal of Combinatorial Theory A Vol 24, 296-307 (1978).
• [6] Bollobás, B., Random Graphs, Academic Press, New York (1978).
• [7] Callaway, D.S., Hopcroft, J. E., Kleinberg, J. M., Newman, M. E. J. and Strogatz, S. H. Are randomly grown graphs really random?, Phys. Rev. E 64, 041902 (2001).
• [8] Chen, Q., Chang, H., Govindan, R., Jamin, S., Shenker, S. J., and Willinger,W., The origin of power laws in Internet topologies revisited, Proc. the 21st Annual Joint Conference of the IEEE Computer and Communications Societies, IEEE Computer Society (2002).
• [9] Chung, F., Lu, L., The diameter of random sparse graphs, Advances in Applied Math Vol. 26, PP. 257-279 (2001).
• [10] C. Cooper and A. Frieze, A general model of web graphs, RandomStructures Algorithms 22, 311-335 (2003).
• [11] Erdős, P. and Rényi, A., On random graphs, PublicationesMathematicase Debrecen, Vol. 5, 290-297 (1959).
• [12] Erdős, P. and Rényi, A., On the evolution of random graphs,Magyar Tud. Akad.Mat. Kutató Int. K¨ozl., Vol. 5, 17-61 (1960).
• [13] Gomez-Gardenes, J. and Moreno, Y., From Scale-free to Erdos-Renyi Networks, Phys. Rev. E 73, 056124 (2006).
• [14] Kappen, H. andWiegerinckW. J., Mean field theory for graphical models In M. Opper and D. Saad, editors, Advanced Mean Field Theory- Theory and Practice, 37-49. MIT Press, (2001).
• [15] Luo, H.W., Modelling and simulation of large-scale complex networks, PhD Thesis Submitted June 2006, RMIT University.
• [16] Luo, H.W. and Horadam, K. J., Simulation and measurement of large-scale complex networks, Proc. AWOCA, Ballarat, Australia, September 2005, 173-184 (2005).
• [17] Luo, H.W. and Horadam, K.J., Simulation and Measurement of a Two-stage Complex Network Model Proc. of SPIE, Vol 6417, Complexity and Nonlinear Dynamics, 64170B (2007)
• [18] The MathWorks, Inc., MATLAB Version 7.01.24704 (R14) Service Pack 1, http://www.mathworks.com/
• [19] Milgram, S., The small-world problem, Psychology Today, Vol. 2, pp. 60-67 (1967).
• [20] MolloyM. and Reed B., A critical point for random graphs with a given degree sequence, Random Structures and Algorithms, Vol 6, 161-179 (1995).
• [21] Molloy M. and Reed B., The size of the giant component of a random graph with a given degree sequence, Combinatorics, Probability and Computing, Vol 7, 195-305 (1998).
• [22] Newman, Mark, Models of the small world, Phys. 101, 819-841 (2000).
• [23] Newman, Mark, The structure and function of complex networks, SIAM Review 45, 167-256 (2003).
• [24] Newman M. E. J., Strogatz, S. H. and Watts, D. J., Random graphs with arbitrary degree distribution and their applications, Phys. Rev. E 64, 026118 (2001).
• [25] Shao, Z., Zou, X., Tan, Z. and Jin, Z. Growing networks with mixed attachment mechanisms, J. Phys. A: Math. Gen. Vol 39 2035-2042 (2006).
• [26] V. Batagelj, A. Mrvar, Pajek - program for large network analysis, Home page: http://vlado.fmf.uni-lj.si/pub/networks/pajek/.
• [27] Zalányi L., Csábor G., Kiss T., Lengyel M., Warner R., Tobochnik J. and ´Erdi P. Properties of a random attachment growing network, Physical Review E Vol 68, 066104 (2003).