优化社交网络演化模型

Question

我正在写一段代码，用来模拟社交网络的发展。简单来说，每个人都对应一个节点，而人与人之间的关系（在网络中称为边）会根据关系是友好还是不友好，分别赋予+1或-1的权重。

通过这个简单的模型，我们可以判断三个人的关系组合是“平衡”的还是“不平衡”的，这取决于这三个人之间的关系边的乘积是正数还是负数。

最后，我想实现一种类似于伊辛模型的东西。也就是说，随机改变一些关系，如果新的网络中有更多的平衡三人组合（能量更低），那么就保留这个新关系；如果没有，那么这个新关系只有在一定概率下才会被保留。

好了，接下来是我的问题：我写了以下代码，但我的数据集大约有12万个三人组合，因此运行需要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 个回答

撰写回答