Abstract
We propose a common framework for analysis of a wide class of preferential attachment models, which includes LCD, Buckley–Osthus, Holme–Kim and many others. The class is defined in terms of constraints that are sufficient for the study of the degree distribution and the clustering coefficient. We also consider a particular parameterized model from the class and illustrate the power of our approach as follows. Applying our general results to this model, we show that both the parameter of the power-law degree distribution and the clustering coefficient can be controlled via variation of the model parameters. In particular, the model turns out to be able to reflect realistically these two quantitative characteristics of a real network, thus performing better than previous preferential attachment models. All our theoretical results are illustrated empirically.
The authors are given in alphabetical order.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Albert, R., Barabási, A.-L.: Statistical mechanics of complex networks. Reviews of Modern Physics 74, 47–97 (2002)
Bansal, S., Khandelwal, S., Meyers, L.A.: Exploring biological network structure with clustered random networks. BMC Bioinformatics 10, 405 (2009)
Barabási, A.-L., Albert, R.: Science 286, 509 (1999); Barabási, A.-L., Albert, R., Jeong, H.: Physica A 272, 173 (1999); Albert, R., Jeong, H., Barabási, A.-L.: Nature 401, 130 (1999)
Batagelj, V., Brandes, U.: Efficient generation of large random networks. Phys. Rev. E 71, 036113 (2005)
Boccaletti, S., Latora, V., Moreno, Y., Chavez, M., Hwang, D.-U.: Complex networks: Structure and dynamics. Physics Reports 424(45), 175–308 (2006)
Bollobás, B., Riordan, O.M.: Mathematical results on scale-free random graphs. In: Handbook of Graphs and Networks: From the Genome to the Internet, pp. 1–3 (2003)
Bollobás, B., Riordan, O.M., Spencer, J., Tusnády, G.: The degree sequence of a scale-free random graph process. Random Structures and Algorithms 18(3), 279–290 (2001)
Borgs, C., Brautbar, M., Chayes, J., Khanna, S., Lucier, B.: The power of local information in social networks (2012) (preprint)
Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., Wiener, J.: Graph structure in the web. Computer Networks 33(16), 309–320 (2000)
Buckley, P.G., Osthus, D.: Popularity based random graph models leading to a scale-free degree sequence. Discrete Mathematics 282, 53–63 (2004)
Cooper, C.: Distribution of Vertex Degree in Web-Graphs. Combinatorics, Probability and Computing 15, 637–661 (2006)
Cooper, C., Frieze, A.: A General Model of Web Graphs. Random Structures and Algorithms 22(3), 311–335 (2003)
Cooper, C., Prał, P.: at, Scale-free graphs of increasing degree. Random Structures and Algorithms 38(4), 396–421 (2011)
Deijfen, M., van den Esker, H., van der Hofstad, R., Hooghiemstra, G.: A preferential attachment model with random initial degrees. Ark. Mat. 47, 41–72 (2009)
Eggemann, N., Noble, S.D.: The clustering coefficient of a scale-free random graph. Discrete Applied Mathematics 159(10), 953–965 (2011)
Faloutsos, M., Faloutsos, P., Faloutsos, C.: On power-law relationships of the Internet topology. In: Proc. SIGCOMM 1999 (1999)
Grechnikov, E.A.: An estimate for the number of edges between vertices of given degrees in random graphs in the Bollobás–Riordan model. Moscow Journal of Combinatorics and Number Theory 1(2), 40–73 (2011)
Holme, P., Kim, B.J.: Growing scale-free networks with tunable clustering. Phys. Rev. E 65(2), 026107 (2002)
Móri, T.F.: The maximum degree of the Barabási-Albert random tree. Combinatorics, Probability and Computing 14, 339–348 (2005)
Serrano, M.Á., Boguñá, M.: Tuning clustering in random networks with arbitrary degree distributions. Phys. Rev. E 72(3), 036133 (2005)
Volz, E.: Random Networks with Tunable Degree Distribution and Clustering. Phys. Rev. E 70(5), 056115 (2004)
Zhou, T., Yan, G., Wang, B.-H.: Maximal planar networks with large clustering coefficient and power-law degree distribution journal. Phys. Rev. E 71(4), 46141 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
Ostroumova, L., Ryabchenko, A., Samosvat, E. (2013). Generalized Preferential Attachment: Tunable Power-Law Degree Distribution and Clustering Coefficient. In: Bonato, A., Mitzenmacher, M., Prałat, P. (eds) Algorithms and Models for the Web Graph. WAW 2013. Lecture Notes in Computer Science, vol 8305. Springer, Cham. https://doi.org/10.1007/978-3-319-03536-9_15
Download citation
DOI: https://doi.org/10.1007/978-3-319-03536-9_15
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-03535-2
Online ISBN: 978-3-319-03536-9
eBook Packages: Computer ScienceComputer Science (R0)