[Solved]: Betweenness Centrality measurement in Undirected Graphs

Problem Detail: 

I'm working with graphs of a very large size (> 60k vertices), and want to speed up B.C. measurements. It is defined here: http://en.wikipedia.org/wiki/Betweenness_centrality The algorithm that I am using to compute B.C. is Brandes' algorithm: http://www.inf.uni-konstanz.de/algo/publications/b-fabc-01.pdf

For undirected graphs, would running the Betweenness centrality algorithm on each of its connected components (and then combine the results) give the exact same answer as computing on the whole graph at once? I would think so (but don't have a proof) because different connected components are not related.

Asked By : Ryan

Answered By : emab

Betweenness centrality is defined on connected graphs. Suppose a graph $G$ with two connected components, $G_1$ and $G_2$, and consider a node $v \in G_1$, then the betweenness centrality for $v$ is

$$C_B(u)=\sum_{s,t \in G}{\frac{\sigma_{st}(v)}{\sigma_{st}}}=\sum_{s,t \in G_1}{\frac{\sigma_{st}(v)}{\sigma_{st}}}+\sum_{s,t \in G_2}{\frac{\sigma_{st}(v)}{\sigma_{st}}}+2\sum_{s \in G_1,t \in G_2}{\frac{\sigma_{st}(v)}{\sigma_{st}}}=$$

$$\sum_{s,t \in G_1}{\frac{\sigma_{st}(v)}{\sigma_{st}}}+\sum_{s,t \in G_2}{\frac{\sigma_{st}(v)}{\sigma_{st}}}+2\sum_{s \in G_1,t \in G_2}{\frac{0}{0}}$$

But if you want to treat each connected component as a single graph, you can also calculate the betweenness centrality independently for each component.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/30088

3.2K people like this

 Download Related Notes/Documents