Skip to content

Instantly share code, notes, and snippets.

Created April 22, 2014 14:33
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
  • Save bagrow/11181518 to your computer and use it in GitHub Desktop.
Save bagrow/11181518 to your computer and use it in GitHub Desktop.
Extract the multiscale backbone of a weighted complex network
#!/usr/bin/env python
# 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]
# command line args:
in_file = sys.argv[1]
ot_file = sys.argv[2]
alpha = float(sys.argv[3])
delimiter = sys.argv[4]
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] == "#":
ni,nj,wij = line.strip().split(delimiter)
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) )
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment