Database Reference
In-Depth Information
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 ques-
tion 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
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 different 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 efficient algorithms for discovering other properties of
graphs. We look at “simrank,” a way to discover similarities among nodes of a graph. We
explore triangle counting as a way to measure the connectedness of a community. We give
efficient algorithms for exact and approximate measurement of the neighborhood sizes of
nodes in a graph. Finally, we look at efficient algorithms for computing the transitive clos-
ure.
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 so-
cial networks that occur in practice.
