igraph

Bug #404256
Comment #11

Comment 11 for bug 404256

Revision history for this message

Tamás Nepusz (ntamas) wrote on 2009-07-27:

#11

igraph_arpack_patch_01.patch Edit (3.0 KiB, text/plain)

Okay, so here's what I figured out so far:

1. The original bug report (unknown ARPACK error) is caused by incorrect error handling in igraph_i_arpack_err_dsaupd. Practically, error codes 1 and 3 were not handled properly. The second call to Graph.leading_eigenvector_community() resulted in a "maximum number of iterations reached" error message which was then turned to an unknown ARPACK error.

2. Having fixed the error handler, I tried the test case in #7 with the 4-star graph. With the fixed error handler, I got an error message complaining about NCV (the number of Lanczos vectors to be generated) is too small. The ARPACK documentation says the following: "At present there is no a-priori analysis to guide the selection of NCV relative to NEV. The only formal requirement is that NCV > NEV. However, it is recommended that NCV .ge. 2*NEV.". Since NEV is 1 (we need the leading eigenvector only), NCV was set to 3 per default. I increased NCV to 4 and it seems to have fixed the problem. I also checked other C code snippets that use ARPACK in other projects, and the general rule of thumb seems to set NCV to 4 * NEV and threshold it with the number of rows in the input matrix from above.

3. The inconsistency wrt the obtained results in repeated calls of community_leading_eigenvector() stems from the fact that the top eigenvalue of the modularity matrix is zero for these graphs if I calculated it right. Due to rounding errors and such, the actual eigenvalue calculated by ARPACK can be slightly larger than zero depending on the random initial starting vector used. igraph uses a hard threshold at zero, i.e. if the largest eigenvalue is less than or equal to zero, the community splitting process is stopped. If it is slightly larger than zero, the process will continue. If I increase the threshold to 1e-5 in the code, I always get the same results for star graphs, but I'm not sure that there isn't a better solution.

I'm attaching a patch that should fix the above mentioned issues. Can you please check it on your platform(s)? The patch is against the head revision of the igraph trunk, but it should work against the 0.5 branch as well.

Okay, so here's what I figured out so far:

2. Having fixed the error handler, I tried the test case in #7 with the 4-star graph. With the fixed error handler, I got an error message complaining about NCV (the number of Lanczos vectors to be generated) is too small. The ARPACK documentation says the following: "At present there is no a-priori analysis to guide the selection of NCV relative to NEV.  The only formal requirement is that NCV > NEV. However, it is recommended that NCV .ge. 2*NEV.". Since NEV is 1 (we need the leading eigenvector only), NCV was set to 3 per default. I increased NCV to 4 and it seems to have fixed the problem. I also checked other C code snippets that use ARPACK in other projects, and the general rule of thumb seems to set NCV to 4 * NEV and threshold it with the number of rows in the input matrix from above.