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.7 Exercises 103

person on a first-name basis. Otherwise, they had to forward it to someone

who was more likely to know the target. The results showed that the letters

were on average forwarded 5.5 to 6 times until they reached the target in

Boston. Other recent research on small-world model dynamics can be found

in [Watts, 1999, 2002 ].

Price [1965, 1976] was among the first who described power laws

observed in citation networks and models capable of generating them.

Power-law distributions are commonly found in social networks and the

web [Faloutsos et al., 1999;Mislove et al., 2007]. The first developers of

preferential attachment models wereYule [1925], who described these mod-

els for generating power-law distributions in plants, and Herbert A.Simon

[1955], who developed these models for describing power laws observed

in various phenomena: distribution of words in prose, scientists by cita-

tions, and cities by population, among others. Simon used what is known as

themaster equationto prove that preferential attachment models generate

power-law degree distributions. A more rigorous proof for estimating the

power-law exponent of the preferential attachment model using the master

equation method can be found in [Newman, 2010]. The preferential attach-

ment model introduced in this chapter has a fixed exponentb=3, but,

as mentioned, real-world networks have exponents in the range [2,3]. To

solve this issue, extensions have been proposed in [Krapivsky, Redner, and

Leyvraz, 2000;Albert and Barabasi, 2000 ́ ].

4.7 Exercises

Properties of Real-World Networks

1. Ascale invariantfunctionf(.) is one such that, for a scalarα,

f(αx)=αcf(x), (4.34)

for some constantc. Prove that the power-law degree distribution is

scale invariant.

Random Graphs

2. Assuming that we are interested in a sparse random graph, what should
   we choose as ourpvalue?


3. Construct a random graph as follows. Start withnnodes and a given
   k. Generate all the possible combinations ofknodes. For each combi-
   nation, create ak-cycle with probability(nα− 1
   2 )

, whereαis a constant.

Calculate the node mean degree and the clustering coefficient.