Chapter 10
Mining Social-Network
Graphs
There is much information to be gained by analyzing the large-scale data that
is derived from social networks. The best-known example of a social network
is the “friends” relation found on sites like Facebook. However, as we shall see
there are many other sources of data that connect people or other entities.
In this chapter, we shall study techniques for analyzing such networks. An
important question about a social network is how to identify “communities,”
that is, subsets of the nodes (people or other entities that form the network)
with unusually strong connections. Some of the techniques used to identify
communities are similar to the clustering algorithms we discussed in Chapter 7.
However, communities almost never partition the set of nodes in a network.
Rather, communities usually overlap. For example, you may belong to several
communities of friends or classmates. The people from one community tend to
know each other, but people from two diﬀerent communities rarely know each
other. You would not want to be assigned to only one of the communities, nor
would it make sense to cluster all the people from all your communities into
one cluster.
Also in this chapter we explore eﬃcient algorithms for discovering other
properties of graphs.
We look at “simrank,” a way to discover similarities
among nodes of a graph.
One of the interesting applications of simrank is
that it gives us a way to identify communities as sets of “similar” nodes. We
then explore triangle counting as a way to measure the connectedness of a
community. In addition, we give eﬃcient algorithms for exact and approximate
measurement of the neighborhood sizes of nodes in a graph, and we look at
eﬃcient algorithms for computing the transitive closure.
355
