CODEWITHSUNDEEP
pythonnetworkxgraph-theory
dliv
dliv

Reputation: 685

calculate indegree centralization of graph with python networkx

I have a graph and want to calculate its indegree and outdegree centralization. I tried to do this by using python networkx, but there I can only find a method to calculate indegree and outdegree centrality for each node. Is there a way to calculate in- and outdegree centralization of a graph in networkx?

Upvotes: 4

Views: 3408

Answers (3)

Almas khan
Almas khan

Reputation: 1

You can use the following code for finding the network in degree centralization. The following is the function definition.

def in_degree_centralization(G):
    centralities=nx.in_degree_centrality(G)
    max_val=max(bcc.values())
    summ=0
    for i in bcc.values():
        cc= max_val-i
        summ=summ+cc
    normalization_factor=(len(G.nodes())-1)*(len(G.nodes())-2)
    return summ/normalization_factor

revoke the same function by passing the graph G as parameter i.e in_degree_centralization(graph)

Upvotes: 0

Aldorath
Aldorath

Reputation: 45

This answer has been taken from a Google Groups on the issue (in the context of using R) that helps clarify the maths taken along with the above answer:

Freeman's approach measures "the average difference in centrality between the most central actor and all others".

This 'centralization' is exactly captured in the mathematical formula

sum(max(x)-x)/(length(x)-1)

x refers to any centrality measure! That is, if you want to calculate the degree centralization of a network, x has simply to capture the vector of all degree values in the network. To compare various centralization measures, it is best to use standardized centrality measures, i.e. the centrality values should always be smaller than 1 (best position in any possible network) and greater than 0 (worst position)... if you do so, the centralization will also be in the range of [0,1].

For degree, e.g., the 'best position' is to have an edge to all other nodes (i.e. incident edges = number of nodes minus 1) and the 'worst position' is to have no incident edge at all.

Upvotes: 0

Joel
Joel

Reputation: 23827

Here's the code. I'm assuming that in-degree centralization is defined as I describe below...

N=G.order()
indegrees = G.in_degree().values()
max_in = max(indegrees)
centralization = float((N*max_in - sum(indegrees)))/(N-1)**2

Note I've written this with the assumption that it's python 2, not 3. So I've used float in the division. You can adapt as needed.

begin definition

Given a network G, define let y be the node with the largest in-degree, and use d_i(u) to denote the in-degree of a node u. Define H_G to be (I don't know a better way to write mathematical formulae on stackoverflow - would appreciate anyone who knows to either edit this or give a comment)

H_G = \sum_{u} d_i(y) - d_i(u)  
    =  N d_i(u) - \sum_u d_i(u)

where u iterates over all nodes in G and N is the number of nodes of G.

The maximum possible value for a graph on N nodes comes when there is a single node to which all other nodes point to and no other nodes have edges to them. Then this H_G is (N-1)^2.

So for a given network, we define the centralization to be it's value of H_G compared to the maximum. So C(G) = H_G/ (N-1)^2.

end definition

Upvotes: 3

Related Questions