Database Reference
In-Depth Information
form communities, and dually, products that are bought by the same customers will form
communities, e.g., all science-fiction topics.
Other Examples of Social Graphs
Many other phenomena give rise to graphs that look something like social graphs, es-
pecially exhibiting locality. Examples include: information networks (documents, web
graphs, patents), infrastructure networks (roads, planes, water pipes, powergrids), biolo-
gical 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 different 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 deli.cio.us place tags on Web pages.
There are thus three different 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 {
U
1
, U
2
}, tags {
T
1
,
T
2
, T
3
, T
4
}, and Web pages {
W
1
, W
2
, W
3
}. Notice that all edges connect nodes from two
different sets. We may assume this graph represents information about the three kinds of
entities. For example, the edge (
U
1
, T
2
) means that user
U
1
has placed the tag
T
2
on at
least one page. Note 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 correspond-
ing to users, tags, and pages.
□
