×

Parameter specification for the degree distribution of simulated Barabási-Albert graphs. (English) Zbl 1400.05058

Summary: The degree distribution of a simulated Barabási-Albert graph under linear preferential attachment is investigated. Specifically, the parameters of the power law distribution are estimated and compared against the theoretical values derived using mean field theory. Least squares method and MLE-nonparametric method were utilized to estimate the distribution parameters on \(1000\) simulated Barabási-Albert graphs for edge parameter \(m \in \{2, 4, 6 \}\) and size \(n \in \{2^k : k = 5, 6, \ldots, 14, 15 \}\). Goodness of fit metrics were computed on a second set of simulated graphs for the median of the estimated parameters and other hypothetical values for the distribution parameters. The results suggest that the distribution of the parameters from simulated graphs are significantly different from the theoretical distribution and is also dependent on \(m\). Further results confirm the finding that the parameter of the power law distribution, \(\beta\), increases as \(m\) increases.

MSC:

05C07 Vertex degrees
05C82 Small world graphs, complex networks (graph-theoretic aspects)
62F10 Point estimation

Software:

plfit; igraph
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Conte, D.; Foggia, P.; Sansone, C.; Vento, M., Thirty years of graph matching in pattern recognition, Int. J. Pattern Recognit. Artif. Intell., 18, 265-298 (2004)
[2] Livi, L.; Rizzi, A., The graph matching problem, Pattern Anal. Appl., 16, 253-283 (2013) · Zbl 1284.68470
[3] de Solla Price, D. J., Networks of scientific papers, Science, 149, 510-515 (1965)
[4] Albert, R.; Jeong, H.; Barabási, A.-L., Internet: Diameter of the world-wide web, Nature, 401, 130-131 (1999)
[5] Barabási, A.-L.; Albert, R., Emergence of scaling in random networks, Science, 286, 509-512 (1999) · Zbl 1226.05223
[6] Newman, M. E., Power laws, pareto distributions and zipf’s law, Contemp. Phys., 46, 323-351 (2005)
[7] Clauset, A.; Shalizi, C. R.; Newman, M. E.J., Power-law distributions in empirical data, SIAM Rev., 51, 661-703 (2009) · Zbl 1176.62001
[8] Zhao, Z.-D.; Yang, Z.; Zhang, Z.; Zhou, T.; Huang, Z.-G.; Lai, Y.-C., Emergence of scaling in human-interest dynamics, Sci. Rep., 3, 3472 (2013)
[9] Fienberg, S. E., A brief history of statistical models for network analysis and open challenges, J. Comput. Graph. Statist., 21, 825-839 (2012)
[10] Zipf, G. K., Human behavior and the principle of least effort, J. Clin. Psychol., 6, 573 (1949)
[11] Yule, G. U., A mathematical theory of evolution, based on the conclusions of dr. j. c. willis, f.r.s., Philos. Trans. R. Soc. Lond. B Biol. Sci., 213, 21-87 (1925)
[12] Simon, H. A., On a class of skew distribution functions, Biometrika, 42, 425-440 (1955) · Zbl 0066.11201
[13] Wang, X.; Trajanovski, S.; Kooij, R. E.; Mieghem, P. V., Degree distribution and assortativity in line graphs of complex networks, Physica A, 445, 343-356 (2016) · Zbl 1400.05205
[14] Albert, R.; Barabási, A.-L., Statistical mechanics of complex networks, Rev. Modern Phys., 74, 47-97 (2002) · Zbl 1205.82086
[15] M. Small, K. Judd, L. Zhang, How is that complex network complex?, in: 2014 IEEE International Symposium on Circuits and Systems, ISCAS, 2014, pp. 1263-1266.; M. Small, K. Judd, L. Zhang, How is that complex network complex?, in: 2014 IEEE International Symposium on Circuits and Systems, ISCAS, 2014, pp. 1263-1266.
[16] Arnold, B., (Pareto Distributions. Pareto Distributions, Statistical Distributions in Scientific Work Series (1983), International Co-operative Publishing House) · Zbl 1169.62307
[17] Kvam, P. H.; Vidakovic, B., (Nonparametric Statistics with Applications to Science and Engineering. Nonparametric Statistics with Applications to Science and Engineering, Wiley Series in Probability and Statistics (2007), Wiley-Interscience) · Zbl 1183.62207
[18] Csardi, G.; Nepusz, T., The igraph software package for complex network research, Int. J. Complex Syst., 1695 (2006)
[19] C.S. Gillespie, Fitting heavy tailed distributions: the poweRlaw package, R package version 0.20.1, 2013.; C.S. Gillespie, Fitting heavy tailed distributions: the poweRlaw package, R package version 0.20.1, 2013.
[20] Li, P.; Zhang, J.; Small, M., Emergence of scaling and assortative mixing through altruism, Physica A, 390, 2192-2197 (2011)
[21] Zhang, L.; Small, M.; Judd, K., Exactly scale-free scale-free networks, Physica A, 433, 182-197 (2015) · Zbl 1400.90075
[22] Small, M.; Li, Y.; Stemler, T.; Judd, K., Growing optimal scale-free networks via likelihood, Phys. Rev. E, 91, Article 042801 pp. (2015)
[23] Blaha, L. M.; Arendt, D. L.; Mohd-Zaid, F., More bang for your research buck: Toward recommender systems for visual analytics, (Proceedings of the Fifth Workshop on Beyond Time and Errors: Novel Evaluation Methods for Visualization. Proceedings of the Fifth Workshop on Beyond Time and Errors: Novel Evaluation Methods for Visualization, BELIV ’14 (2014), ACM: ACM New York, NY, USA), 126-133
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.