# Help with optimising my model of social network evolution.

EDIT: I first asked this on the main stackoverflow page and someone suggested my question should be here.

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.

So finally what I am trying to do is implement an ising type model. I.e. Random edges are flipped and the new relationship is kept if the new network has more balanced triangels (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.

Ok so finally onto my question: I have written the following code, however the dataset I have contains ~120k triads, as a result it will take 4 days to run!

Could anyone offer any tips on how I might optimise the code?

Thanks, Richard.

``````#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[3]
return p

firstgen=G.neighbors(n)
Edges=[]

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][1]]).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][0],Edges[i][j][1]]
t.sort()

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.
Q=prod(a+b+c)

###### Import sorted edge data ######
li=[]
with open('Sorted Data.csv', 'rU') as f:
li.append([float(row[0]),float(row[1]),float(row[2])])
G=nx.Graph()

for i in xrange(800000):
e = random.choice(li)   # Choose random edge

TriNei=[]
for i in xrange(0,len(a)):
if set([e[1]]).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[2]=-1*e[2]# Flip the weight of the random edge and create a new graph with the flipped edge
G.clear()

TriNei=[]
for i in xrange(0,len(a)):
if set([e[1]]).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[2]=-1*e[2]
``````
-

``````#Importing required librarys
``````

I can see that. Don't comment on what's obvious from the syntax

``````try:
import matplotlib.pyplot as plt
except:
raise
``````

Catching an exception only to rethrow it? That's a waste

``````import networkx as nx
import csv
import random
import math

def prod(iterable):
p= 1
for n in iterable:
p *= n
return p
``````

You may want to look at numpy, it has function like this written in efficient C.

``````def Sum(iterable):
p= 0
``````

p? why p?

``````    for n in iterable:
p += n[3]
return p
``````

The python style guide recommends lowercase_with_underscores for global function names. The name also suggests its a generic summing function which its not. No indication is given for what kind of data it expects. A docstring should at least explain that.

``````def CalcTriads(n):
firstgen=G.neighbors(n)
``````

Don't use global variables. Instead pass G in as a parameter. Also, I recommend against calling it G.

``````    Edges=[]
``````

Python style guide recommemnds lowercase_with_underscores for local variables names

``````    for i in firstgen:
Edges.append(G.edges(i))
``````

I recommend a list comprehnsion

``````Edges = [G.edges(i) for i in firstgen]

for i in xrange(len(Edges)):
``````

Don't iterate over the integers, iterate over the edges. Use for edge in Edges:

``````        for j in range(len(Edges[i])):# For node n go through the list of edges (j) for the neighboring nodes (i)
``````

I recommend putting the comment on a seperate line from the if. Otherwise it tends to wrap off the side of the screen and that's annoying. Also, iterate over the container, not the indexes. Use something like for source, dest in edges:

``````            if set([Edges[i][j][1]]).issubset(firstgen):# If the second node on the edge is also a neighbor of n (its in firstgen) then keep the edge.
``````

Create a list with a single element, putting that in a set, simply to call issubet is silly. Use Edges[i][j][1] in firstgen.

``````                t=[n,Edges[i][j][0],Edges[i][j][1]]
t.sort()

``````

That is an inefficient way of doing that. Instead, make Triads a set and put tuples rather then lists in it. That'll be faster and easier to read.

``````    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.
``````

This code would be way cleaner if you used for triad in Triads:

``````            a=G[Triads[i][0]][Triads[i][1]].values()
Q=prod(a+b+c)

###### Import sorted edge data ######
li=[]
``````

Bad name, gives no idea what it intends

``````with open('Sorted Data.csv', 'rU') as f:
``````

I think you are supposed to read csv files in a binary mode.

``````    reader = csv.reader(f)
li.append([float(row[0]),float(row[1]),float(row[2])])
``````

Use for source, dest, value in row: li.append(float(source), float(dest), float(value))

Do you really want floats? Are the source and destination really floats or are they ints?

``````G=nx.Graph()

for i in xrange(800000):
``````

Don't execute loop at the module level. Code written inside a function will run faster. e = random.choice(li) # Choose random edge

``````    TriNei=[]
``````

Don't use variable names like a, a one letter variable name is terrible waste of information capacity.

``````    for i in xrange(0,len(a)):
``````

Don't use xrange to iterate over containers.

``````        if set([e[1]]).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[2]=-1*e[2]# Flip the weight of the random edge and create a new graph with the flipped edge
G.clear()
``````

You should be able to find and change the edge weight directly. Reconstructing the whole graph is going to be kinda slow.

``````    TriNei=[]
for i in xrange(0,len(a)):
if set([e[1]]).issubset(a[i]):
TriNei.append(a[i])
postH=-Sum(TriNei)# Calculate the post flip "energy".
``````

Seeing the same piece of code in two place is a big hint. Write a function!

``````    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[2]=-1*e[2]
``````

What you should consider doing is writing a function which given a node calculates the change in "energy" that would occour if it was flipped. Right now you calculate before and after, but you should be able to simply calculate the delta without changing it. If you can effeciently calculate the delta, that's all you need.

-
Wow. Thanks. Yeah this is the first thing I've ever attempted in python, and the second time I have tried to write a program. I'm a physicist! –  user671629 Jul 18 '11 at 11:26

The following lines seem particularly costly:

``````G.clear()
Why are you clearing the entire graph and recreating it? Isn't there a more direct way to modify the graph without recreating it from scratch? When I looked at the reference I found methods like `Graph.remove_edge(u,v)` and `Graph.add_weighted_edges_from(ebunch,**attr[,attr_dict])` that seem like better ways of adding and removing edges without recreating the entire graph from scratch.
You should also look into adding some kind of caching to `CalcTriads(n)` because the neighbors of `n` don't change and for a fixed `n` you are constantly recalculating the neighbors from scratch which is unnecessary because only the weights of the edges changes not the actual nodes connected to `n`.