Mining Social-Network Graphs - Mining of Massive Datasets - page 331

Figure 10.2 A tripartite graph representing users, tags, and Web pages

10.1.5 Exercises for Section 10.1

EXERCISE 10.1.1 It is possible to think of the edges of one graph G as the nodes of another
graph G ′. We construct G ′ from G by the dual construction :

(1) If ( X, Y ) is an edge of G , then XY , representing the unordered set of X and Y is a node
of G ′. Note that XY and Y X represent the same node of G ′, not two different nodes.
(2) If ( X, Y ) and ( X, Z ) are edges of G , then in G ′ there is an edge between XY and XZ .
That is, nodes of G ′ have an edge between them if the edges of G that these nodes
represent have a node (of G ) in common.

(a) If we apply the dual construction to a network of friends, what is the interpretation
of the edges of the resulting graph?
(b) Apply the dual construction to the graph of Fig. 10.1 .
! (c) How is the degree of a node XY in G ′ related to the degrees of X and Y in G ?
!! (d) The number of edges of G ′ is related to the degrees of the nodes of G by a certain
formula. Discover that formula.
! (e) What we called the dual is not a true dual, because applying the construction to
G ′ does not necessarily yield a graph isomorphic to G . Give an example graph G
where the dual of G ′ is isomorphic to G and another example where the dual of G ′
is not isomorphic to G .

10.2 Clustering of Social-Network Graphs
An important aspect of social networks is that they contain communities of entities that
are connected by many edges. These typically correspond to groups of friends at school or
groups of researchers interested in the same topic, for example. In this section, we shall
consider clustering of the graph as a way to identify communities. It turns out that the