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

88 Network Models

c^2 nodes

c nodes

Figure 4.3. Nodes Visited by Movingn-hops away in a Random Graph.cdenotes the

expected node degree.

It is proven that in random graphs phase transition occurs whenc=1;

that is,p= 1 /(n−1).

Proposition 4.4.In random graphs, phase transition happens at c= 1.

Proof.(Sketch) Consider a random graph with expected node degreec,

wherec=p(n−1). In this graph, consider anyconnectedset of nodes

Sand consider the complement setS ̄=V−S. For the sake of our proof,

we assume that|S||S|. Given any nodevinS, if we move one hop

(edge) away fromv, we visit approximatelycnodes. Following the same

argument, if we move one hop away from nodes inS, we visit approximately

|S|cnodes. Assuming|S|is small, the nodes inSonly visit nodes inS ̄,

and when moving one hop away fromS, the set of nodes “guaranteed to

be connected” gets larger by a factorc(see Figure4.3). The connected

set of visited nodes getsc^2 times larger when moving two hops and so on.

Now, in the limit, if we want this component of visited nodes to become

the largest connected component, then after travelingnhops, we must

have

cn≥1 or equivalentlyc≥ 1. (4.7)

Otherwise (i.e.,c<1), the number of visited nodes dies out exponentially.

Hence, phase transition happens atc= 12.