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

30 Graph Essentials

v 1

v 2

v 4 v 3

v 5

v 1

v 2

v 4 v 3

(a) Planar Graph (b) Non-planar Graph

Figure 2.15. Planar and Nonplanar Graphs.

set. Formally,

V=VL∪VR, (2.18)

VL∩VR=∅, (2.19)

E⊆VL×VR. (2.20)

Figure2.16(a) shows a sample bipartite graph. In this figure,VL=

{v 1 ,v 2 }andVR={v 3 ,v 4 ,v 5 }.

In social media,affiliation networksare well-known examples of bipar-

tite graphs. In these networks, nodes in one part (VLorVR) represent indi-

viduals, and nodes in the other part represent affiliations. If an individual

v 1 v (^3) Kyle
Kate
Kathy
Book Club
Food Bank
Volunteers
v 2 v 4
v 5
(a) Bipartite Graph (b) Affiliation Network
Figure 2.16. Bipartite Graphs and Affiliation Networks.