10
$\begingroup$

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)

$\endgroup$
2
  • 2
    $\begingroup$ Think about posting this question on cs.stackexchange.com or StackOverflow $\endgroup$
    – Simon
    Jul 1, 2019 at 12:15
  • 1
    $\begingroup$ Yeap, I was thinking it as well, but sometimes it is good to see the OR people's approach as well :) $\endgroup$ Jul 1, 2019 at 12:34

2 Answers 2

8
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.