Extract the multiscale backbone of a weighted complex network

extract_backbone.py

#!/usr/bin/env python

# extract_backbone.py
# Jim Bagrow
# Last Modified: 2010-11-18

import sys, os
import networkx as nx


def extract_backbone(G, weights, alpha):
    keep_graph = nx.Graph()
    for n in G:
        k_n = len( G[n] )
        if k_n > 1:
            sum_w = sum( weights[n,nj] for nj in G[n] )
            for nj in G[n]:
                pij = 1.0*weights[n,nj]/sum_w
                if (1-pij)**(k_n-1) < alpha: # edge is significant
                    keep_graph.add_edge( n,nj )
    return keep_graph


if __name__ == '__main__':
    
    if "-h" in sys.argv[1:] or "--help" in sys.argv[1:] or len(sys.argv) < 2:
        usage = """python %s input_file output_file backbone_alpha [file delimiter]""" % sys.argv[0]
        sys.exit(usage)
    
    # command line args:
    in_file = sys.argv[1]
    ot_file = sys.argv[2]
    alpha   = float(sys.argv[3])
    try:
        delimiter = sys.argv[4]
    except:
        delimiter = None # split on whitespace
    
    # load the network and edge weight dict:
    G = nx.Graph()
    weights = {}
    for line in open(in_file):
        if line[0] == "#":
            continue
        ni,nj,wij = line.strip().split(delimiter)
        
        G.add_edge(ni,nj)
        weights[ni,nj] = float(wij)
        
    # extract the backbone:
    G_backbone = extract_backbone(G, weights, alpha)
    
    # save the new edgelist:
    delimiter = " " if delimiter is None else delimiter
    f = open(ot_file, 'w')
    for ni,nj in G_backbone.edges():
        f.write("%s%s%s\n" % (ni,delimiter,nj) )
    f.close()