社交网络演化优化模型

Question

我正在编写一段代码来模拟社交网络的演变。这个想法是，每个人都被分配到一个节点，人与人之间的关系（网络上的边）被赋予 +1 或 -1 的权重，具体取决于关系是友好还是不友好。

使用这个简单的模型，您可以说三个人组成的三元组是“平衡”还是“不平衡”，具体取决于三元组的边的乘积是正还是负。

所以最后我想做的是实现一个 ising 类型模型。即，如果新网络比翻转之前的网络具有更多平衡三角形（较低能量），则翻转随机边并保留新关系，如果不是这种情况，则仅以一定概率保留新关系。

好吧，最后我的问题是：我已经编写了以下代码，但是我拥有的数据集包含约 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 等工具对程序进行分析。这将告诉您程序的大部分时间都花在哪里，从而优化哪里可能最有帮助。作为提示，您不需要在程序的每次迭代中生成所有三元组。

在得到合适的答案之前，您还需要修复缩进。

无论如何，这个问题可能更适合代码审查。

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