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

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 ex-
amples 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 net-
works, the relationship has a degree. This degree could be discrete; e.g., friends, fam-
ily, 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 un-
directed, 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 as “friends,” is represented
by the edges. For instance, B is friends with A , C , and D .

Figure 10.1 Example of a small social network