Re: [igraph] Performance issue regarding when calculating induced_subgra

[Tamas Nepusz]

Hi,

> However, when we run the exact codes of yours we got quite different results:
Ah, yes, sorry, I have probably done a copy-paste error in my last
email; I just re-tested things and indeed the slowest case is when you
have numeric vertex names only.

> Everything is working fine except the „lapply(g_sub,
> function(x){authority_score(x)$vector})” statement, because there is one
> group where the authority_score function fails. [...]
> At arpack.c:944 : ARPACK error, No shifts could be applied during a cycle
> of the Implicitly restarted Arnoldi iteration. One possibility is to
> increase the size of NCV relative to NEV”
This error message usually indicates that ARPACK fails to converge to
the eigenvector being searched for some reason, or converges very
slowly. Sometimes this happens with bipartite graphs (and note that
all star graphs are bipartite), and we have usually seen it with small
graphs only as larger graphs are unlikely to have a structure that
causes slow convergence in ARPACK. In such cases, you can fall back to
the eigen() function in plain R to calculate all the eigenvalues from
A^T * A (or A * A^T, I can't really remember) in order to get the
authority scores.

However, there is one thing that I have noticed in your code.
Originally, your graph is directed, but you remove the directionality
of the edges so you could run the label propagation algorithm on it.
This is fine, but note that the hub and authority scores are equal to
each other _and_ to the eigenvector centrality in undirected graphs,
so there's no point in calculating both the eigenvector centrality and
the authority score at all if you intend to do the full analysis on an
undirected graph. Running the community detection on the undirected
copy and then performing the analysis on the original, directed graph
could be an option, and it might even get rid of the problem with the
authority score for star graphs.

T.