@abrusan The original issue you reported will be fixed Very Soon ™. Hopefully 
We’re working on it, and it will be in the next release, due out this month.
About decomposing into connected components and computing the eigenvector centrality for each, it turns out that Mathematica does exactly that. I originally misunderstood what it does as the documentation was not as clear on this point as would be preferable.
There is still the issue of how to scale centralities in each component relative to each other.
A crude version that sort-of-makes sense would be to scale the centralities according to the number of edges (or the total weight of edges) in each of the connected components.
Why not scale with the eigenvalue instead? That would be consistent with the definition of the eigenvectors of the separate components in a sense.
That is probably even better; one example I could think of is a graph consisting of an in-star component of n vertices (one at the center, n-1 pointing at it) and another component that is a path of length n. (Plus one loop edge at the center of the star and at the end of the path to ensure that the graph is not a DAG). The centrality of the vertex at the center of the in-star should be larger (intuitively) than the centrality of the vertex at the end of the path. The eigenvalues satisfy this as the leading eigenvalue of the star component is n and the leading eigenvalue of the path component is only 2.
The eigenvector centrality of a vertex of proportional to the sum of the centralities of its neighbours (by definition). The constant of proportionality is the eigenvalue.
If we scale the centralities in one component, that will still not change the proportionality constant within that component. It will still be its specific eigenvalue.
Is this what you meant? It is possible I misunderstood.
While I do like the idea of auto-decomposing the graph, my concern is that “the right way” to scale centralities between components is really a research level question (albeit not a very interesting one). We should not mislead inexperienced users into thinking that “this is the right way” and that “this nodes in component A is twice as central as that one in component B” when the scaling is something that we came up with without a solid theoretical justification.
In the end, whatever scaling we were to choose, it will be independent of the concept of eigenvector centrality, as eigenvector centrality is defined in terms of a relationship with neighbours, but there are no connections (no neighbours) between components. It may be a good scaling in some sense, but it will still be independent of the original definition of eigenvector centrality. That definition gives no guidance on what to choose. Thus, there are multiple reasonable choices.
It would be nice to do a survey about what others do before settling on a solution.
Survey of what other software does (I’ll keep updating this list). Note that there are two issues: How scores are normalized (e.g. by the vector’s 2-norm, by its maximum, or something else), and how scores are scaled across components. The final result is affected by both.
Software that decomposes the graph:
- Mathematica: http://reference.wolfram.com/language/ref/EigenvectorCentrality.html See under “Properties and Relations”, 4th section. Normalization is done by the total (i.e. scores add up to 1). Scaling is done by component size minus one. No justification is given.
- Visione: https://groups.google.com/g/visone-users/c/XdZIX5s93ZI/m/zO10z7X9BjAJ Normalization is done by the 2-norm. Scaling is done by component size minus one. No justification is given.
- ORA/UCINET: http://www.casos.cs.cmu.edu/publications/papers/CMU-ISR-11-113.pdf Unclear how normalization is done. Scaling is by component size. No justification is given, but they point out that “The case of unconnected networks is very tricky”.
Software that does not decomponse (and therefore returns zeros for all but one component):
- networkx, Maple, SNAP (only checked the docs!)
More discussions on the topic from other software packages:
- NetLogo: https://github.com/NetLogo/NW-Extension/issues/168 https://github.com/NetLogo/NW-Extension/issues/44
The fact that most discussion I find is about “how to implement it correctly” confirms my belief that this not really a practical issue. Eigenvector centrality just shouldn’t be used in disconnected cases, fullstop. It comes up as an issue only when a software package wants to have a complete and correct implementation, and they discuss it (as we do here), but there is no valid use case for it.
I would be comfortable simply refusing to return eigenvector centralities for disconnected components (or only return it for the largest component). It should be a use case that is rare, exactly because of the difficulties of comparing centralities. If some user would still insist on doing so, (s)he should go through more trouble to get those centrality scores, forcing the user to also think about how to interpret such scores.
1 Like