Estas son mis funciones: "import numpy as np import networkx as nx from scipy.linalg…
- User
Estas son mis funciones:
"import numpy as np import networkx as nx from scipy.linalg import solve_triangular import matplotlib.pyplot as plt def leer_archivo(input_file_path): f = open(input_file_path, 'r') n = int(f.readline()) m = int(f.readline()) W = np.zeros(shape=(n,n)) for _ in range(m): line = f.readline() i = int(line.split()[0]) - 1 j = int(line.split()[1]) - 1 W[j,i] = 1.0 f.close()
return W
def dibujarGrafo(W, print_ejes=True):
options = { 'node_color': 'yellow', 'node_size': 200, 'width': 3, 'arrowstyle': '-|>', 'arrowsize': 10, 'with_labels' : True}
N = W.shape[0] G = nx.DiGraph(W.T)
#renombro nodos de 1 a N G = nx.relabel_nodes(G, {i:i+1 for i in range(N)}) if print_ejes: print('Ejes: ', [e for e in G.edges])
nx.draw(G, pos=nx.spring_layout(G), **options)
def calcularRanking(M, p): npages = M.shape[0] rnk = np.arange(0, npages) # ind[k] = i, la pagina k tienen el iesimo orden en la lista. #k∈[0,11] su representacion en el grafico es k+1 scr = np.zeros(npages) # scr[k] = alpha, la pagina k tiene un score de alpha
CODIGO
R = matriz_de_puntajes(M) #calculo R que es: R = WD x = naveganteAleatorio(R,p) #Calculo x con la ec: (I-pWD)x=e
suma = np.sum(x) if suma != 0: x = x / suma #la normalizo para que la suma de x_i de igual a 1
indices_ordenados = np.argsort(x) #vector tal que indices_ordenados[i] = k, osea que los primeros indices corresponden a los alphas mas bajos y los ultimos a mas altos # ej: indices_ordenados[0] = 1 (en el grafico seria el 2) y indices_ordenados[-1] = indices_ordenados[11] = 6 (en el grafico seria el 7)
#indices_reordenados = organizar_posiciones(indices_ordenados) #ahora indices_reordenados[k] = i
#rnk = indices_reordenados
rnk = indices_ordenados
scr = x
return rnk, scr
def organizar_posiciones(p): n = len(p) p2 = [0] * n
for k in range(n): i = p[k] p2[i] = k
return p2
def matriz_de_puntajes(M): """ Esta funcion toma una matriz M que es la matriz de conectividad retorna la matriz de puntajes R que es el producto de M y la matriz diagonal D """ npages = M.shape[0] D_ii = [] # aca almacenamos los elementos en la diagonal de D for n in range(npages): c_j = np.sum(M[:, n]) # definimos a c_j como la sumatoria de elementos de la columna j if c_j != 0: D_ii.append(1/c_j) else: D_ii.append(0) # si c_j = 0, 1/c_j es indefinido entonces se le asigna el valor 0
D = np.diag(np.array(D_ii)) # creamos la matriz diagonal D a partir de los c_j R = M @ D # a partir de M y D podemos formar la matriz R return R
def naveganteAleatorio(R,p): """ Esta funcion toma R una matriz y p un valor entre 0 y 1 R corresponde a la matriz resultante de [completar] p corresponde a la probabilidad del usuario si va a seguir uno de los links retorna un vector x con los puntajes de cada pagina de forma que k es una pagina => x[k] = alpha (puntaje de la pagina) """ npages = R.shape[0]
L, U = descomposicionLU(np.eye(npages)-p*R)
#Al saber que A = (I_n-p*R) acepta descomposicion LU entonces:
A*x = b
se puede resolver haciendo
L*y = b
U*x = y
y = solve_triangular(L,np.ones(npages),lower=True) x = solve_triangular(U,y)
return x
def obtenerMaximoRankingScore(M, p): """ Toma una matriz M y una probabilidad p entre 0 y 1 devulve el mayor ranking alpha """ output = -np.inf
calculo el ranking y los scores
rnk, scr = calcularRanking(M, p) output = np.max(scr)
return output
def descomposicionLU(A): """ Toma una matriz cuadrada A que debe aceptar descomposicion LU Retorna una tupla con los valores de la descomposicion LU como (L,U) """ n = A.shape[0] L = np.eye(n).astype(float) #matriz identidad nxn que va hacer la matriz triangular inferior U = A.astype(float).copy() #matriz A que va a ser la matriz triangular superior
for c in range(n): # c representa columna
pivot = U[c,c] #tomo el elemento en la diagonal que va a funcionar como pivot for f in range(c+1,n): # f representa fila f∈[1,n-1] k = U[f,c]/pivot #encuentro el k para que en U[f,c] = k*pivot L[f,c] = k #coloco k en L U[f, c:n] -= k*U[c, c:n] # tomo la fila con la que estoy trabajando U[c, c:n], lo multiplico por k, y se lo resto a las filas de debajo para formar la columna de ceros en la # primera columna de la submatriz U[c, c:n] exceptuando el primer valor U[c,c]return (L,U)"
analisis cuantitativo, se pide, como m´ınimo, estudiar los tiempos de procesamiento en funci´on del tama˜no del grafo de p´aginas y de la densidad del mismo. Para esto, se espera que presenten gr´aficos mostrando los tiempos de ejecuci´on para obtener la soluci´on en funci´on de la cantidad de nodos/links de diferentes grafos de p´aginas aleatorios.
Tengo esto:
"archivos = ['test_dosestrellas.txt','mathworld_grafo.txt', 'instagram_famosos_grafo.txt', 'test_aleatorio.txt'] #'test_30_segundos.txt'
def generar_grafo_aleatorio(num_nodos, probabilidad_arista): G = nx.gnp_random_graph(num_nodos, probabilidad_arista, directed=True) W = nx.adjacency_matrix(G).todense() return W
def realizar_experimentos(): resultados = [] lista_nodos = [10, 50, 100, 200, 500] # Número de nodos a usar probabilidades_aristas = [0.1, 0.3, 0.5, 0.7, 0.9] # Probabilidad de enlaces
# Diccionario para almacenar grafos para cada configuración grafos = {(n, p): generar_grafo_aleatorio(n, p) for n in lista_nodos for p in probabilidades_aristas} for num_nodos in lista_nodos: for prob_arista in probabilidades_aristas: W = grafos[(num_nodos, prob_arista)] num_aristas = np.sum(W) # Total de aristas start_time = time.time() rnk, scr = calcularRanking(W, p=0.85) fin_tiempo = time.time() resultados.append({ 'nodos': num_nodos, 'aristas': num_aristas, 'tiempo': fin_tiempo - start_time, 'nodos_x_aristas': num_nodos * num_aristas }) nodos = [res['nodos'] for res in resultados] tiempos = [res['tiempo'] for res in resultados] aristas = [res['aristas'] for res in resultados] nodos_x_aristas = [res['nodos_x_aristas'] for res in resultados]"Lo quiero corregir, que no use grafos aleatorios, sino sólo un grafo de "archivos"
Luego, que lo repita para los demás archivos mi visualización de grafo era esta:
plt.figure(figsize=(12, 8)) colors = ['blue', 'green', 'red', 'purple', 'orange'] label_added = {key: False for key in colors}
for res, color in zip(resultados, colors * len(lista_nodos)): label = f'Prob. Arista = {probabilidades_aristas[colors.index(color)]}' if not label_added[color]: plt.scatter(res['nodos'], res['tiempo'], color=color, label=label) label_added[color] = True else: plt.scatter(res['nodos'], res['tiempo'], color=color)
Visualización: Tiempo vs. Número de nodos
plt.title('Tiempo de Procesamiento vs. Número de Nodos por Densidad del Grafo') plt.xlabel('Número de Nodos') plt.ylabel('Tiempo de Procesamiento (s)') plt.legend(title='Densidad del Grafo') plt.grid(True) plt.show()
- Assistant
Para adaptar tu código a que procese grafos a partir de los archivos especificados en lugar de generarlos aleatoriamente, pero realizando las pruebas de tiempo de ejecución para cada grafo y visualizándolos, puedes realizar los siguientes cambios:
Primero, modifica tu código para que cargue los grafos desde los archivos y ejecute el proceso de cálculo del ranking, medición del tiempo y recolección de datos.
Código Modificado para Cargar y Procesar Archivos
Integraremos el código que mide tiempos y genera rankings directamente con la carga de archivos de adjacencia.
import numpy as np import matplotlib.pyplot as plt import time # Asumiendo que todas las funciones previamente definidas todavía están en el entorno de ejecución. archivos = ['test_dosestrellas.txt', 'mathworld_grafo.txt', 'instagram_famosos_grafo.txt', 'test_aleatorio.txt'] nombres_grafos = ['Dos Estrellas', 'Math World', 'Instagram Famosos', 'Aleatorio'] def realizar_experimentos(): resultados = [] for filename, nombre in zip(archivos, nombres_grafos): W = leer_archivo(filename) num_nodos = W.shape[0] num_aristas = np.sum(W) start_time = time.time() rnk, scr = calcularRanking(W, p=0.85) fin_tiempo = time.time() resultados.append({ 'nombre': nombre, 'nodos': num_nodos, 'aristas': num_aristas, 'tiempo': fin_tiempo - start_time, 'nodos_x_aristas': num_nodos * num_aristas }) return resultados resultados = realizar_experimentos() # Visualización de resultados plt.figure(figsize=(12, 8)) colors = ['blue', 'green', 'red', 'yellow'] for res, color in zip(resultados, colors): plt.scatter(res['nodos'], res['tiempo'], color=color, label=res['nombre']) plt.title('Tiempo de Procesamiento vs. Número de Nodos') plt.xlabel('Número de Nodos') plt.ylabel('Tiempo de Procesamiento (s)') plt.legend(title='Archivos') plt.grid(True) plt.show()Análisis del código:
- Carga archivos: Usa los nombres de archivos de un arreglo predefinido para cargar los grafos.
- Medición de tiempo: Mide el tiempo de ejecución del cálculo del ranking para cada grafo.
- Visualización: Crea una gráfica que muestra estos tiempos en función del número de nodos para cada archivo, proporcionando una buena representación visual de la escalabilidad y el desempeño del código.
Nota:
- Asegúrate de que los archivos especificados en
archivosestén en el directorio correcto y accesibles para la funciónleer_archivo. - También es importante que el formato de datos en estos archivos coincida con lo que espera la función
leer_archivo(esto es, dos líneas de enteros seguidas por conexiones). - Verifica que tus funciones de ranking, etc., están óptimamente implementadas y no contienen errores lógicos o de sintaxis que pudieran afectar el rendimiento o la exactitud de los resultados.
- User
Pero ese código lo hace también en funcion de la densidad del grafo? porque tiene que ser variable
- Assistant
Dado que quieres incluir también la variable como la densidad del grafo, y no solo el tamaño en términos de nodos, la forma en que definimos y trabajamos con grafos en tu ejemplo original no varía directamente con la densidad en archivos fijos, ya que la estructura de los grafos descritos en estos archivos no se modifica una vez creados.
Sin embargo, para abordar el análisis de cómo el tiempo de procesamiento varía con la densidad del grafo, introduciría otra función para generar grafos con diferentes densidades, pero manteniendo los mismos nodos. Aquí te muestro cómo:
Modificación del Código para Considerar Varias Densidades por Grafo Fijo
Trabajaremos con un solo archivo pero variando la densidad eliminando aleatoriamente aristas para obtener varias densidades.
import numpy as np import matplotlib.pyplot as plt import networkx as nx import time import copy def generar_grafo_con_densidad(W, nueva_densidad): G = nx.DiGraph(W) num_total_posibles_aristas = G.number_of_nodes() * (G.number_of_nodes() - 1) num_aristas_objetivo = int(num_total_posibles_aristas * nueva_densidad) aristas_a_remover = num_total_posibles_aristas - num_aristas_objetivo while nx.number_of_edges(G) > num_aristas_objetivo: u, v = np.random.choice(G.nodes(), 2, replace=False) if G.has_edge(u, v): G.remove_edge(u, v) W_modificado = nx.adjacency_matrix(G).todense() return W_modificado def realizar_experimentos_densidad(W_original, num_nodos): resultados = [] densidades = [0.1, 0.3, 0.5, 0.7, 0.9] # Diferentes densidades de prueba for densidad in densidades: W = generar_grafo_con_densidad(W_original, densidad) num_aristas = np.sum(W) start_time = time.time() rnk, scr = calcularRanking(W, p=0.85) fin_tiempo = time.time() resultados.append({ 'densidad': densidad, 'nodos': num_nodos, 'aristas': num_aristas, 'tiempo': fin_tiempo - start_time, 'nodos_x_aristas': num_nodos * num_aristas }) return resultados # Elegimos un archivo para las pruebas filename = 'archivo_ejemplo.txt' W_original = leer_archivo(filename) num_nodos = W_original.shape[0] resultados = realizar_experimentos_densidad(W_original, num_nodos) # Visualización de resultados plt.figure(figsize=(12, 8)) colors = plt.cm.viridis(np.linspace(0, 1, len(resultados))) for res, color in zip(resultados, colors): plt.scatter(res['densidad'], res['tiempo'], color=color, s=50, label=f'Densidad = {res["densidad"]}') plt.title('Tiempo de Procesamiento vs. Densidad del Grafo') plt.xlabel('Densidad del Grafo') plt.ylabel('Tiempo de Procesamiento (s)') plt.legend(title='Densidad del Grafo') plt.grid(True) plt.show()Explicación:
En este ejemplo:
generar_grafo_con_densidad: Esta función ajusta la densidad del grafo original eliminando aristas al azar para alcanzar la densidad deseada.- Proceso de Experimentación: Para un grafo dado en
filename, generamos múltiples grafos con diferentes densidades y medimos el tiempo de proceso para cada uno de ellos.
Asegúrate de tener en cuenta la aleatoriedad en la eliminación de aristas; esto podría llevar a grafos con estructuras substancialmente diferentes, lo cual es un factor en el análisis de cómo las características estructurales de un grafo afectan el tiempo de procesamiento.
- User
modificar para que use cada uno de estos archivos cargados:
archivos = ['test_dosestrellas.txt','mathworld_grafo.txt', 'instagram_famosos_grafo.txt', 'test_aleatorio.txt'] #'test_30_segundos.txt'
- Assistant
Para integrar la variación en función de la densidad del grafo y trabajar con cada uno de los archivos listados, debes incorporar dos bucles: uno para iterar sobre los archivos y otro para variar la densidad de los grafos. Aquí te ofrezco una versión adaptada que realiza las pruebas de rendimiento sobre estos múltiples archivos y diferentes densidades para cada archivo:
import numpy as np import matplotlib.pyplot as plt import networkx as nx import time import copy # Asumiendo funciones previas definidas (leer_archivo, calcularRanking) archivos = ['test_dosestrellas.txt', 'mathworld_grafo.txt', 'instagram_famosos_grafo.txt', 'test_aleatorio.txt'] def generar_grafo_con_densidad(W, nueva_densidad): G = nx.DiGraph(W) edges_to_remove = list(G.edges()) np.random.shuffle(edges_to_remove) # Mezclamos las aristas num_aristas_objetivo = int(G.number_of_nodes() * (G.number_of_nodes() - 1) * nueva_densidad) for u, v in edges_to_remove: if nx.number_of_edges(G) > num_aristas_objetivo: G.remove_edge(u, v) else: break return nx.adjacency_matrix(G).todense() def realizar_experimentos_densidad(): resultados = [] densidades = [0.1, 0.3, 0.5, 0.7, 0.9] # Diferentes densidades de prueba for archivo in archivos: W_original = leer_archivo(archivo) num_nodos = W_original.shape[0] for densidad in densidades: W = generar_grafo_con_densidad(W_original, densidad) num_aristas = np.sum(W) start_time = time.time() rnk, scr = calcularRanking(W, p=0.85) fin_tiempo = time.time() resultados.append({ 'archivo': archivo, 'densidad': densidad, 'nodos': num_nodos, 'aristas': num_aristas, 'tiempo': fin_tiempo - start_time, 'nodos_x_aristas': num_nodos * num_aristas }) return resultados resultados = realizar_experimentos_densidad() # Visualización de resultados plt.figure(figsize=(12, 8)) colors = plt.cm.viridis(np.linspace(0, 1, len(densidades))) labels = set() # Para etiquetas únicas en la leyenda for res in resultados: color = colors[densidades.index(res['densidad'])] marker = 'o' if 'estrella' in res['archivo'] else 's' # Diferentes marcadores para un potencial otro archivo label = f'{res["archivo"]} Densidad = {res["densidad"]}' if label not in labels: plt.scatter(res['nodos'], res['tiempo'], color=color, marker=marker, label=label) labels.add(label) else: plt.scatter(res['nodos'], res['tiempo'], color=color, marker=marker) plt.title('Tiempo de Procesamiento vs. Número de Nodos por Densidad del Grafo') plt.xlabel('Número de Nodos') plt.ylabel('Tiempo de Procesamiento (s)') plt.legend(title='Archivo y Densidad', bbox_to_anchor=(1.05, 1), loc='upper left') plt.grid(True) plt.tight_layout() plt.show()Explicación:
-
generar_grafo_con_densidad(): Esta función ahora maneja los casos en los que la densidad resultante puede ser más alta de lo deseado si se eliminan aristas al azar. De todas formas, intentará eliminar aristas hasta obtener la densidad deseada o será tan cercano como posible dada la estructura inicial del grafo. -
realizar_experimentos_densidad(): Ampliamos para incluir todos los archivos, donde cada archivo se procesa a diferentes densidades. -
Visualización: Grafica el tiempo de procesamiento en función del número de nodos, pero ahora agrupado por archivo y densidad para cada conjunto de pruebas.
Este enfoque visualización ahora integra información de densidad en la leyenda permitiendo una mirada más granulada a cómo el tiempo de procesamiento se comporta bajo estas variables para cada archivo especificado.
-
- User
ValueError Traceback (most recent call last) in <cell line: 55>() 54 55 for res in resultados: ---> 56 color = colors[densidades.index(res['densidad'])] 57 marker = 'o' if 'estrella' in res['archivo'] else 's' # Diferentes marcadores para un potencial otro archivo 58 label = f'{res["archivo"]} Densidad = {res["densidad"]}'
ValueError: 0.1 is not in list
- Assistant
El error
"ValueError: 0.1 is not in list"puede ser el resultado de problemas de precisión de punto flotante cuando se intenta buscar un valor de densidad en la listadensidades. Esto es común cuando se trata con números de punto flotante en Python.Para solucionar este problema, podemos cambiar el manejo de las densidades a una forma más robusta mediante el uso de índices directamente en lugar de buscar en la lista, como en el código anterior.
Aquí está el código corregido con un enfoque más robusto para manejar los índices de densidad:
import numpy as np import matplotlib.pyplot as plt import networkx as nx import time import copy archivos = ['test_dosestrellas.txt', 'mathworld_grafo.txt', 'instagram_famosos_grafo.txt', 'test_aleatorio.txt'] def generar_grafo_con_densidad(W, nueva_densidad): G = nx.DiGraph(W) num_aristas_original = G.size() num_nodos = G.number_of_nodes() num_aristas_objetivo = int(num_nodos * (num_nodos - 1) * nueva_densidad) # Eliminar aristas al azar hasta obtener la densidad deseada while G.size() > num_aristas_objetivo: u, v = list(G.edges())[np.random.randint(0, G.size())] G.remove_edge(u, v) # Si el grafo se desconecta, esto puede introducir sesgos en el modelo. Se debe tener cuidado con esto. return nx.adjacency_matrix(G).todense() def realizar_experimentos_densidad(): resultados = [] densidades = [0.1, 0.3, 0.5, 0.7, 0.9] # Diferentes densidades de prueba for archivo in archivos: W_original = leer_archivo(archivo) num_nodos = W_original.shape[0] for i, densidad in enumerate(densidades): W = generar_grafo_con_densidad(W_original, densidad) num_aristas = np.sum(W) start_time = time.time() rnk, scr = calcularRanking(W, p=0.85) tiempo = time.time() - start_time resultados.append({ 'archivo': archivo, 'densidad': densidad, 'nodos': num_nodos, 'aristas': num_aristas, 'tiempo': tiempo, 'indice_densidad': i # Mejor usar un índice para evitar errores de precisión }) return resultados resultados = realizar_experimentos_densidad() # Visualización de resultados plt.figure(figsize=(12, 8)) colors = plt.cm.viridis(np.linspace(0, 1, len(densidades))) for res in resultados: color = colors[res['indice_densidad']] label = f"{res['archivo']} (Densidad {res['densidad']})" plt.scatter(res['nodos'], res['tiempo'], color=color, label=label if res['indice_densidad'] == 0 else "") plt.title('Tiempo de Procesamiento vs. Número de Nodos por Densidad del Grafo') plt.xlabel('Número de Nodos') plt.ylabel('Tiempo de Procesamiento [s]') plt.legend(title='Archivo y Densidad', bbox_to_anchor=(1.05, 1), loc='upper left') plt.grid(True) plt.tight_layout() plt.show()Cambios Realizados:
- Usamos
enumeratepara obtener un índice para cada densidad directamente, lo que evita problemas de precisión al buscar directamente en la listadensidades. - Ajustamos
generar_grafo_con_densidadpara evitar eliminar aristas cuando ya se ha alcanzado la densidad deseada. - Modificamos el código de visualización para evitar duplicar etiquetas en la leyenda.
- Usamos
- User
" in <cell line: 54>() 53 54 for res in resultados: ---> 55 color = colors[res['indice_densidad']] 56 label = f"{res['archivo']} (Densidad {res['densidad']})" 57 plt.scatter(res['nodos'], res['tiempo'], color=color, label=label if res['indice_densidad'] == 0 else "")
IndexError: index 4 is out of bounds for axis 0 with size 4"
ARREGLAR por favor
- Assistant
Parece que hay un problema con el mapeo de los colores a cada densidad. El error
IndexError: index 4 is out of bounds for axis 0 with size 4sugiere que el número de colores generados no es suficiente para cubrir los índices de densidades. Esto es debido a que estamos intentando acceder a un índice que no existe en el arreglo generado porcolors.Podríamos solucionar este problema asegurando que la array de colores
colorstenga el tamaño adecuado basado en el número de densidades. Vamos a realizar un ajuste para asegurarnos de que generamos un mapa de colores que pueda acomodar correctamente todos los índices de densidades. Además, vamos a verificar todas las partes del código donde estás utilizando el arreglocolorspara asegurarnos de que la cantidad de elementos endensidadesse corresponda precisamente con la longitud decolors.Código corregido:
import numpy as np import matplotlib.pyplot as plt import networkx as nx import time import copy archivos = ['test_dosestrellas.txt', 'mathworld_grafo.txt', 'instagram_famosos_grafo.txt', 'test_aleatorio.txt'] def generar_grafo_con_densidad(W, nueva_densidad): G = nx.DiGraph(W) num_aristas_original = G.size() num_nodos = G.number_of_nodes() num_aristas_objetivo = int(num_nodos * (num_nodos - 1) * nueva_densidad) # Eliminar aristas al azar hasta obtener la densidad deseada while G.size() > num_aristas_objetivo: u, v = list(G.edges())[np.random.randint(0, G.size())] G.remove_edge(u, v) # Si el grafo se desconecta, esto puede introducir sesgos en el modelo. Se debe tener cuidado con esto. return nx.adjacency_matrix(G).todense() def realizar_experimentos_densidad(): resultados = [] densidades = [0.1, 0.3, 0.5, 0.7, 0.9] # Diferentes densidades de prueba colors = plt.cm.viridis(np.linspace(0, 1, len(densidades))) # Asegurar colores para cada densidad for archivo in archivos: W_original = leer_archivo(archivo) num_nodos = W_original.shape[0] for i, densidad in enumerate(densidades): W = generar_grafo_con_densidad(W_original, densidad) num_aristas = np.sum(W) start_time = time.time() rnk, scr = calcularRanking(W, p=0.85) tiempo = time.time() - start_time resultados.append({ 'archivo': archivo, 'densidad': densidad, 'nodos': num_nodos, 'aristas': num_aristas, 'tiempo': tiempo, 'color': colors[i] # Guardamos el color correspondiente aquí mismo }) return resultados resultados = realizar_experimentos_densidad() # Visualización de resultados plt.figure(figsize=(12, 8)) for res in resultados: color = res['color'] label = f"{res['archivo']} (Densidad {res['densidad']})" plt.scatter(res['nodos'], res['tiempo'], color=color, label=label if res['densidad'] == 0.1 else "") plt.title('Tiempo de Procesamiento vs. Número de Nodos por Densidad del Grafo') plt.xlabel('Número de Nodos') plt.ylabel('Tiempo de Procesamiento [s]') plt.legend(title='Archivo y Densidad', bbox_to_anchor=(1.05, 1), loc='upper left') plt.grid(True) plt.tight_layout() plt.show()En este código, ajustamos el mapa de colores para que coincida exactamente con el número de densidades y almacenamos el color correspondiente directamente en el diccionario de resultados para evitar cualquier discrepancia en los índices de acceso. Esto resuelve el problema del índice fuera de límites.
- User
import time import matplotlib.pyplot as plt
pruebo diferentes grafos y grafico tamaño en funcion del tiempo?
archivo_test = 'test_30_segundos.txt'
#CARGA DE ARCHIVO EN GRAFO W = leer_archivo(archivo_test)
archivos = ['test_dosestrellas.txt','mathworld_grafo.txt', 'instagram_famosos_grafo.txt', 'test_aleatorio.txt'] #'test_30_segundos.txt'
cantNodos = [] cantAristas = [] tiempos = [] lista_p = [0.1, 0.5, 0.95] colores = ['red', 'green', 'blue']
#dibujarGrafo(W, print_ejes=False) for x in range(3): p2 = lista_p[x] color = colores[x] for archivo in archivos: W = leer_archivo(archivo) n = W.shape[0] cantNodos.append(n) #cantAristas.append(np.sum(W)) inicio = time.time() calcularRanking(W,p2) fin = time.time() tiempos.append(fin-inicio)
plt.scatter(tiempos,cantNodos, color=color) plt.title('Cantidad de Nodos vs Tiempo') plt.xlabel('Tiempo') plt.ylabel('Cantidad de Nodos') tiempos = [] cantNodos = []
plt.show()
modificar para que ponga gráficos variando por densidad
- Assistant
Para modificar tu script para que grafique los resultados variando la densidad del grafo en lugar de diferentes valores de ( p ), primero necesitas generar versiones de cada grafo con diferentes densidades. Podemos utilizar un enfoque similar al que propuse anteriormente para ajustar la densidad de cada grafo. Luego graficaremos el tiempo de procesamiento en función del número de nodos para cada densidad.
A continuación, te presento el código modificado para graficar en función de la densidad del grafo:
import time import matplotlib.pyplot as plt import numpy as np import networkx as nx archivos = ['test_dosestrellas.txt', 'mathworld_grafo.txt', 'instagram_famosos_grafo.txt', 'test_aleatorio.txt'] densidades = [0.1, 0.5, 0.9] # Por ejemplo, tres niveles de densidad colores = ['red', 'green', 'blue'] p = 0.85 # Valor fijo de p para simplificar, ajuste según sea necesario def generar_grafo_con_densidad(W, nueva_densidad): G = nx.DiGraph(W) num_aristas = nx.number_of_edges(G) num_nodos = nx.number_of_nodes(G) num_aristas_deseadas = int(num_nodos * (num_nodos - 1) * nueva_densidad) if num_aristas > num_aristas_deseadas: while num_aristas > num_aristas_deseadas: u, v = list(G.edges())[np.random.randint(0, num_aristas)] G.remove_edge(u, v) num_aristas -= 1 return nx.adjacency_matrix(G).todense() plt.figure(figsize=(10, 8)) for idx, densidad in enumerate(densidades): tiempos = [] cantNodos = [] color = colores[idx] for archivo in archivos: W_original = leer_archivo(archivo) # Cargar el grafo original desde archivo W = generar_grafo_con_densidad(W_original, densidad) n = W.shape[0] cantNodos.append(n) inicio = time.time() calcularRanking(W, p) fin = time.time() tiempos.append(fin - inicio) # Plotting single scatter for same color with label plt.scatter(tiempos, cantNodos, color=color, label=f'Densidad={densidad}') plt.title('Tiempo de ejecución vs Cantidad de Nodos por Densidad del Grafo') plt.xlabel('Tiempo de Ejecución (s)') plt.ylabel('Cantidad de Nodos') plt.legend(title='Densidades') plt.grid(True) plt.show()Notas importantes:
- Densidad: Aumentar o disminuir el número de aristas para acercarse a la densidad deseada (esto podría resultar en una densidad ligeramente diferente si el ajuste manual de aristas crea situaciones inesperadas, como desconexión del grafo).
- Visualización: El gráfico muestra el tiempo de ejecución en función del número de nodos para cada densidad especificada, con diferentes colores representando las densidades.
- Eficiencia: Este enfoque puede ser ineficiente para grafos muy grandes o densidades muy bajas, especialmente en términos de tiempo de cálculo y riesgos de modificaciones estructurales significativas en el grafo.
Este script te permitirá analizar cómo las variaciones en la densidad de los grafos afectan el tiempo de procesamiento para calcular el ranking de las páginas, ayudando a entender mejor las implicaciones del tamaño y la estructura del grafo en el rendimiento del algoritmo.
- User
Gracias. y ahora quiero otro gráfico pero en vez de con distinta cantidad de nodos, con distintas cantidades de aristas
- Assistant
Para adaptar el código para producir un gráfico que muestre el tiempo de procesamiento en función del número de aristas, en lugar de la cantidad de nodos, basta con cambiar los elementos que se plotean en el gráfico y asegurarse de que estamos contabilizando correctamente el número de aristas en cada configuración de densidad del grafo generado. Aquí tienes el código modificado:
import time import matplotlib.pyplot as plt import numpy as np import networkx as nx archivos = ['test_dosestrellas.txt', 'mathworld_grafo.txt', 'instagram_famosos_grafo.txt', 'test_aleatorio.txt'] densidades = [0.1, 0.5, 0.9] # Diferentes densidades colores = ['red', 'green', 'blue'] p = 0.85 # Un valor fijo de p para simplificar def generar_grafo_con_densidad(W, nueva_densidad): G = nx.DiGraph(W) num_nodos = G.number_of_nodes() num_aristas_deseadas = int(num_nodos * (num_nodos - 1) * nueva_densidad) # Si ya cumplimos la densidad deseada, regreamos lo mismo if nx.number_of_edges(G) <= num_aristas_deseadas: return W while nx.number_of_edges(G) > num_aristas_deseadas: u, v = list(G.edges())[np.random.randint(0, nx.number_of_edges(G))] G.remove_edge(u, v) return nx.adjacency_matrix(G).todense() plt.figure(figsize=(10, 8)) for idx, densidad in enumerate(densidades): tiempos = [] cantAristas = [] color = colores[idx] for archivo in archivos: W_original = leer_archivo(archivo) # Cargar el grafo original desde archivo W = generar_grafo_con_densidad(W_original, densidad) num_aristas = np.sum(W) cantAristas.append(num_aristas) inicio = time.time() calcularRanking(W, p) fin = time.time() tiempos.append(fin - inicio) # Plotear los tiempos contra la cantidad de aristas plt.scatter(tiempos, cantAristas, color=color, label=f'Densidad={densidad}') plt.title('Tiempo de ejecución vs Cantidad de Aristas por Densidad del Grafo') plt.xlabel('Tiempo de Ejecución (s)') plt.ylabel('Cantidad de Aristas') plt.legend(title='Densidades') plt.grid(True) plt.show()Resumen del código:
- Generación del gráfico generado: Corresponde modificar la función
generar_grafo_con_densidadpara manejar casos donde la densidad es ya más baja que la deseada. - Recolección de datos: Calculamos el número de aristas en lugar del número de nodos y lo usamos para graficar.
- Visualización: Dibuja un gráfico que muestra cómo el tiempo de ejecución varía en función del número de aristas para diferentes densidades especificadas.
Este enfoque te permitirá ver directamente cómo la cantidad de relaciones (aristas) en un grafo afecta los tiempos de ejecución de tu algoritmo de ranking, lo que es particularmente útil para evaluar la eficiencia del algoritmo en grafos de diferentes densidades y tamaños.
- Generación del gráfico generado: Corresponde modificar la función
- User
Es redundante variar la cantidad de aristas ya que tenemos la densidad?
- Assistant
En cierto sentido, variar la cantidad de aristas manteniendo fijo el número de nodos y observando sus efectos es, de hecho, variar la densidad del grafo, puesto que la densidad está directamente relacionada con la proporción de aristas presentes relativas al número máximo de aristas posibles en un grafo dado. La densidad del grafo ( D ) se define típicamente como:
[ D = \frac{2E}{N(N-1)} ]
donde ( E ) es el número de aristas y ( N ) es el número de nodos para un grafo no dirigido. Para grafos dirigidos, el factor 2 en el denominador se omite:
[ D = \frac{E}{N(N-1)} ]
Por lo tanto, si mantienes fija la cantidad de nodos y solo ajustas el número de aristas (como lo hiciste modificando la densidad del gráfico), en realidad estás examinando cómo las variaciones en la densidad afectan el rendimiento del algoritmo. El gráfico de tiempo de ejecución versus número de aristas por diferentes densidades es conceptualmente similar al gráfico de tiempo versus densidades porque, para un tamaño de grafo fijo, ambos son representaciones del mismo fenómeno — cómo la conectividad del grafo afecta el rendimiento del algoritmo.
Cuando podría ser relevante ajustar solo el número de aristas:
- Detalles de implementación: Si estás específicamente interesado en cómo el almacenamiento o la manipulación de aristas (en términos de estructuras de datos y algoritmos utilizados) impactan el rendimiento, independientemente de la densidad.
- Estudios granulares: En algunos casos, podría ser importante comprender cómo pequeños cambios en el número de aristas (en un rango de densidades muy ajustado) impactan el rendimiento, especialmente cuando se está cerca de ciertos umbrales críticos de conectividad (como el punto de transición de un grafo de ser desconectado a conectado).
Sugerencias para estudios adicionales:
- Comparación de Algoritmos: Considerando que estás analizando el rendimiento del cálculo de rankings de páginas, también podrías explorar cómo diferentes algoritmos (por ejemplo, variaciones en la implementación de PageRank, diferentes maneras de manejar cuellos de botella computacionales) reaccionan a cambios en la densidad.
- Análisis de Comportamiento Asintótico: Estudiar cómo el comportamiento del cálculo de rankings cambia a medida que el número de nodos se escala hacia arriba o hacia abajo puede revelar más sobre la eficiencia del algoritmo bajo condiciones extremas.
En conclusión, mientras que ajustar las aristas para diferentes densidades te brinda una buena medida general, el enfoque específico debe ser seleccionado en función de las preguntas de investigación exactas que pretendes responder y cómo estos ajustes facilitan la comprensión de esas preguntas.
- User
Qué conclusiones se puede obtener del analisis cuantitativo del graficos?
- Assistant
El análisis cuantitativo de un gráfico que relaciona el tiempo de procesamiento del cálculo de ranking de páginas con la cantidad de aristas (o la densidad) de un grafo puede revelar varios aspectos importantes del comportamiento del algoritmo y la naturaleza de los datos procesados. Aquí están algunas conclusiones potenciales que podrías derivar de estos gráficos:
-
Complejidad Computacional: El gráfico puede ayudarte a entender cómo la complejidad del algoritmo de ranking escala con el tamaño del gráfico. Si el tiempo de procesamiento aumenta rápidamente con un incremento en el número de aristas, esto podría indicar que el algoritmo podría no ser eficiente para grafos grandes o densos. Esto es especialmente relevante para algoritmos como PageRank, donde la convergencia puede ser más lenta en grafos densos.
-
Comportamiento Asintótico: Los gráficos pueden mostrar cómo se comporta el algoritmo cuando el número de aristas se acerca al máximo posible (es decir, cuando el grafo se vuelve completo en el caso de grafos no dirigidos). Este es un caso de prueba extremo que puede revelar problemas de rendimiento no observados en grafos más dispersos.
-
Influencia de la Densidad: Observar el impacto de la densidad del grafo en el tiempo de procesamiento ayuda a determinar si el algoritmo es más adecuado para grafos dispersos o densos. Esto es importante para su aplicación práctica, donde las características del grafo objetivo pueden variar considerablemente.
-
Puntos de Inflexión o Umbral: Si el gráfico muestra un cambio repentino en el tiempo de procesamiento a ciertos niveles de densidad, esto puede indicar un umbral o punto de inflexión donde la naturaleza del problema cambia (por ejemplo, un cambio en el método de resolución más óptimo o en el comportamiento del algoritmo).
-
Optimización y Mejoras en el Algoritmo: Identificar regiones donde el tiempo de procesamiento es desproporcionadamente alto puede sugerir áreas para la optimización del algoritmo. Variaciones en la implementación, como diferentes esquemas de almacenamiento de datos o paralelización, pueden ser exploradas para abordar estos cuellos de botella.
-
Validación de la Teoría: Los resultados empíricos (gráficos) pueden ser comparados con la teoría computacional, ayudando a validar o refutar las complejidades teóricas esperadas del algoritmo bajo ciertas condiciones.
Consideraciones Adicionales:
- Robustez y Consistencia: Realizar pruebas adicionales bajo diferentes configuraciones y en diferentes grafos de prueba para confirmar la consistencia de los resultados.
- Comparación con otros algoritmos: Sería útil comparar estos resultados con los tiempos de ejecución de otros algoritmos de cálculo de ranking para evaluar relativa eficiencia y adecuación para diferentes tipos de grafos.
Conclusión: El análisis de estos gráficos no solo ayuda a comprender y mejorar el rendimiento del algoritmo actual, sino que también proporciona información crucial para su aplicación y adaptación en contextos prácticos y teóricos.
-