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.3 Small-World Model 93

v 1

v 2

v 3

v 4

v 5

v 6

v 7

v 8

v 9

v 10

Figure 4.4. Regular Lattice of Degree 4.

4.3 Small-World Model

The assumption behind the random graph model is that connections in

real-world networks are formed at random. Although unrealistic, random

graphs can model average path lengths in real-world networks properly, but

underestimate the clustering coefficient. To mitigate this problem, Duncan

J. Watts and Steven Strogatz in 1997 proposed the small-world model.

In real-world interactions, many individuals have a limited and often at

least, a fixed number of connections. Individuals connect with their parents,

brothers, sisters, grandparents, and teachers, among others. Thus, instead of

assuming random connections, as we did in random graph models, one can

assume anegalitarianmodel in real-world networks, where people have the

same number of neighbors (friends). This again is unrealistic; however, it

models more accurately the clustering coefficient of real-world networks. In REGULAR

graph theory terms, this assumption is equivalent to embedding individuals RING LATTICE

in aregular network. A regular (ring) lattice is a special case of regular

networks where there exists a certain pattern for howorderednodes are

connected to one another. In particular, in a regular lattice of degreec, nodes

are connected to their previousc/2 and followingc/2 neighbors. Formally,

for node setV={v 1 ,v 2 ,v 3 ,...,vn}, an edge exists between nodeviand

vjif and only if

0 <|i−j|≤c/ 2. (4.19)

A regular lattice of degree 4 is shown in Figure4.4.