maciejkos · January 31, 2020 22:16 · Apr 22, 2014
diff --git a/extract_backbone.py b/extract_backbone.py
@@ -0,0 +1,60 @@
+#!/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()
+
+
No results found