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

90 Network Models

We also have

nlim→∞

(

n− 1

d

)

=nlim→∞

(n−1)!

(n− 1 −d)!d!

=nlim→∞

((n−1)×(n−2)×···(n−d))(n− 1 −d)!

(n− 1 −d)!d!

=nlim→∞

((n−1)×(n−2)×···(n−d))

d!

≈

(n−1)d

d!

. (4.10)

We can compute the degree distribution of random graphs in the limit

by substituting Equations4.10,4.9, and4.4in Equation4.8,

nlim→∞P(dv=d)=nlim→∞

(

n− 1

d

)

pd(1−p)n−^1 −d

=

(n−1)d

d!

(

c

n− 1

)d

e−c=e−c

cd

d!

, (4.11)

which is basically thePoisson distributionwith meanc. Thus, in the limit,

random graphs generate Poisson degree distribution, which differs from the

power-law degree distribution observed in real-world networks.

Clustering Coefficient

Proposition 4.6.In a random graph generated by G(n,p), the expected

local clustering coefficient for nodevis p.

Proof.The local clustering coefficient for nodevis

C(v)=

number of connected pairs ofv’s neighbors

number of pairs ofv’s neighbors

. (4.12)

However,vcan have different degrees depending on the edges that are

formed randomly. Thus, we can compute the expected value forC(v):

E(C(v))=

∑n−^1

d= 0

E(C(v)|dv=d)P(dv=d). (4.13)