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.pdfFor 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.
Betweenness Centrality measurement in Undirected Graphs
graph theory;graphs
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.