> 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. _______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
