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

24 Graph Essentials

v 5

v 2

v 1 v 3

v 4

v 6

Figure 2.7. Walk, Path, Trail, Tour, and Cycle. In this figure,v 4 ,v 3 ,v 6 ,v 4 ,v 2 is a walk;

v 4 ,v 3 is a path;v 4 ,v 3 ,v 6 ,v 4 ,v 2 is a trail; andv 4 ,v 3 ,v 6 ,v 4 is both a tour and a cycle.

edges that start atviwe have

∑

x

wi,x= 1 ,∀i,jwi,j≥ 0. (2.15)

The random walk procedure is outlined in Algorithm2.1. The algorithm

starts at a nodev 0 and visits its adjacent nodes based on the transition

probability (weight) assigned to edges connecting them. This procedure

is performed fortsteps (provided to the algorithm); therefore, a walk of

lengthtis generated by the random walk.

v 19

v 10 v 18 v 17

v 11

v 20

v 16

v 6

v 7

v 8

v 9

v 1

v 1

v 6 v 2

v 4

v 5 v 3

v 2 v 5

v 15

v 14

v 4

v 12 v 13

v 3

(a) Hamiltonian Cycle (b) Eulerian Tour

Figure 2.8. Hamiltonian Cycle and Eulerian Tour. In a Hamiltonian cycle we start at one

node, visit all other nodes only once, and return to our start node. In an Eulerian tour, we

traverse all edges only once and return to our start point. In an Eulerian tour, we can visit

a single node multiple times. In this figure,v 1 ,v 5 ,v 3 ,v 1 ,v 2 ,v 4 ,v 6 ,v 2 ,v 3 ,v 4 ,v 5 ,v 6 ,v 1

is an Eulerian tour.