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.6 Graph Algorithms 31

v 1

v 6 v 2

v 5 v 3

v 4

Figure 2.17. Regular Graph withk=3.

is associated with an affiliation, an edge connects the corresponding nodes.

A sample affiliation network is shown in Figure2.16(b).

2.5.6 Regular Graphs

Aregulargraph is one in which all nodes have the same degree. A regular

graph where all nodes have degree 2 is called a 2-regular graph. More

generally, a graph where all nodes have degreekis called ak-regular graph.

Regular graphs can be connected or disconnected. Complete graphs are

examples of regular graphs, where allnnodes have degreen−1 (i.e.,

k=n−1). Cycles are also regular graphs, wherek=2. Another example

fork=3 is shown in Figure2.17.

2.5.7 Bridges

Consider a graph with several connected components. Edges in this graph

whose removal will increase the number of connected components are

calledbridges. As the name suggests, these edges act as bridges between

connected components. The removal of these edges results in the discon-

nection of formerly connected components and hence an increase in the

number of components. An example graph and all its bridges are depicted

in Figure2.18.

2.6 Graph Algorithms

In this section, we review some well-known algorithms for graphs, although

they are only a small fraction of the plethora of algorithms related to graphs.