Re: [igraph] time complexity of centrality calculation

[Tamás Nepusz]

> I need to compare time complexity of computing different centrality measures 
> in igraph but I could not find how they are implemented exactly. 
The documentation of the C core of igraph lists the time complexity of most of 
the functions:

- Degree: http://igraph.sourceforge.net/doc/html/ch04s02.html#igraph_degree
- Closeness: 
http://igraph.sourceforge.net/doc/html/ch13s05.html#igraph_closeness
- Betweenness: 
http://igraph.sourceforge.net/doc/html/ch13s05.html#igraph_betweenness
- PageRank: http://igraph.sourceforge.net/doc/html/ch13s05.html#igraph_pagerank
- Eigenvector centrality: 
http://igraph.sourceforge.net/doc/html/ch13s05.html#igraph_eigenvector_centrality

Closeness centrality basically falls down to a breadth first search in order to 
find the shortest paths. Betweenness centrality calculation uses the algorithm 
of Brandes (http://www.inf.uni-konstanz.de/algo/publications/b-fabc-01.pdf). 
PageRank and eigenvector centrality do not really have a "proven" time 
complexity because they use the ARPACK eigenvector solver on sparse matrices 
and the exact time complexity depends on a lot of factors. Academic papers 
usually claim that they are O(|V| + |E|) where |V| is the number of vertices 
and |E| is the number of edges, but the actual time complexity depends also on 
the speed of convergence, which in turn depends on the "spectral gap" of the 
associated adjacency matrix if I remember correctly. (Not sure about this last 
part, though, and I'm too tired to check it now).

> I also need to know how degree() is implemented. does it use network 
> adjacency matrix, it is precomputed  or any others?  
It is not precomputed but the data structure that igraph uses makes it easy to 
calculate the degree. (It boils down to a few constant-time lookups and a 
subtraction). FWIW, igraph does not use adjacency matrice; the internal 
representation is currently an indexed edge list, but this is an implementation 
detail and might change in the future without notice.

Best,
T.