Social Media Mining: An Introduction

P1: WQS Trim: 6.125in×9.25in Top: 0.5in Gutter: 0.75in
CUUS2079-02 CUUS2079-Zafarani 978 1 107 01885 3 January 13, 2014 16:38

2.4 Connectivity in Graphs 25

Algorithm 2.1Random Walk

Require:Initial Nodev 0 , Weighted GraphG:(V,E,W), Stepst

1: return Random WalkP

2: state=0;

3: vt=v 0 ;

4: P={v 0 };

5: whilestate<tdo

6: state=state+1;

7:

8: select a random nodevjadjacent tovtwith probabilitywt,j;

9: vt=vj;

10: P=P∪{vj};

11: end while

12: ReturnP

Connectivity.A nodeviisconnectedto nodevj(orvjisreachablefrom

vi) if it is adjacent to it or there exists apathfromvitovj. A graph is

connectedif there exists a path between any pair of nodes in it. In a directed

graph, the graph isweakly connectedif there exists a path between any

pair of nodes, without following the edge directions (i.e., directed edges are

replaced with undirected edges). The graph isstrongly connectedif there

exists a directed path (following edge directions) between any pair of nodes.

Figure2.9shows examples of connected, disconnected, weakly connected,

and strongly connected graphs.

Components.A component in an undirected graph is a subgraph such

that, there exists a path between every pair of nodes inside the compo-

nent. Figure2.10(a) depicts an undirected graph with three components.

A component in a directed graph is strongly connected if, for every pair

v 1 v 2

v 4 v 3

v 1 v 2

v 4 v 3

v 1 v 2

v 6 v 3

v 5 v 4

v 5 v 2

v 1

v 4 v 3

(a) Connected (b) Disconnected (c) Strongly connected (d) Weakly connected

Figure 2.9. Connectivity in Graphs.