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

96 Network Models

1

0.8

0.6

0.4

0.2

0

0.0001 0.001 0.01

p

L(p) / L(0)

C(p) /C(0)

0.1 1

Figure 4.5. Clustering Coefficient and Average Path Length Change in the Small-World

Model (from [Watts and Strogatz, 1997]). In this figure,C(p)/C(0) denotes the cluster-

ing coefficient of a small-world model, withβ=pover the regular lattice. Similarly,

L(p)/L(0) denotes the average path length of a small-world model over the regular

lattice. Since models with a high clustering coefficient and small average path length

are desired,βvalues in range 0. 01 ≤β=p≤ 0 .1 are preferred.

As shown in the figure, the value forC(p) stays high untilpreaches

0.1 (10% rewired) and then decreases rapidly to a value around zero. Since

a high clustering coefficient is required in generated graphs,β≤ 0 .1is

preferred.

Average Path Length

The same procedure can be done for the average path length. The average

path length in a regular lattice is

n

2 c

. (4.23)

We denote this value asL(0). The average path length in a random graph

islnlnnc. We denoteL(p) as the average path length for a small-world model

whereβ=p. UnlikeC(p), no analytical formula for comparingL(p)to

L(0) exists; however, the relation can be computed empirically for different

values ofp. Similar toC(p), we plotLL(0)(p)in Figure4.5. As shown in the

figure, the average path length decays sooner than the clustering coefficient

and becomes stable when around 1% of edges are rewired. Since we require

small average path lengths in the generated graphs,β≥ 0 .01 is preferred.