search

dracor-org / dracor-api

eXistdb application for dracor.org
MIT License
10 stars 2 forks source link

Eigenvector Centrality in cast list differs from values calculated by Gephi and igraph #58

Open cmil opened 5 years ago

cmil commented 5 years ago

We're not the first to notice this mismatch (cf. "Eigenvector Centrality Oddity with iGraph, Gephi, and NetworkX"). While that article finds diverging values for all three, igraph, Gephi and NetworkX, we find that igraph and Gephi throw the same results, while NetworkX begs to differ.

To add another example, here's what our R script throws (using igraph) for "Emilia Galotti":

r_screenshot

The documentation for igraph and NetworkX both insinuate that they're relying on the same algorithm. Could you maybe check if you throw the 'edge weights' into the formula (which we don't do)? This could explain the different values…

Originally posted by @lehkost in https://github.com/dracor-org/dracor-api/issues/31#issuecomment-462030597

cmil commented 5 years ago

The current calculation in dracor-metrics does not consider edge weights (see https://github.com/dracor-org/dracor-metrics/blob/master/routes/metrics.js#L98). When I added the edge weights the values were still off from those calculated by gephi or igraph.

I noticed that the gephi values listed above are about 2.22724 times higher than what we calculate with JSNetworkX (not considering weights).

lehkost commented 5 years ago

Oh, so they all differ by this factor? That could be a hint.

Also, did some further research… Since we're relying on eigenvectorCentrality (as eigenvectorCentralityNumpy as alternative is not implemented yet in JSNetworkX), we can't try if that would solve the problem.

In addition, in this thread it sounds like there are certain node constellations in graphs that make throw eigenvectorCentrality an error (just like you described here); actually, at least two of the four exception-throwing graphs are star graphs (the other two might have the same properties, but that's less visible at first sight due to their being too big).

pixelmagenta commented 5 years ago

The function eigenvector_centrality in NetworkX returns normalized vector. I found it in the source code (see https://github.com/networkx/networkx/blob/a299546d0c70016c2d2154654864e9aaa8969233/networkx/algorithms/centrality/eigenvector.py#L25) and I also checked manually the norm of the eigenvector centrality vector from the API results for Emilia Galotti and it is 1.

In igraph eigenvector centrality vector isn't normalized. I checked it manually too and in the code (see https://github.com/igraph/igraph/blob/c517ad26e537bbdf363a1f6f9cabd66040664fdd/src/centrality.c#L157) there is no normalization.

lehkost commented 5 years ago

Thanks for digging this up! So the question probably is, how do we want our eigenvector centrality? Given that the NetworkX way has trouble to calculate eigenvector centrality for star-like graphs (or so it seems), we should maybe do it the igraph way, i.e., non-normalised?