Социальная эволюция сети


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

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

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

Я написал следующий код, но данных у меня содержит ~120к триады, и в результате это уйдет 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]


Комментарии
2 ответа

#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

Вы можете захотеть взглянуть на библиотеки numpy, он имеет функции, как это написано в эффективном С.

def Sum(iterable):
p= 0

п? почему Р?

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

Руководство по стилю Python рекомендует lowercase_with_underscores для глобальных функций. Имя также предлагает свою универсальную функцию суммирования, которая его не. Нет указаний на какие данные он рассчитывает. Одной строкой документации должен, как минимум, объяснить, что.

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

Не использовать глобальные переменные. Вместо того, чтобы передать г в качестве параметра. Также, я рекомендую против того, чтобы называть это Г.

    Edges=[]
Triads=[]

Руководство по стилю Python recommemnds lowercase_with_underscores для локальных имен переменных

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

Я рекомендую comprehnsion список

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

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.

Создайте список с одним элементом, положить, что в наборе, просто позвонить issubet глупо. Используйте края[я][Дж][1] в firstgen.

                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:

Я думаю, что вы должны читать CSV-файлы в двоичном режиме.

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

Использовать для source, dest, то значение в строке: литий.добавить(тип float(источник), поплавок(дест), поплавок(значения))

Вы действительно хотите, чтобы поплавки? Источник и место назначения действительно плавает или они ИНЦ?

G=nx.Graph()
G.add_weighted_edges_from(li)

for i in xrange(800000):

Не выполнять петли на уровне модуля. Код, написанный внутри функции будет работать быстрее.
е = случайное.выбор(литий) # выбрать случайное ребро

    TriNei=[]
a=CalcTriads(e[0]) # Find triads of first node in the chosen edge

Не используйте имена переменных, как, в одной букве имени переменной-это ужасная потеря информации.

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

Не использовать xrange для перебора контейнеров.

        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]

Что вы должны рассмотреть возможность сделать это написать функцию, которая дана узел вычисляет изменение в "энергии", которые могли бы произойти, если он был перевернут. Прямо сейчас вы рассчитывать до и после, но вы должны быть в состоянии просто вычислить дельту без изменения. Если можно эффективно вычислять Дельты, это все, что вам нужно.

6
ответ дан 18 июля 2011 в 04:07 Источник Поделиться

Следующие строки выглядят особенно дорого:

G.clear()
G.add_weighted_edges_from(li)

Почему вам очистить весь график и воссоздавать его? Разве нет более прямой путь, чтобы изменить график, не создавая его с нуля? Когда я посмотрел на ссылки, я нашел методы, как диаграммы.remove_edge(U,В) и график.add_weighted_edges_from(ebunch,**м[,attr_dict]) кажется, что лучшие способы добавления и удаления ребер без воссоздания всю диаграмму с нуля.

Вы должны также добавить какое-либо кэширование, чтобы CalcTriads(Н) , потому что соседи из н не меняется и при фиксированном п вы постоянно пересчитывать соседей с нуля, который является ненужным, потому что только веса ребер не изменяется фактический узлы, подключенные к Н.

0
ответ дан 17 июля 2011 в 11:07 Источник Поделиться