Modèle optimisant l'évolution des réseaux sociaux

Question

J'écris un morceau de code qui modélise l'évolution d'un réseau social. L'idée est que chaque personne est assignée à un nœud et que les relations entre les personnes (les bords du réseau) reçoivent un poids de +1 ou -1 selon que la relation est amicale ou inamicale.

En utilisant ce modèle simple, on peut dire qu'une triade de trois personnes est soit "équilibrée", soit "déséquilibrée", selon que le produit des bords de la triade est positif ou négatif.

Finalement, ce que j'essaie de faire, c'est d'implémenter un modèle de type ising. C'est-à-dire que des arêtes aléatoires sont retournées et la nouvelle relation est conservée si le nouveau réseau a plus de triangles équilibrés (une énergie plus faible) que le réseau avant le retournement, si ce n'est pas le cas alors la nouvelle relation n'est conservée qu'avec une certaine probabilité.

Ok, j'en viens enfin à ma question : J'ai écrit le code suivant, mais l'ensemble de données que j'ai contient ~120k triades, en conséquence, il faudra 4 jours pour l'exécuter !

Quelqu'un peut-il me donner des conseils sur la façon d'optimiser le code ?

Merci.

#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

Les suggestions suivantes n'amélioreront pas beaucoup vos performances car elles ne se situent pas au niveau algorithmique, c'est-à-dire qu'elles ne sont pas très spécifiques à votre problème. Cependant, il s'agit de suggestions génériques pour améliorer légèrement les performances :

À moins que vous n'utilisiez Python 3, modifiez les paramètres suivants

for i in range(800000):

à

for i in xrange(800000):

Ce dernier se contente d'itérer les nombres de 0 à 800000, le premier crée une énorme liste de nombres et itère ensuite cette liste. Faites quelque chose de similaire pour les autres boucles en utilisant range .

Aussi, changez

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

à

e = random.choice(li)

et utiliser e au lieu de li[j] par la suite. Si vous avez vraiment besoin d'un numéro d'index, utilisez random.randint(0, len(li)-1) .

Answer 2

Il existe des modifications syntaxiques que vous pouvez apporter pour accélérer les choses, comme le remplacement de vos fonctions Sum et Prod par les équivalents intégrés sum(x[3] for x in iterable) y reduce(operator.mul, iterable) - il est généralement plus rapide d'utiliser des fonctions intégrées ou des expressions de générateur que des boucles explicites.

D'après ce que je peux dire, la ligne :

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

teste si un flottant se trouve dans une liste de flottants. En le remplaçant par if e[1] in a[i]: supprimera les frais généraux liés à la création de deux set pour chaque comparaison.

Par ailleurs, il n'est pas nécessaire de parcourir en boucle les valeurs d'index d'un tableau, si vous n'utilisez que cet index pour accéder aux éléments, par exemple en remplaçant

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])    

avec

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)    

Cependant, je soupçonne que de tels changements ne feront pas une grande différence dans le temps d'exécution global. Pour cela, vous devez soit utiliser un algorithme différent, soit passer à un langage plus rapide. Vous pouvez essayer de l'exécuter en pypy - Dans certains cas, il peut être nettement plus rapide que CPython. Vous pouvez également essayer cython qui compilera votre code en C et peut parfois offrir un gain de performance important, surtout si vous annotez votre code avec des informations de type cython. Je pense que la plus grande amélioration pourrait venir d'une modification de l'algorithme pour en faire un qui fait moins de travail, mais je n'ai pas de suggestions pour cela.

BTW, pourquoi boucler 800000 fois ? Quelle est la signification de ce nombre ?

Veuillez également utiliser des noms significatifs pour vos variables. L'utilisation de noms à un seul caractère ou de shrtAbbrv n'accélère pas du tout le code, et rend très difficile de suivre ce qu'il fait.

Answer 3

Il y a pas mal de choses que vous pouvez améliorer ici. Commencez par profiler votre programme à l'aide d'un outil tel que cProfile . Cela vous indiquera où le programme passe le plus de temps et donc où l'optimisation sera probablement la plus utile. À titre indicatif, vous n'avez pas besoin de générer toutes les triades à chaque itération du programme.

Vous devez également corriger votre indentation avant de pouvoir espérer une réponse décente.

Quoi qu'il en soit, cette question conviendrait mieux à Examen du code .

Answer 4

Je ne suis pas sûr de comprendre exactement ce que vous visez, mais il y a au moins deux changements qui pourraient vous aider. Vous n'avez probablement pas besoin de détruire et de créer le graphe à chaque fois dans la boucle puisque tout ce que vous faites est de changer le signe du poids d'un bord. Et le calcul pour trouver les triangles peut être amélioré.

Voici un code qui génère un graphe complet avec des poids aléatoires, choisit un bord aléatoire dans une boucle, trouve les triades et retourne le poids du bord...

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