Оптимизационная модель эволюции социальной сети

Question

Я пишу кусок кода, который моделирует эволюцию социальной сети.Идея состоит в том, что каждый человек назначается узлу, а отношения между людьми (ребра в сети) имеют вес +1 или -1 в зависимости от того, дружеские отношения или недружественные.

Используя эту простую модель, вы можете сказать, что триада из трех человек является «сбалансированной» или «несбалансированной» в зависимости от того, является ли произведение краев триады положительным или отрицательным.

Итак, наконец, я пытаюсь реализовать модель изингового типа.Т.е. случайные ребра переворачиваются, и новые отношения сохраняются, если в новой сети более сбалансированные треугольники (более низкая энергия), чем сеть до переворота, если это не так, то новые отношения сохраняются только с определенной вероятностью.

Хорошо, наконец, на мой вопрос: я написал следующий код, однако набор данных, который у меня есть, содержит ~ 120k триад, в результате на выполнение которого уйдет 4 дня!

Может ли кто-нибудь предложить какие-либо советы по оптимизации кода?

Спасибо.

#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


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][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()
                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][0]][Triads[i][1]].values()
            b=G[Triads[i][1]][Triads[i][2]].values()
            c=G[Triads[i][2]][Triads[i][0]].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[0]),float(row[1]),float(row[2])])
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[0]) # Find triads of first node in the chosen edge 
    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()
    G.add_weighted_edges_from(li)


    TriNei=[]
    a=CalcTriads(e[0])  
    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]

Answer 1

Следующие предложения не сильно повысят вашу производительность, потому что они не на алгоритмическом уровне, то есть не очень специфичны для вашей проблемы. Тем не менее, это общие предложения для небольших улучшений производительности:

Если вы не используете Python 3, измените

for i in range(800000):

до

for i in xrange(800000):

Последний просто повторяет числа от 0 до 800000, первый создает огромный список чисел, а затем повторяет этот список. Сделайте что-то подобное для других циклов, используя range.

Кроме того, измените

j=random.choice(range(len(li))) 
e=li[j] # Choose random edge

до

e = random.choice(li)

и используйте e вместо li[j] впоследствии. Если вам действительно нужен индексный номер, используйте random.randint(0, len(li)-1).

Answer 2

Существуют синтаксические изменения, которые вы можете внести, чтобы ускорить процесс, например, замена функций Sum и Prod встроенными эквивалентами sum(x[3] for x in iterable) и reduce(operator.mul, iterable) - обычно быстрее использовать встроенные функции или выражения генератора, чем явные петли.

Насколько я могу сказать строку:

    if set([e[1]]).issubset(a[i]): # Keep triads which contain the whole edge (i.e. both nodes on the edge)

проверяет, есть ли число в списке. Замена его на if e[1] in a[i]: устранит накладные расходы на создание двух set объектов для каждого сравнения.

Кстати, вам не нужно перебирать значения индекса массива, если вы собираетесь использовать этот индекс только для доступа к элементам. например замена

for i in range(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])    

с

for x in a:
    if set([e[1]]).issubset(x): # Keep triads which contain the whole edge (i.e. both nodes on the edge)
    TriNei.append(x)    

Однако я подозреваю, что подобные изменения не будут иметь большого значения для общего времени выполнения. Для этого вам нужно либо использовать другой алгоритм, либо перейти на более быстрый язык. Вы можете попробовать запустить его в pypy - в некоторых случаях он может быть значительно быстрее, чем CPython. Вы также можете попробовать cython , который скомпилирует ваш код в C и иногда может дать большой выигрыш в производительности, особенно если вы аннотируете свой код информацией о типах cython. Я думаю, что самое большое улучшение может произойти из-за изменения алгоритма, который делает меньше работы, но у меня нет никаких предложений для этого.

Кстати, почему цикл 800000 раз? Каково значение этого числа?

Также, пожалуйста, используйте значимые имена для ваших переменных. Использование односимвольных имен или shrtAbbrv совсем не ускоряет код и очень усложняет понимание того, что он делает.

Answer 3

Есть несколько вещей, которые вы можете улучшить здесь.Начните с профилирования вашей программы с помощью инструмента, подобного cProfile .Это скажет вам, где большая часть времени программы тратится и, следовательно, где оптимизация, вероятно, будет наиболее полезной.Как подсказка, вам не нужно генерировать все триады на каждой итерации программы.

Вам также необходимо исправить отступ, прежде чем вы сможете ожидать достойного ответа.этот вопрос может быть лучше подходит для Code Review .

Answer 4

Я не уверен, что точно понимаю, к чему вы стремитесь, но есть как минимум два изменения, которые могут помочь. Вам, вероятно, не нужно уничтожать и создавать график каждый раз в цикле, поскольку все, что вы делаете, - это переворачиваете один знак веса ребра. И вычисления, чтобы найти треугольники могут быть улучшены.

Вот код, который генерирует полный граф со случайными весами, выбирает случайное ребро в цикле, находит триады и переворачивает вес ребра ...

import random 
import networkx as nx

# complete graph with random 1/-1 as weight
G=nx.complete_graph(5)
for u,v,d in G.edges(data=True):
    d['weight']=random.randrange(-1,2,2) # -1 or 1

edges=G.edges()
for i in range(10):
    u,v = random.choice(edges) # random edge
    nbrs = set(G[u]) & set(G[v]) - set([u,v]) # nodes in traids
    triads = [(u,v,n) for n in nbrs]
    print "triads",triads
    for u,v,w in triads:
        print (u,v,G[u][v]['weight']),(u,w,G[u][w]['weight']),(v,w,G[v][w]['weight'])
    G[u][v]['weight']*=-1