CODEWITHSUNDEEP
pythonrnetwork-programmingnetworkxsna
Aldorath
Aldorath

Reputation: 45

How do you create a networkx function for eigenvector centralization for a whole network? (Freeman)

The question is: How do you compute eigenvector centralization for a graph using networkx?

(As in, not for individual nodes, but for the whole graph for comparing nodes, using Freeman's method for doing this).

I need to compare a number of different graphs and I wish to use four different centrality measures for comparing them:

Currently networkx doesn't have any functions that compute the centralization for a whole network - all of the functions return a dictionary of the centrality for each node.

Note that centralization is about the distribution of the centrality within a network.

I've written a function that can compute the centrality for the whole network for the first three of these, but I can't figure out how to compute this for Eigenvector centrality.

The theory is that it ought to be the sum(max centrality - centrality for each node) divided by the theoretical maximum for a network of size n.

The closest I can get to figuring out how to do this for eigenvector centrality is seeing the theory for this on slide 32 of this set of lecture notes which looks like this:

Ce<-function(Y)
{
    n<-nrow(Y)
    e<-evecc(Y)
    Y.sgn<-matrix(0,n,n) ; Y.sgn[1,-1]<-1 ; Y.sgn<-Y.sgn+t(Y.sgn)
    e.sgn<-evecc(Y.sgn)
    sum(max(e)-e)/ sum(max(e.sgn)-e.sgn)
}

This seems to be the sum of (max eigen centrality minus each node eign centrality) divided by something that makes no sense - it's the denominator that I can't figure out.

My code in python so far accounts for the other three types, but I have no idea what this code is doing (the above). The part of the code that I can't figure out is indicated. All help much appreciated.

def getCentrality(centrality, c_type):

    c_denominator = float(1)

    n_val = float(len(centrality))

    print (str(len(centrality)) + "," +  c_type + "\n")

    if (c_type=="degree"):
        c_denominator = (n_val-1)*(n_val-2)

    if (c_type=="close"):
        c_top = (n_val-1)*(n_val-2)
        c_bottom = (2*n_val)-3  
        c_denominator = float(c_top/c_bottom)

    if (c_type=="between"):
        c_denominator = (n_val*n_val*(n_val-2))
    if (c_type=="eigen"):
        c_denominator = [THIS PART I CAN'T FIGURE OUT]




    c_node_max = max(centrality.values())


    c_sorted = sorted(centrality.values(),reverse=True)

    print "max node" + str(c_node_max) + "\n"

    c_numerator = 0

    for value in c_sorted:

        if c_type == "degree":
            #remove normalisation for each value
            c_numerator += (c_node_max*(n_val-1) - value*(n_val-1))
        else:
            c_numerator += (c_node_max - value)

    print ('numerator:' + str(c_numerator)  + "\n") 
    print ('denominator:' + str(c_denominator)  + "\n") 

    network_centrality = float(c_numerator/c_denominator)

    if c_type == "between":
        network_centrality = network_centrality * 2

    return network_centrality

(note that closeness and betweenness should not be normalized when inputting those into this function)

Update: Following the answer the code has been completed and posted as a gist function for others to use

Upvotes: 2

Views: 1333

Answers (1)

paqmo
paqmo

Reputation: 3729

Just to be clear, you are looking for (I think) the eigenvector centralization for a network. Centrality is a node-level index and is defined only for the nodes of a network (as makes sense, given what they measure). (As I recall, Freeman calls centralization "graph centrality", but the term "centralization" has replaced, hence the possible confusion in the comments.)

The theoretical maximum for eigenvector centralization is the network of the same size with only one edge between two nodes. In the case of a directed network, this is n - 1. In the case of an undirected network, it is sqrt(2)/2 * (n - 2). (See Butts, 2016, pg. 56)

So with that in mind:

from math import sqrt
if (c_type=="eigen"):
    c_denominator = sqrt(2)/2 * (n_val - 2)

Or:

if (c_type=="eigen"):
    c_denominator = n_val - 1

Upvotes: 4

Related Questions