Revisiting Degree Distribution Models for Social Graph Analysis

Details Revisiting Degree Distribution Models for Social Graph Analysis Revisiting Degree Distribution Models for Social Graph Analysis

2011-07-29

arxiv.org/abs/1108.0027v1

Computer Science

Social and Information Networks

Scientific paper

Degree distribution models are incredibly important tools for analyzing and understanding the structure and formation of social networks, and can help guide the design of efficient graph algorithms. In particular, the Power-law degree distribution has long been used to model the structure of online social networks, and is the basis for algorithms and heuristics in graph applications such as influence maximization and social search. Along with recent measurement results, our interest in this topic was sparked by our own experimental results on social graphs that deviated significantly from those predicted by a Power-law model. In this work, we seek a deeper understanding of these deviations, and propose an alternative model with significant implications on graph algorithms and applications. We start by quantifying this artifact using a variety of real social graphs, and show that their structures cannot be accurately modeled using elementary distributions including the Power-law. Instead, we propose the Pareto-Lognormal (PLN) model, verify its goodness-of-fit using graphical and statistical methods, and present an analytical study of its asymptotical differences with the Power-law. To demonstrate the quantitative benefits of the PLN model, we compare the results of three wide-ranging graph applications on real social graphs against those on synthetic graphs generated using the PLN and Power-law models. We show that synthetic graphs generated using PLN are much better predictors of degree distributions in real graphs, and produce experimental results with errors that are orders-of-magnitude smaller than those produced by the Power-law model.

Affiliated with

Also associated with

No associations

Rating

Revisiting Degree Distribution Models for Social Graph Analysis does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Revisiting Degree Distribution Models for Social Graph Analysis, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Revisiting Degree Distribution Models for Social Graph Analysis will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-135881