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 45

v 1

v 6

v 2

v 3

v 4

v 7

v 8

v 9

s t

v 5

VL VR

Figure 2.27. Maximum Bipartite Matching Using Max Flow.

be easily solved by creating a flow graphG(V′,E′,C) from our bipartite

graphG(V,E), as follows:

 SetV′=V∪{s}∪{t}.

 Connect all nodes inVLtosand all nodes inVRtot,

E′=E∪{(s,v)|v∈VL}∪{(v,t)|v∈VR}. (2.25)

 Setc(u,v)=1,∀(u,v)∈E′.

This procedure is graphically shown in Figure2.27. By solving the max

flow for this flow graph, the maximum matching is obtained, since the

maximum number of edges need to be used betweenVLandVRfor the flow

to become maximum.^4

2.6.6 Bridge Detection

As discussed in Section2.5.7,bridgesorcut edges are edges whose CUT-EDGES

removal makes formerly connected components disconnected. Here we list

a simple algorithm for detecting bridges. This algorithm is computationally

expensive, but quite intuitive. More efficient algorithms have been described

for the same task.

Since we know that, by removing bridges, formerly connected compo-

nents become disconnected, one simple algorithm is to remove edges one

by one and test if the connected components become disconnected. This

algorithm is outlined in Algorithm2.7.