Random graphs, models and generators of scale-free graphs
Abstract
In this paper various models of random graphs describing real networks arising in different research fields: biology, computer science, engineering, sociology are considered. Particular attention is paid to models describing social networks. We start with observation of classical Erdos-Renyi model and basic facts concerning properties of random graphs depending on the value p of the probability of appearance each edge in a graph. Then we observe so-called scale-free model of random graphs proposed by Barabassi and Albert and some its generalizations. Some mathematical results about properties of random graphs in such models are described. For one such model of Bollobas-Riordan we describe results concerning the diameter of random graph, the number of verticies of given degree (power-law distribution) and other different properties. This class of models can be characterized by the property that so-called power law constant cannot be chosen in advance and has one fixed value. For example in Bollobas-Riordan model this constant is 3. Finely we observe more general models of random graphs such as Aiello-Chung-Lu model where the power law constant can be chosen as a parameter. In such models there are interesting results concerning evolution properties of random graphs depending on the value of parameter of power law constant. The main example of such property is the size of maximum clique in random graph which we consider in this paper.
About the Authors
M. M. Bernovskiy
PhysTech; ISP RAS
Russian Federation
Russian Federation
N. N. Kuzyurin
ISP RAS
Russian Federation
Russian Federation
References
1. Newman M., Barabási A.L., Watts D. J.. The Structure and dynamics of networks. Princeton University Press, 2006.
2. Erdös P., Rényi A. On the evolution of random graphs. Publ. Math. Debrecen. 1959. V. 6. P. 290-297.
3. Aiello W., Chung F., Lu L. A Random Graph Model for Massive Graphs. STOC '2000.
4. Janson S., Łuczak T., Norros I., Large cliques in a power-law random graph, J. Appl. Probab. 2010. V. 47, N. 4, pp. 1124-1135.
5. Barabási L.A., Albert R. Emergence of scaling in random networks. Science, 1999.
6. V.286. P. 509-512
7. Barabási L.A., Albert R., Jeong H.. Scale-free characteristics of random networks: the topology of the world-wide web. Physica, 2000. V. A281. P. 69-77.
8. Barabási L.A., Albert R., Jeong H. Diameter of the world-wide web. Nature, 1999. V. 401. P. 130-131.
9. Kumar R., Raghavan P., Rajagopalan S., Sivakumar D., Tomkins A., Upfal E. Stochastic models for the web graph. Proceedings of the 41st Symposium on Foundations of Computer Science. 2000.
10. Bollobás B., Riordan O. Mathematical results on scale-free random graphs. Handbook of graphs and networks. Weinheim: Wiley-VCH, 2003. P. 1-34.
11. Raigoroskii A.M. Modeli sluchainykh grafov [Random graph models]. MCNMO [Moscow center of continuous mathematical education], 2011. 136 , p. (in Russian)
12. Buckley P.G., Osthus D. Popularity based random graph models leading to scale-free degree sequence. Discrete Mathematics. Volume 282, Issues 1–3, 6 May 2004, pp. 53–68.
13. Bollobás B., Borgs C., Chayes T., Riordan O.M. Directed scale-free graphs. Proceedings SODA '03 Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms.
14. Brady A.R. A compact routing scheme for power-law networks using empirical discoveries in power-law graph topology. http://digg.cs.tufts.edu/readings/pdf/021.pdf
15. Chakrabarti D., et al. R-MAT: A Recursive Model for Graph Mining. http://www.cs.cmu.edu/ christos/PUBLICATIONS/siam04.pdf
16. Medina A., et al. BRITE: Universal Topology Generation from a User’s Perspective. http://www.cs.bu.edu/brite/publications/usermanual.pdf
17. Miller J. C., Hagberg A. Efficient Generation of Networks with Given Expected Degrees. WAW, 2011.
18. Nazir A.,, Raza C., Chuah C.-N.. Unveiling Facebook: a measurement study of social network based applications. IMC'08.
19. Leskovec J., Kleinberg J., Faloutsos C. Graph evolution: Densification and shrinking diameters. ACM Transact. on Knowledge Discovery from Data, 1(1), 2007.
Review
For citations:
Bernovskiy M.M., Kuzyurin N.N. Random graphs, models and generators of scale-free graphs. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2012;22. (In Russ.)
Email this article 