Skip to content
TheChatArchiveThe Chat Archive
gpt-4-turbo-2024-04-09· OpenAIAi2 WildChat-4.8M (AI2)

Estas son mis funciones: "import numpy as np import networkx as nx from scipy.linalg…

  1. 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()

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

    1. Carga archivos: Usa los nombres de archivos de un arreglo predefinido para cargar los grafos.
    2. Medición de tiempo: Mide el tiempo de ejecución del cálculo del ranking para cada grafo.
    3. 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 archivos estén en el directorio correcto y accesibles para la función leer_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.
  3. User

    Pero ese código lo hace también en funcion de la densidad del grafo? porque tiene que ser variable

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

    1. generar_grafo_con_densidad: Esta función ajusta la densidad del grafo original eliminando aristas al azar para alcanzar la densidad deseada.
    2. 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.

  5. 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'

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

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

    2. realizar_experimentos_densidad(): Ampliamos para incluir todos los archivos, donde cada archivo se procesa a diferentes densidades.

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

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

  8. 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 lista densidades. 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 enumerate para obtener un índice para cada densidad directamente, lo que evita problemas de precisión al buscar directamente en la lista densidades.
    • Ajustamos generar_grafo_con_densidad para 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.
  9. 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

  10. 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 4 sugiere 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 por colors.

    Podríamos solucionar este problema asegurando que la array de colores colors tenga 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 arreglo colors para asegurarnos de que la cantidad de elementos en densidades se corresponda precisamente con la longitud de colors.

    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.

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

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

    1. 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).
    2. 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.
    3. 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.

  13. User

    Gracias. y ahora quiero otro gráfico pero en vez de con distinta cantidad de nodos, con distintas cantidades de aristas

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

    1. Generación del gráfico generado: Corresponde modificar la función generar_grafo_con_densidad para manejar casos donde la densidad es ya más baja que la deseada.
    2. Recolección de datos: Calculamos el número de aristas en lugar del número de nodos y lo usamos para graficar.
    3. 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.

  15. User

    Es redundante variar la cantidad de aristas ya que tenemos la densidad?

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

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

  17. User

    Qué conclusiones se puede obtener del analisis cuantitativo del graficos?

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

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

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

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

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

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

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