Data Mining: The Textbook

SP (j) = SP (i) + cij

(19.16)

Therefore, the directed subgraph G^s = (N, A^s) of tight edges is determined, where A^s ⊆ A. The direction of the edge (i, j) is such that SP (j ) > SP (i). Therefore, the subgraph of tight edges is a directed acyclic graph. An example of a base graph, together with its subgraph of tight edges, is illustrated in Fig. 19.5. The edges are annotated with their lengths. In this case, node 0 is assumed to be the source node. The subgraph of tight edges will obviously vary with the choice of the source node. The shortest-path distances SP (i) of node i from source node 0 are illustrated by the first component of the pair of numbers annotating the nodes in Fig. 19.5b.

The number of shortest paths N_s(j ) from the source node s to a given node j is relatively easy to determine from the subgraph of tight edges. This is because the number of paths to a given node is equal to the sum of the number of paths to the nodes incident on it.

Ns(j) =	Ns(i)	(19.17)
	i:(i,j)∈A^s

The algorithm starts by setting N_s(s) = 1 for the source node s. Subsequently, the algorithm performs a breadth first search of the subgraph of tight edges, starting with the source node. The number of paths to each node is computed as the sum of the paths to its ancestors in the directed acyclic graph of tight edges, according to Eq. 19.17. The number of shortest paths to each node, from source node 0, is illustrated in Fig. 19.5b by the second component of the pair of numbers annotating each node.

The next step is to compute the component of the betweenness centrality for both nodes and edges starting at the source node s. Let f_sk(i) be the fraction of shortest paths between nodes s and k, that pass through node i. Let F_sk(i, j) be the fraction of shortest paths

19.3. COMMUNITY DETECTION

633