Friday, January 16, 2015

Finding k-cores and Clustering Coefficient Computation with NetworkX

Assume you have a large network and you want to find k-cores of each node and also you want to compute clustering coefficient for each one. Python package NetworkX comes with very nice methods for you to easily do these.

k-core is a maximal subgraph whose nodes are at least k degree[1]. To find k-cores:

Add all edges you have in your network in a NetworkX graph, and use core_number method that gets graph as the single input and returns node – k-core pairs.

cores = networkx.core_number(G)

If you also need to compute clustering coefficient each node, use clustering method which gets graph and node as inputs for unweighted and returns a floating number as the clustering coefficient of the node.

cc = networkx.clustering(G, node)

1. Preventing Unraveling in Social Networks: The Anchored k-Core Problem, http://www.cs.cornell.edu/home/kleinber/icalp12-kcore.pdf

Below there is an example script that does these operations. Read the code and prepare your input accordingly.

No comments: