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

32 Graph Essentials

v 16 v 15 v 14 v 13

v 10 v 9

v 6 v 5

v 2 v 1

v 12 v 11

v 8 v 7

v 4 v 3

Figure 2.18. Bridges. Highlighted edges represent bridges; their removal will increase

the number of components in the graph.

2.6.1 Graph/Tree Traversal

One of the most useful algorithms for graphs are the traversal algorithms

for graphs and special subgraphs, such as trees. Consider a social media site

that has many users, and we are interested in surveying it and computing

the average age of its users. The usual technique is to start from one user

and employ some traversal technique to browse his friends and then these

friends’ friends and so on. The traversal technique guarantees that (1) all

users are visited and (2) no user is visited more than once.

In this section discuss two traversal algorithms:depth-first search (DFS)

andbreadth-first search (BFS).

Depth-First Search (DFS)

Depth-first search (DFS) starts from a nodevi, selects one of its neighbors

vj∈N(vi), and performs DFS onvj before visiting other neighbors in

N(vi). In other words, DFS explores as deep as possible in the graph using

one neighbor before backtracking to other neighbors. Consider a nodevi

that has neighborsvjandvk; that is,vj,vk∈N(vi). Letvj(1)∈N(vj) and

vj(2)∈N(vj) denote neighbors ofvjsuch thatvi =vj(1) =vj(2). Then for

a depth-first search starting atvi, that visitsvjnext, the next set of visited

nodes arevj(1)andvj(2). In other words, a deeper nodevj(1)is preferred to

a neighborvkthat is closer tovi. Depth-first search can be used both for

trees and graphs, but is better visualized using trees. The DFS execution on

a tree is shown in Figure2.19(a).