368
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
A
B
D
E
G
F
C
Figure 10.8: All the edges with betweenness 4 or more have been removed
Speeding Up the Betweenness Calculation
If we apply the method of Section 10.2.4 to a graph of n nodes and e edges,
it takes O(ne) running time to compute the betweenness of each edge.
That is, BFS from a single node takes O(e) time, as do the two labeling
steps. We must start from each node, so there are n of the computations
described in Section 10.2.4.
If the graph is large – and even a million nodes is large when the
algorithm takes O(ne) time – we cannot aﬀord to execute it as suggested.
However, if we pick a subset of the nodes at random and use these as
the roots of breadth-ﬁrst searches, we can get an approximation to the
betweenness of each edge that will serve in most applications.
of the following nodes that pass through each of the edges. (a) A
(b) B.
Exercise 10.2.2: Using symmetry, the calculations of Exercise 10.2.1 are all
you need to compute the betweenness of each edge. Do the calculation.
Exercise 10.2.3: Using the betweenness values from Exercise 10.2.2, deter-
mine reasonable candidates for the communities in Fig. 10.9 by removing all
edges with a betweenness above some threshold.
10.3
Direct Discovery of Communities
In the previous section we searched for communities by partitioning all the in-
dividuals in a social network. While this approach is relatively eﬃcient, it does
have several limitations. It is not possible to place an individual in two diﬀerent
communities, and everyone is assigned to a community. In this section, we shall
see a technique for discovering communities directly by looking for subsets of
the nodes that have a relatively large number of edges among them. Interest-
ingly, the technique for doing this search on a large graph involves ﬁnding large
frequent itemsets, as was discussed in Chapter 6.
