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

26 Graph Essentials

v 2 v 3 v 5

v 4 v 7

v 6

v 1 v 2 v 3

v 4 v 5 v 6

v 7 v 8 v 9

v 8

v 1

(a) A Graph with Three Components (b) A Graph with Three Strongly

Connected Components

Figure 2.10. Components in Undirected and Directed Graphs.

of nodesvandu, there exists a directed path fromvtouand one fromu

tov. The component is weakly connected if replacing directed edges with

undirected edges results in a connected component. A graph with three

strongly connected components is shown in Figure2.10(b).

Shortest Path.When a graph is connected, multiple paths can exist between

any pair of nodes. Often, we are interested in the path that has the shortest

length. This path is called theshortest path. Applications for shortest paths

include GPS routing, where users are interested in the shortest path to

their destination. In this chapter, we denote the length of the shortest path

between nodesviandvjasli,j. The concept of the neighborhood of a node

vican be generalized using shortest paths. Ann-hop neighborhoodof node

viis the set of nodes that are withinnhops distance from nodevi. That is,

their shortest path tovihas length less than or equal ton.

Diameter.Thediameterof a graph is defined as the length of the longest

shortest path between any pair of nodes in the graph. It is defined only for

connected graphs because the shortest path might not exist in disconnected

graphs. Formally, for a graphGthe diameter is defined as

diameterG= max

(vi,vj)∈V×V

li,j. (2.16)

2.5 Special Graphs

Using general concepts defined thus far, many special graphs can be defined.

These special graphs can be used to model different problems. We review

some well-known special graphs and their properties in this section.