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 97

Table 4.5.A Comparison between Real-World Networks and Simulated Graphs

Using the Small-World Model. In this table C denotes the average clustering

coefficient. The last two columns show the average path length and the clustering

coefficient for the small-world graph simulated for the real-world network. Both

average path lengths and clustering coefficients are modeled properly

Original Network Simulated Graph

Average Average Path Average Path

Network Size Degree Length C Length C

Film Actors 225,226 61 3.65 0.79 4.2 0.73

Medline Coauthorship 1,520,251 18.1 4.6 0.56 5.1 0.52

E. Coli 282 7.35 2.9 0.32 4.46 0.31

C. Elegans 282 14 2.65 0.28 3.49 0.37

4.3.2 Modeling Real-World Networks with the Small-World Model

A desirable model for a real-world network should generate graphs with

high clustering coefficients and short average path lengths. As shown in

Figure4.5,for0. 01 ≤β≤ 0 .10, the small-world network generated is

acceptable, in which the average path length is small and the clustering

coefficient is still high. Given a real-world network in which average degree

cand clustering coefficientCare given, we setC(p)=Cand determineβ

using Equation4.22.Givenβ,c, andn(size of the real-world network), we

can simulate the small-world model.

Table4.5demonstrates the simulation results for various real-world net-

works. As observed in the table, the small-world model generates a realistic

clustering coefficient and small average path length. Note that the small-

world model is still incapable of generating a realistic degree distribution in

the simulated graph. To generate scale-free networks (i.e., with a power-law

degree distribution), we introduce the preferential attachment model next.

4.4 Preferential Attachment Model

There exist a variety of scale-free network-modeling algorithms. A well-

established one is the model proposed byBarab ́asi and Albert [1999]. The

model is calledpreferential attachmentor sometimes the Bar ́abasi-Albert

(BA) model and is as follows:

When new nodes are added to networks, they are more likely to connect to existing nodes

that many others have connected to.

This connection likelihood is proportional to the degree of the node

that the new node is aiming to connect to. In other words, arich-get-

richerphenomenon oraristocrat networkis observed where the higher the