Social Media Mining: An Introduction

P1: WQS Trim: 6.125in×9.25in Top: 0.5in Gutter: 0.75in
CUUS2079-04 CUUS2079-Zafarani 978 1 107 01885 3 January 13, 2014 16:54

82 Network Models

Degree

pk Log (p

k)

Log (Degree)

(a) Power-Law Degree Distribution (b) Log-Log Plot of Power-Law

Degree Distribution

Figure 4.1. Power-Law Degree Distribution and Its Log-Log Plot.

wherebis the power-law exponent andais the power-law intercept. A

power-law degree distribution is shown in Figure4.1(a).

Taking the logarithm from both sides of Equation4.1, we get

lnpk=−blnk+lna. (4.2)

Equation 4.2 shows that the log-log plot of a power-law distribution is a

straight line with slope−band intercept lna(see Figure4.1(b)). This also

reveals a methodology for checking whether a network exhibits a power-law

distribution.^1 We can do the following:

 Pick a popularity measure and compute it for the whole network. For

instance, we can take the number of friends in a social network as a

measure. We denote the measured value ask.

 Computepk, the fraction of individuals having popularityk.

 Plot a log-log graph, where thex-axis represents lnkand they-axis

represents lnpk.

 If a power-law distribution exists, we should observe a straight line in

the plot.

Figure4.2depicts some log-log graphs for the number of friends on

real-world networks. In all networks, a linear trend is observed denoting a

power-law degree distribution.

Networks exhibiting power-law degree distribution are often calledscale-

SCALE-FREE freenetworks. Since the majority of social networks are scale-free, we are

NETWORKS interested in models that can generate synthetic networks with a power-law

degree distribution.