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

40 Graph Essentials

v 1

14

12

4

9

16

20

13

47

v 2 v 4

v 3

s t

Figure 2.22. A Sample Flow Network.

For instance, in social media sites where users have daily limits (the capac-

ity, here) of sending messages (the flow) to others, what is the maximum

number of messages the network should be prepared to handle at any time?

Before we delve into the details, let us formally define a flow network.

Flow Network

A flow networkG(V,E,C)^2 is a directed weighted graph, where we have

the following:

 ∀e(u,v)∈E,c(u,v)≥0 defines the edge capacity.

 When (u,v)∈E,(v,u) ∈E(opposite flow is impossible).

SOURCE AND  sdefines thesourcenode andtdefines thesinknode. An infinite

SINK supply of flow is connected to the source.

A sample flow network, along with its capacities, is shown in Figure2.22.

Flow

Given edges with certain capacities, we can fill these edges with the flow up

to their capacities. This is known as thecapacity constraint. Furthermore,

we should guarantee that the flow that enters any node other than source

sand sinktis equal to the flow that exits it so that no flow is lost (flow

conservation constraint). Formally,

 ∀(u,v)∈E,f(u,v)≥0 defines the flow passing through that edge.

 ∀(u,v)∈E,0≤f(u,v)≤c(u,v) (capacity constraint).

 ∀v∈V,v ∈{s,t},∑

k:(k,v)∈E f(k,v)=

∑

l:(v,l)∈Ef(v,l) (flow con-

servation constraint).

Commonly, to visualize an edge with capacitycand flowf, we use the

notationf/c. A sample flow network with its flows and capacities is shown

in Figure2.23.