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 23

uv w

Figure 2.6. Adjacent Nodes and Incident Edges. In this graphuandv,aswellasvand

w, are adjacent nodes, and edges (u,v)and(v,w) are incident edges.

beginning of the other; that is, the edge directions must match for edges to

be incident.

Traversing an Edge.An edge in a graph can betraversedwhen one starts at

one of its end-nodes, moves along the edge, and stops at its other end-node.

So, if an edgee(a,b) connects nodesaandb, then visitingecan start ata

and end atb. Alternatively, in an undirected graph we can start atband end

the visit ata.

Walk, Path, Trail, Tour, and Cycle.A walk is a sequence of incident

edges traversed one after another. In other words, if in a walk one traverses

edgese 1 (v 1 ,v 2 ),e 2 (v 2 ,v 3 ),e 3 (v 3 ,v 4 ),...,en(vn,vn+ 1 ), we havev 1 as the

walk’s starting node andvn+ 1 as the walk’s ending node. When a walk does

not end where it started (v 1    =vn+ 1 ) then it is called anopen walk. When OPEN WALK

AND

CLOSED

WALK

a walk returns to where it was started (v 1 =vn+ 1 ), it is called aclosed

walk. Similarly, a walk can be denoted as a sequence of nodes,v 1 ,v 2 ,

v 3 ,...,vn. In this representation, the edges that are traversed aree 1 (v 1 ,v 2 ),

e 2 (v 2 ,v 3 ),...,en− 1 (vn− 1 ,vn). The length of a walk is the number of edges

traversed during the walk and in our case isn−1.

Atrailis a walk where no edge is traversed more than once; therefore,

all walk edges are distinct. A closed trail (one that ends where it started) is

called atourorcircuit.

A walk where nodes and edges are distinct is called apath, and a closed

path is called acycle. The length of a path or cycle is the number of edges

traversed in the path or cycle. In a directed graph, we havedirected paths

because traversal of edges is only allowed in the direction of the edges. In

Figure2.7,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.

A graph has aHamiltoniancycle if it has a cycle such that all the

nodes in the graph are visited. It has anEuleriantour if all the edges are

traversed only once. Examples of a Hamiltonian cycle and an Eulerian tour

are provided in Figure2.8.

One can perform arandom walkon a weighted graph, where nodes are RANDOM

visited randomly. The weight of an edge, in this case, defines the probability WALK

of traversing it. For this to work correctly, we must make sure that for all