Creando una red dirigida grande utilizando NetworkX y comprobando la conectividad débil.
Estoy tratando de crear una red dirigida con más de 5000 nodos. Las aristas entre los nodos se basan en la diferencia de un cierto valor asignado a cada nodo; si la diferencia de valores entre pares de nodos es menor que un umbral, hay una arista. Genero una matriz de adyacencia y quiero verificar si el grafo dirigido está débilmente conectado, y también calcular el Page Rank. Actualmente, uso el código a continuación para generar el grafo y me lleva 78s y ocupa casi 7GB de memoria. Quiero saber si hay una forma más eficiente (en tiempo y memoria) de construir y evaluar redes grandes en Python.
“`
%reset -f
!pip install faiss-gpu
import faiss
import numpy as np
import torch
import random
import networkx as nx
import time
device='cuda'
res = faiss.StandardGpuResources()
start=time.time()
<h1>Total de Nodos</h1>
N = 5000
<h1>Media</h1>
mu = 0.5*np.pi
<h1>Varianza</h1>
var = np.pi/18
<h1>Grado máximo de cada nodo</h1>
max_degree = 1000
<h1>Umbral</h1>
value_thres = np.pi/6
<h1>Placeholder</h1>
Values = torch.zeros((N,1),dtype=torch.double,device='cuda')
Matrixs = torch.zeros((2,N,max_degree),dtype=torch.double,device='cuda')
Adj_Matrix = torch.zeros((N,N),dtype=torch.long,device='cuda')
<h1>Generar una red dirigida con N nodos cuya conectividad se basa en los valores</h1>
start_network=time.time()
Values[:,0] = torch.normal(mu,var,(N,))
<h1>Encontrar vecinos hasta max_degree</h1>
<h1>De Pytorch a numpy</h1>
Current = np.float32(Values[:,0].cpu().detach().numpy())
index_flat = faiss.IndexFlatL2(Current[:,None].shape[1])
gpu_index_flat = faiss.index_cpu_to_gpu(res, 0, index_flat)
gpu_index_flat.add(Current[:,None])
m, n = gpu_index_flat.search(Current[:,None], max_degree)
<h1>Índices de posibles vecinos</h1>
Matrixs[1] = torch.from_numpy(n).long()
<h1>Separación de valores</h1>
Matrixs[0] = torch.squeeze(torch.cdist(Values[:,0][:,None][:,None],Values[:,0][:,None][Matrixs[1].long()],p=2))<>
<h1>Construir la Matriz de Adyacencia</h1>
Adj_Matrix[Matrixs[1].long()] = 1
Adj_Matrix-=torch.eye(N,dtype=torch.long,device='cuda')
G = nx.from_numpy_matrix(Adj_Matrix.cpu().detach().numpy())
end=time.time()
print('Tiempo de Creación de la Red',end-start-network)
print('Tiempo Total',end-start-start_network)
“`
davy.ai
Hay algunas formas de optimizar la construcción y evaluación de redes grandes en Python utilizando la biblioteca networkx. Aquí te presento algunas sugerencias:
Utiliza las funciones incorporadas de networkx para calcular propiedades del grafo como los componentes débilmente conectados y el PageRank, en lugar de calcularlos desde cero. Por ejemplo, networkx.weakly_connected_components() puede calcular los componentes débilmente conectados de un grafo dirigido, y networkx.pagerank() puede calcular el PageRank de los nodos en un grafo.
Intenta minimizar el número de bucles e iteraciones en tu código, ya que pueden ser consumidores de tiempo para redes grandes. Vectoriza tus cálculos utilizando funciones de numpy y pytorch siempre que sea posible.
Considera utilizar técnicas de cómputo paralelo, como multiprocessing o aceleración de GPU, para acelerar tus cálculos. La biblioteca faiss-gpu utilizada en el código proporcionado ya aprovecha la aceleración de la GPU.
Aquí tienes un ejemplo de cómo construir una red utilizando una estructura de datos de matriz dispersa:
Esto debería ser más eficiente en memoria que el código original, ya que la matriz de adyacencia se representa utilizando solo elementos distintos de cero. Para verificar si la red está débilmente conectada, puedes utilizar la función incorporada
nx.is_weakly_connected(G)
. Para calcular el PageRank, puedes utilizarnx.pagerank(G)
.