360
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
U
U
T
T
T
T
W
W
W
1
1
1
2
2
2
3
3
4
Figure 10.2: A tripartite graph representing users, tags, and Web pages
that the graph does not tell us a detail that could be important: who placed
which tag on which page? To represent such ternary information would require
a more complex representation, such as a database relation with three columns
corresponding to users, tags, and 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 diﬀerent 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.
