422
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
10.9
Summary of Chapter 10
✦Social-Network Graphs: Graphs that represent the connections in a social
network are not only large, but they exhibit a form of locality, where small
subsets of nodes (communities) have a much higher density of edges than
the average density.
✦Communities and Clusters: While communities resemble clusters in some
ways, there are also signiﬁcant diﬀerences. Individuals (nodes) normally
belong to several communities, and the usual distance measures fail to
represent closeness among nodes of a community. As a result, standard
algorithms for ﬁnding clusters in data do not work well for community
ﬁnding.
✦Betweenness: One way to separate nodes into communities is to measure
the betweenness of edges, which is the sum over all pairs of nodes of the
fraction of shortest paths between those nodes that go through the given
edge. Communities are formed by deleting the edges whose betweenness
is above a given threshold.
✦The Girvan-Newman Algorithm: The Girvan-Newman Algorithm is an
eﬃcient technique for computing the betweenness of edges. A breadth-
ﬁrst search from each node is performed, and a sequence of labeling steps
computes the share of paths from the root to each other node that go
through each of the edges. The shares for an edge that are computed for
each root are summed to get the betweenness.
✦Communities and Complete Bipartite Graphs: A complete bipartite graph
has two groups of nodes, all possible edges between pairs of nodes chosen
one from each group, and no edges between nodes of the same group.
Any suﬃciently dense community (a set of nodes with many edges among
them) will have a large complete bipartite graph.
✦Finding Complete Bipartite Graphs: We can ﬁnd complete bipartite graphs
by the same techniques we used for ﬁnding frequent itemsets. Nodes of
the graph can be thought of both as the items and as the baskets. The
basket corresponding to a node is the set of adjacent nodes, thought of as
items. A complete bipartite graph with node groups of size t and s can
be thought of as ﬁnding frequent itemsets of size t with support s.
✦Graph Partitioning: One way to ﬁnd communities is to partition a graph
repeatedly into pieces of roughly similar sizes. A cut is a partition of the
nodes of the graph into two sets, and its size is the number of edges that
have one end in each set. The volume of a set of nodes is the number of
edges with at least one end in that set.
✦Normalized Cuts: We can normalize the size of a cut by taking the ratio
of the size of the cut and the volume of each of the two sets formed
