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

Figure 10.24 A graph for exercises on neighborhoods and transitive closure
EXERCISE 10.8.2 The smart transitive-closure algorithm breaks paths of any length into
head and tail of specific lengths. What are the head and tail lengths for paths of length 7, 8,
and 9?
EXERCISE 10.8.3 Consider the running example of a social network, last shown in Fig.
10.23 . Suppose we use one hash function h which maps each node (capital letter) to its
ASCII code. Note that the ASCII code for A is 01000001, and the codes for B, C, . . . are
sequential, 01000010 , 01000011, . . . .
(a) Using this hash function, compute the values of R for each node and radius 1. What are
the estimates of the sizes of each neighborhood? How do the estimates compare with
reality?
(b) Next, compute the values of R for each node and radius 2. Again compute the estim-
ates of neighborhood sizes and compare with reality.
(c) The diameter of the graph is 3. Compute the value of R and the size estimate for the
set of reachable nodes for each of the nodes of the graph.
(d) Another hash function g is one plus the ASCII code for a letter. Repeat (a) through (c)
for hash function g . Take the estimate of the size of a neighborhood to be the average
of the estimates given by h and g . How close are these estimates?
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 significant differen-
ces. 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 finding clusters in data do not work
well for community finding.
✦ 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.