0
$\begingroup$

I am studying Brandes' betweenness algorithm for weighted undirected graph. I am not sure that, in Algorithm 1 (which is based on Dijkstra's shortest path algorithm),

  • If a node is first encountered, then we have to check d[neighbor_node] < 0. But if not, do we have to check d[neighbor_node] > d[current] + length(current,neighbor_node)?

  • If greater, then do I have to delete previous updates like Queue, Pre[] and others?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Could you please provide some background information about Brandes' betweenness algorithm, at least a link to the one you are trying to understand? Also you can use LaTeX for symbols. $\endgroup$ – hengxin Jan 18 '16 at 12:31
  • $\begingroup$ 1. Your question is all one long sentence. Can you break it down into several shortest sentences? That would make it easier to understand what you are asking. 2. What are your thoughts? What have you tried? Have you tried working through some examples? Have you tried to find a proof of correctness for the algorithm? Often one or the other of those will help understand how to answer these kinds of questions. $\endgroup$ – D.W.♦ Jan 18 '16 at 17:23
1
$\begingroup$

Note: I assume that the OP is talking about Algorithm 1 in the paper "A Faster Algorithm for Betweenness Centrality" By Ulrik Brandes.

You probably have noticed that Algorithm 1 in the paper is for unweighted graphs. In this case, Dijkstra's algorithm@wiki amounts to BFS and a shortest path for a vertex $v$ is found immediately when $v$ is first encountered (in the pseudo-code, it is represented by if d[w] < 0 then). This property is due to the layer-by-layer search feature of BFS.

$Q_1:$ If a node is the first occurrence , then we have to check d[neighbor_node] < 0. However, if not, do we have to check d[neighbor_node] > d[current] + length(current,neighbor_node)?

For weighted graphs, the property mentioned above does not necessarily hold. So you need to replace (meaning the following is not needed any more) the if d[w] < 0 then predicate by a slightly involved one suitable for weighted graphs: 

          [foreach] neighbor w of v [do] [if] d[v] + length(w,v) < d[w] [then]

Note that for weighted graph, you should use a priority queue.

$Q_2:$ If greater, then do I have to delete previous updates like Queue, Pre[] and others?

No. You set d[], P[], sigma[] only when a shortest path is found. It is valid all the time once it is set. No need to update them later.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ thanks for ur advice, hengxin. U told exactly what i did. But i've done what u said. I just did the condition d[v]+c(v,w)<d[w], and it gives all betweenness centrality to 0. I think because i've initially assigned -1 to all d[] except d[s] , right? So, it means condition never checks for first encounter, then it never satisfies this condition. So, it turns out to be zero for all. Let me know ur advice, please. $\endgroup$ – Eint Sandi Aung Jan 19 '16 at 11:39
  • $\begingroup$ @carengonzerlax Have you used priority queue and extractMin() accordingly? Perhaps -1 should be $\infty$ (except d[s]). $\endgroup$ – hengxin Jan 19 '16 at 13:33
  • $\begingroup$ i just used priority queue and reversed it using PriorityQueue<Integer> que = new PriorityQueue<Integer>(size,Collections.reverseOrder()); .but the problem is while checking d[v]+c(v,w)<d[w]. since it is the first element and i only add one element which is "let s=1" to the queue. so, it popped "1" and "let neighbors of 1 are 2 and 3". so, when checking d[1]+c(1,2)<d[2], it doesn't enter condition because d[2] is already ∞(infinity) and d[1] is already set to 0. so do the same for all steps and nothing satisfy and doesn't do statements in condition. please understand me if i bother u. $\endgroup$ – Eint Sandi Aung Jan 19 '16 at 14:37
  • $\begingroup$ @carengonzerlax Are you using Java? Could you please upload your code into GitHub or somewhere available to me? If so, I will check it when I have time. $\endgroup$ – hengxin Jan 19 '16 at 14:40
  • $\begingroup$ i sent you my code to ur mail. $\endgroup$ – Eint Sandi Aung Jan 20 '16 at 1:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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