Many-to-many Breadth First Search

Question

There is a directed social network with large number of nodes and arcs and there are many instances of the network (nodes are same but arcs change in each instance). You can think of it as a stochastic network with probabilities on the arcs, so that in each scenario you end up a different instance of the network (in terms of arcs).

For each node in the network and for each instance we run BFS to determine the successor set. As you may realize we need to run the BFS (V.R) times where V is the number of nodes and R is the number of instances. However for a given instance, there may be a much efficient way of doing the BFS. For instance during the steps of BFS if we meet a node whose successor set is already calculated, we directly add that whole set and do not continue further in that direction. This improves the performance when we consider all the nodes, however it still takes too much time for large networks.

So the challenge is: Is there an efficient all-nodes BFS algorithm that computes the BFS sets of all nodes, that is faster than the above method? (Similar to the comparison of Dijkstra and Floyd-Warshall for shortest paths)

Answer 1

Since your graph is directed you can first compute the strongly connected components in linear time $O(n+m)$, contract the components, and then run BFS on the contracted graph. For each strongly connected component with $c$ nodes this saves you $c-1$ BFS calls.

Also, the resulting graph is a DAG, so processing it in reverse topological order the reachable nodes of a node are given by the union of the reachable nodes of the successors and the node itself.

Answer 2

I am not sure. But this is an obvious case where parallelization will help (per source node, and instance).