10.1. SOCIAL NETWORKS AS GRAPHS
359
article in common. The communities are groups of editors that are interested
in the same subject. Dually, we can build a network of articles, and connect
articles if they have been edited by the same person. Here, we get communities
of articles on similar or related subjects.
In fact, the data involved in Collaborative ﬁltering, as was discussed in
Chapter 9, often can be viewed as forming a pair of networks, one for the
customers and one for the products. Customers who buy the same sorts of
products, e.g., science-ﬁction books, will form communities, and dually, prod-
ucts that are bought by the same customers will form communities, e.g., all
science-ﬁction books.
Other Examples of Social Graphs
Many other phenomena give rise to graphs that look something like social
graphs, especially exhibiting locality. Examples include: information networks
(documents, web graphs, patents), infrastructure networks (roads, planes, water
pipes, powergrids), biological networks (genes, proteins, food-webs of animals
eating each other), as well as other types, like product co-purchasing networks
(e.g., Groupon).
10.1.4
Graphs With Several Node Types
There are other social phenomena that involve entities of diﬀerent types. We
just discussed under the heading of “collaboration networks,” several kinds of
graphs that are really formed from two types of nodes. Authorship networks
can be seen to have author nodes and paper nodes. In the discussion above, we
built two social networks by eliminating the nodes of one of the two types, but
we do not have to do that. We can rather think of the structure as a whole.
For a more complex example, users at a site like del.icio.us place tags on
Web pages. There are thus three diﬀerent kinds of entities: users, tags, and
pages. We might think that users were somehow connected if they tended to
use the same tags frequently, or if they tended to tag the same pages. Similarly,
tags could be considered related if they appeared on the same pages or were
used by the same users, and pages could be considered similar if they had many
of the same tags or were tagged by many of the same users.
The natural way to represent such information is as a k-partite graph for
some k > 1.
We met bipartite graphs, the case k = 2, in Section 8.3.
In
general, a k-partite graph consists of k disjoint sets of nodes, with no edges
between nodes of the same set.
Example 10.2 : Figure 10.2 is an example of a tripartite graph (the case k = 3
of a k-partite graph). There are three sets of nodes, which we may think of
as users {U1, U2}, tags {T1, T2, T3, T4}, and Web pages {W1, W2, W3}. Notice
that all edges connect nodes from two diﬀerent sets. We may assume this graph
represents information about the three kinds of entities. For example, the edge
(U1, T2) means that user U1 has placed the tag T2 on at least one page. Note
