
Hello!
This one is a more theoritical question but since ''indegree centrality'' and ''betweenness centrality'' are two of the most important graph metrics that are computed by NodeXl, I feel it would be quite interesting for all the community.
Does anyone know the complexity of the ''betweenness centrality'' algorithm or the ''indegree centrality'' algorithm?Is there any source where i can find it ?


Jun 13, 2012 at 3:52 AM
Edited Jun 13, 2012 at 4:39 PM

The complexity for the degree metrics is O(n*m), where n is the number of vertices and m is the number of edges in the graph.
The complexity for the betweenness centrality metrics is described in "A Faster Algorithm for Betweenness Centrality," by Ulrik Brandes, which you can find at
http://www.inf.unikonstanz.de/algo/publications/bfabc01.pdf.
 Tony

