Eigenvector Centrality issues

[Alex Garnett]

Hey guys,

I'm having seemingly no end of trouble trying to get an eigenvector centrality algorithm to work on my graph. The regular nX implementation gives me an error about failing to converge, and the numpy implementation, when called from nX, runs its 100 iterations outputting 0.0 values for every node except for one node which is assigned a 1.0 value.

Something is obviously screwed up in my graph, but I've been able to export to gexf and open it in Gephi to calculate eigenvector centrality without any issues. This, however, is starting to take too long, so I'd really like to be able to get this and other metrics out of nX.

My nodes each have 5 properties, one of which is called weight (and is effectively degree); my edges each also have a property called weight. I'm trying to calculate eigenvector centrality after pruning the graph by removing all but the 3000 nodes with the highest degree (using Twitter data), as follows:

eigenvector = nx.eigenvector_centrality(g_reduced)

for n in eigenvector:

g_reduced.node[n]['eigenvector centrality'] = eigenvector[n]

Any help? Appreciate it!

-alex

Alex Garnett, MLIS, Ph.D. Student
Data Science Asst., Arts ISIT
University of British Columbia

(778) 228-5110; USA (860) 245-1638

[Aric Hagberg]

On Mon, Jun 11, 2012 at 11:53 AM, Alex Garnett <axf...@gmail.com> wrote:
> Hey guys,
>
> I'm having seemingly no end of trouble trying to get an eigenvector
> centrality algorithm to work on my graph. The regular nX implementation
> gives me an error about failing to converge, and the numpy implementation,
> when called from nX, runs its 100 iterations outputting 0.0 values for every
> node except for one node which is assigned a 1.0 value.
>
> Something is obviously screwed up in my graph, but I've been able to export
> to gexf and open it in Gephi to calculate eigenvector centrality without any
> issues. This, however, is starting to take too long, so I'd really like to
> be able to get this and other metrics out of nX.
>
> My nodes each have 5 properties, one of which is called weight (and is
> effectively degree); my edges each also have a property called weight. I'm
> trying to calculate eigenvector centrality after pruning the graph by
> removing all but the 3000 nodes with the highest degree (using Twitter
> data), as follows:
>
> eigenvector = nx.eigenvector_centrality(g_reduced)
> for n in eigenvector:
> g_reduced.node[n]['eigenvector centrality'] = eigenvector[n]
>

The power method might not be converging very fast (or at all?).

so what happens when you try
eigenvector = nx.eigenvector_centrality_numpy(g_reduced) ?

That uses the numpy/LAPACK eigenvalue solver instead of the power
method and should work if your graph/matrix is OK.

If that breaks you might have to look carefully at your graph to find
out why it is special.

Aric

[Alex Garnett]

Hi Aric,

Like I said, when I try the numpy method, it

> runs its 100 iterations outputting 0.0 values for every 

> node except for one node which is assigned a 1.0 value.

Obviously, this isn't quite correct... though I can't tell what in the world is special about my graph for it not to work.

[Daniel Schult]

There's not much to go on in your description.  It would be best to have a self contained example that shows the issue.  It seems likely that you are using slightly different functions in the Gephi and NX....  

Perhaps Gephi uses weights by default and NX doesn't?

Looking at the node whose value is assigned 1.0, how many neighbors?

The next step might be to carefully go through the docs for the nx and gephi functions and make sure they are doing the same thing.  There is almost certainly a way to get the NX version to match (within roundoff) the results from gephi.

Dan

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To view this discussion on the web visit https://groups.google.com/d/msg/networkx-discuss/-/neprfNCtCNQJ.
To post to this group, send email to networkx...@googlegroups.com.
To unsubscribe from this group, send email to networkx-discu...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/networkx-discuss?hl=en.

[JZM]

Hello, I do not know how I really got this chat up

I have a similar problem and can't get how gephi calculates the eigenvector centrality anywhere, Do you know where can I find the formulas they used?

Sorry for the message if I am not supposed to be here

Best regards

JZM