I am writing a piece of code which models the evolution of a social network. The idea is that each person is assigned to a node and relationships between people (edges on the network) are given a weight of +1 or -1 depending on whether the relationship is friendly or unfriendly.
Using this simple model you can say that a triad of three people is either "balanced" or "unbalanced" depending on whether the product of the edges of the triad is positive or negative.
Finally, what I am trying to do is implement an ising type model. In other words, random edges are flipped and the new relationship is kept if the new network has more balanced triangles (a lower energy) than the network before the flip, if that is not the case then the new relationship is only kept with a certain probability.
I have written the following code, however the dataset I have contains ~120k triads, and as a result it will take 4 days to run!
Could anyone offer any tips on how I might optimise the code?
#Importing required librarys try: import matplotlib.pyplot as plt except: raise import networkx as nx import csv import random import math def prod(iterable): p= 1 for n in iterable: p *= n return p def Sum(iterable): p= 0 for n in iterable: p += n return p def CalcTriads(n): firstgen=G.neighbors(n) Edges= Triads= for i in firstgen: Edges.append(G.edges(i)) for i in xrange(len(Edges)): for j in range(len(Edges[i])):# For node n go through the list of edges (j) for the neighboring nodes (i) if set([Edges[i][j]]).issubset(firstgen):# If the second node on the edge is also a neighbor of n (its in firstgen) then keep the edge. t=[n,Edges[i][j],Edges[i][j]] t.sort() Triads.append(t)# Add found nodes to Triads. new_Triads = # Delete duplicate triads. for elem in Triads: if elem not in new_Triads: new_Triads.append(elem) Triads = new_Triads for i in xrange(len(Triads)):# Go through list of all Triads finding the weights of their edges using G[node1][node2]. Multiply the three weights and append value to each triad. a=G[Triads[i]][Triads[i]].values() b=G[Triads[i]][Triads[i]].values() c=G[Triads[i]][Triads[i]].values() Q=prod(a+b+c) Triads[i].append(Q) return Triads ###### Import sorted edge data ###### li= with open('Sorted Data.csv', 'rU') as f: reader = csv.reader(f) for row in reader: li.append([float(row),float(row),float(row)]) G=nx.Graph() G.add_weighted_edges_from(li) for i in xrange(800000): e = random.choice(li) # Choose random edge TriNei= a=CalcTriads(e) # Find triads of first node in the chosen edge for i in xrange(0,len(a)): if set([e]).issubset(a[i]): # Keep triads which contain the whole edge (i.e. both nodes on the edge) TriNei.append(a[i]) preH=-Sum(TriNei) # Save the "energy" of all the triads of which the edge is a member e=-1*e# Flip the weight of the random edge and create a new graph with the flipped edge G.clear() G.add_weighted_edges_from(li) TriNei= a=CalcTriads(e) for i in xrange(0,len(a)): if set([e]).issubset(a[i]): TriNei.append(a[i]) postH=-Sum(TriNei)# Calculate the post flip "energy". if postH<preH:# If the post flip energy is lower then the pre flip energy keep the change continue elif random.random() < 0.92: # If the post flip energy is higher then only keep the change with some small probability. (0.92 is an approximate placeholder for exp(-DeltaH)/exp(1) at the moment) e=-1*e