<p>What is the time complexity of computing betweenness centrality if we are given the shortest path predecessor matrix of a graph?</p>

<p>Predecessor matrix cells look like this:</p>

<p>If node $i$ and node $j$ are directly connected then the value in the cell is $0$;
if node $i$ and node $j$ are not connected then value in the cell is $-1$;
else the cell contains $\operatorname{predecessor}(j)$ (this can be only one predecessor if there is a single shortest path or an array of predecessors if there are more than one shortest paths between $i$ and $j$).</p>

CC BY-SA 3.0
2011-07-08T13:07:24.800Z
The following changes should improve your question: providing more information about betweenness centrality (I'm not sure how many people are familiar with it); changing the title as it is misleading; the question is about betweenness centrality; and using latex to write the mathematics.
Dave Clarke
CC BY-SA 3.0
2011-07-08T13:11:00.083Z
@Dave Clarke I just LaTeXed the question, which can be seen after someone approves that changes. (Wow! That was fast :) )
Tyson Williams
<ds.algorithms><graph-algorithms>
Predecessor matrix storing
ilija
# Predecessor matrix storing

(Asked by: username_0 on 2011-07-08)

What is the time complexity of computing betweenness centrality if we are given the shortest path predecessor matrix of a graph?

Predecessor matrix cells look like this:

If node $i$ and node $j$ are directly connected then the value in the cell is $0$;
if node $i$ and node $j$ are not connected then value in the cell is $-1$;
else the cell contains $\operatorname{predecessor}(j)$ (this can be only one predecessor if there is a single shortest path or an array of predecessors if there are more than one shortest paths between $i$ and $j$).

**Tags:** ds.algorithms, graph-algorithms
> **Comments:**
> **username_1**: The following changes should improve your question: providing more information about betweenness centrality (I'm not sure how many people are familiar with it); changing the title as it is misleading; the question is about betweenness centrality; and using latex to write the mathematics.  
> **username_2**: @Dave Clarke I just LaTeXed the question, which can be seen after someone approves that changes. (Wow! That was fast :) )  

---

## 0 answers

