The study of complex networks led to the belief that the connectivity of network nodes generally follows a Power-law distribution. In this work, we show that modeling large-scale online social networks using a Power-law distribution produces significant fitting errors. We propose the use of a more accurate node degree distribution model based on the Pareto-Lognormal distribution. Using large datasets gathered from Facebook, we show that the Power-law curve produces a significant over-estimation of the number of high degree nodes, leading researchers to erroneous designs for a number of social applications and systems, including shortest-path prediction, community detection, and influence maximization. We provide a formal proof of the error reduction using the Pareto-Lognormal distribution, which we envision will have strong implications on the correctness of social systems and applications.
Revisiting the power-law degree distribution for social graph analysis / A. Sala, H. Zheng, B. Y. Zhao, S. Gaito, G. P. Rossi - In: PODC '10 : ACM symposium on principles of distributed computing, Zurich, Switzerland, july 25 - 28, 2010New York : ACM, 2010 Jul. - ISBN 9781605588889. - pp. 400-401 (( Intervento presentato al 29th. convegno Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing tenutosi a Zurigo, CH nel 2010.
Revisiting the power-law degree distribution for social graph analysis
S. Gaito;G. P. Rossi
2010
Abstract
The study of complex networks led to the belief that the connectivity of network nodes generally follows a Power-law distribution. In this work, we show that modeling large-scale online social networks using a Power-law distribution produces significant fitting errors. We propose the use of a more accurate node degree distribution model based on the Pareto-Lognormal distribution. Using large datasets gathered from Facebook, we show that the Power-law curve produces a significant over-estimation of the number of high degree nodes, leading researchers to erroneous designs for a number of social applications and systems, including shortest-path prediction, community detection, and influence maximization. We provide a formal proof of the error reduction using the Pareto-Lognormal distribution, which we envision will have strong implications on the correctness of social systems and applications.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.