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

4.4 Preferential Attachment Model 99

4.4.1 Properties of the Preferential Attachment Model

Degree Distribution

We first demonstrate that the preferential attachment model generates

scale-free networks and can therefore model real-world networks. Empir-

ical evidence found by simulating the preferential attachment model

suggests that this model generates a scale-free network with exponent

b= 2. 9 ± 0 .1[Barabasi and Albert, 1999 ́ ]. Theoretically, amean-field

[Newman, Barabasi, and Watts, 2006] proof can be provided as follows.

Letdidenote the degree for nodevi. The probability of an edge con-

necting from a new node toviis

P(vi)=

di

∑

jdj

. (4.24)

The expected increase to the degree ofviis proportional todi(this is true

on average). Assuming a mean-field setting, the expected temporal change

indiis

ddi

dt

=mP(vi)=

mdi

∑

jdj

=

mdi

2 mt

=

di

2 t

. (4.25)

Note that at each time step,medges are added; therefore,mtedges

are added over time, and the degree sum

∑

jdjis 2mt. Rearranging and

solving this differential equation, we get

di(t)=m

(

t

ti

) 0. 5

. (4.26)

Here,tirepresents the time thatviwas added to the network, and because

we set the expected degree tomin preferential attachment, thendi(ti)=m.

The probability thatdiis less thandis

P(di(t)<d)=P(ti>m^2 t/d^2 ). (4.27)

Assuming uniform intervals of adding nodes,

P(ti>m^2 t/d^2 )= 1 −P(ti≤m^2 t/d^2 )= 1 −

m^2 t

d^2

1

(t+m 0 )

. (4.28)

The factor(t+^1 m 0 )shows the probability that one time step has passed

because, at the end of the simulation,t+m 0 nodes are in the network. The

probability density forP(d)

P(d)=

∂P(di(t)<d)

∂d

, (4.29)