356
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
10.1
Social Networks as Graphs
We begin our discussion of social networks by introducing a graph model. Not
every graph is a suitable representation of what we intuitively regard as a social
network.
We therefore discuss the idea of “locality,” the property of social
networks that says nodes and edges of the graph tend to cluster in communities.
This section also looks at some of the kinds of social networks that occur in
practice.
10.1.1
What is a Social Network?
When we think of a social network, we think of Facebook, Twitter, Google+,
or another website that is called a “social network,” and indeed this kind of
network is representative of the broader class of networks called “social.” The
essential characteristics of a social network are:
1. There is a collection of entities that participate in the network. Typically,
these entities are people, but they could be something else entirely. We
shall discuss some other examples in Section 10.1.3.
2. There is at least one relationship between entities of the network. On
Facebook or its ilk, this relationship is called friends.
Sometimes the
relationship is all-or-nothing; two people are either friends or they are
not. However, in other examples of social networks, the relationship has a
degree. This degree could be discrete; e.g., friends, family, acquaintances,
or none as in Google+. It could be a real number; an example would
be the fraction of the average day that two people spend talking to each
other.
3. There is an assumption of nonrandomness or locality. This condition is
the hardest to formalize, but the intuition is that relationships tend to
cluster. That is, if entity A is related to both B and C, then there is a
higher probability than average that B and C are related.
10.1.2
Social Networks as Graphs
Social networks are naturally modeled as graphs, which we sometimes refer to
as a social graph. The entities are the nodes, and an edge connects two nodes
if the nodes are related by the relationship that characterizes the network. If
there is a degree associated with the relationship, this degree is represented by
labeling the edges. Often, social graphs are undirected, as for the Facebook
friends graph. But they can be directed graphs, as for example the graphs of
followers on Twitter or Google+.
Example 10.1 : Figure 10.1 is an example of a tiny social network.
The
entities are the nodes A through G. The relationship, which we might think of
