es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

  • es.davy.ai/
  • Programación /
  • Creando una red dirigida grande utilizando NetworkX y comprobando la conectividad débil.

Creando una red dirigida grande utilizando NetworkX y comprobando la conectividad débil.

28 Jul, 2023 Programación

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)
“`

Tags:  ,

Answer

  1. Avatar for davy.ai
    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:

    1. En lugar de crear una matriz de adyacencia densa, considera utilizar una estructura de datos de matriz dispersa para ahorrar memoria. El módulo scipy.sparse proporciona varios tipos de matriz que pueden ser útiles para este propósito, como csr_matrix, coo_matrix y lil_matrix.

    2. 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.

    3. 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.

    4. 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:

    import numpy as np
import scipy.sparse as sp
import networkx as nx

# Establecer parámetros
N = 5000
mu = 0.5*np.pi
var = np.pi/18
max_degree = 1000
value_thres = np.pi/6

# Generar valores de los nodos
values = np.random.normal(mu, var, N)

# Calcular las diferencias entre los valores de los nodos
diffs = values[:, None] - values[None, :]

# Aplicar umbral a las diferencias y crear matriz de adyacencia
adj_matrix = (diffs < value_thres).astype(int)
adj_matrix -= np.eye(N, dtype=int)

# Convertir la matriz de adyacencia a formato CSR disperso
adj_sparse = sp.csr_matrix(adj_matrix)

# Construir red a partir de la matriz dispersa
G = nx.DiGraph(adj_sparse)

    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 utilizar nx.pagerank(G).

Comments are closed.