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.
|Titolo:||Revisiting the power-law degree distribution for social graph analysis|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Data di pubblicazione:||lug-2010|
|Enti collegati al convegno:||ACM|
|Digital Object Identifier (DOI):||10.1145/1835698.1835791|
|Tipologia:||Book Part (author)|
|Appare nelle tipologie:||03 - Contributo in volume|