3

我正在编写一段代码来模拟社交网络的演变。这个想法是，每个人都被分配到一个节点，人们之间的关系（网络上的边缘）被赋予 +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]
4

4 回答 4

5

以下建议不会大大提高您的性能，因为它们不在算法级别上，即不是很针对您的问题。但是，它们是用于轻微性能改进的通用建议：

除非您使用的是 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).

于 2011-07-17T18:35:11.830 回答
4

您可以进行语法更改以加快速度，例如将 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 根本不会加快代码速度，并且很难理解它在做什么。

于 2011-07-17T19:49:17.567 回答
2

这里有很多可以改进的地方。首先使用诸如cProfile 之类的工具分析您的程序。这将告诉您程序的大部分时间都花在了哪里，因此优化可能最有帮助。作为提示，您不需要在程序的每次迭代中生成所有三元组。

您还需要修复缩进，然后才能期待一个体面的答案。

无论如何，这个问题可能更适合Code Review。

于 2011-07-17T18:24:19.610 回答
1

我不确定我是否完全理解您的目标，但至少有两个更改可能会有所帮助。您可能不需要每次都在循环中销毁和创建图形，因为您所做的只是翻转一个边权重符号。并且可以改进找到三角形的计算。

这是一些代码，它生成一个具有随机权重的完整图，在循环中选择一条随机边，找到三元组并翻转边权重......

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
于 2011-07-18T00:10:10.413 回答