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

44 Graph Essentials

v 1

v 6

v 2

v 7

v 3

v 8

v 4

v 5

VL VR VL VR

v 9

v 1

v 6

v 2

v 7

v 3

v 8

v 4

v 5 v^9

Figure 2.26. Maximum Bipartite Matching.

The algorithm searches for augmenting paths, if possible, in the resid-

ual and augments flows in the original flow network. Path finding can be

achieved by any graph traversal algorithm, such as BFS.

2.6.5 Maximum Bipartite Matching

Suppose we are trying to solve the following problem in social media:

Given n products and m users such that some users are only interested in certain

products, find the maximum number of products that can be bought by users.

The problem is graphically depicted in Figure2.26. The nodes on the

left represent products and the nodes on the right represent users. Edges

represent the interest of users in products. Highlighted edges demonstrate

MATCHING amatching, where products are matched with users. The figure on the left

depicts a matching and the figure on the right depicts amaximum matching,

where no more edges can be added to increase the size of the matching.

This problem can be reformulated as a bipartite graph problem. Given

a bipartite graph, whereVLandVRrepresent the left and right node sets

(V=VL∪VR), andErepresents the edges, we define amatching M,

M⊂E, such that, for allv∈V, such that each node inVappears in at

most one edge inM. In other words, either the node is matched appears in

an edgee∈Mor not. Amaximum bipartite matching MMaxis a matching

such that, for any other matchingM′in the graph,|MMax|≥|M′|.

Here we solve the maximum bipartite matching problem using the previ-

ously discussed Ford-Fulkerson maximum flow technique. The problem can