Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como elaborar um algoritmo de hill climbing (steepest ascent) para redes complexas?

0 votos
19 visitas
perguntada Out 27 em Sistemas Complexos por Renan Abrantes (16 pontos)  
editado Out 27 por Renan Abrantes

Suponha que cada vértice \(i\) de uma rede complexa tenha um valor \(P_i(y)\) associado. Nosso objetivo é maximizar \(P(y)\) a partir do espaço de possibilidades de \(i\), que são todos os vértices vizinhos a \(i\) e seus respectivos \(P(y)\), repetindo este procedimento até que o próprio vértice \(i\) represente o máximo valor associado \(P(y)\) na sua vizinhança.
A execução desse algoritmo é útil para encontrar a estrutura de máximos locais da rede.

Compartilhe

1 Resposta

0 votos
respondida Out 27 por Renan Abrantes (16 pontos)  

Neste algoritmo, precisaremos de três módulos do Python:

import csv
import networkit as nk
import pandas as pd

O Networkit foi desenhado explicitamente para grandes redes e tem uma performance melhor que o NetworkX. Para mais informações sobre performance, clique aqui.

Vamos definir o algoritmo de hill climbing como uma função no Python. A função necessitará de dois insumos:

  • A rede "G", não ponderada (unweighted) e não direcionada (undirected), em formato de edge list. A edge list é uma lista com todas as conexões dos vértices e tem duas colunas, sendo a primeira com o vértice de origem da conexão e a segunda com o vértice de destino da conexão.
  • A lista "Py", que associa o vértice na primeira coluna a um valor esperado na segunda coluna.

O primeiro passo é ler a rede e criar uma lista com as vizinhanças de qualquer vértice i, dois a dois:

def HillClimbing(G, Py):

    # Ler a rede, que está definida por edge list.
    edges = nk.graphio.EdgeListReader(',', 0).read(G)
    allneighbors = []
    nnodes = edges.numberOfNodes()
    nodes = list(range(nnodes)) #cria lista com número de vértices

    # A partir da rede, cria lista com a vizinhança de qualquer vértice i, dois a dois.
    apsp = nk.distance.APSP(edges) #APSP calcula a distância entre todos os vértices
    apsp.run()
    for i in nodes:
        for j in nodes:
            if apsp.getDistance(i, j) == 1: #distância igual a um para pegar a vizinhança
                allneighbors.append([int(i),int(j)])

Agora, vamos ler o arquivo Py e criar uma lista com os valores de Py para cada vizinhança de i, dois a dois:

    # Lê arquivo com valor de interesse associado ao vértice e cria lista; neste caso, o valor é o prody.
    prody = []
    with open (Py) as fh:
        reader = csv.reader(fh)
        for i in reader:
            prody.append([int(i[0]),float(i[1])])

    # Cria lista com os valores prody associados à vizinhança de qualquer vértice i, dois a dois.
    prodyneighbors = allneighbors
    for j in prodyneighbors:
        for i in prody:
            if j[0] == i[0]:
                j[0] = [j[0], i[1]]
            elif j[1] == i[0]:
                j[1] = [j[1], i[1]]

Comparando cada par vizinho, definimos o vértice com maior e menor Py. Posteriormente, vamos contar o número de vezes que cada vértice foi maior ou menor na comparação e mensurar o seu degree.

    # Define o vértice com prody máximo/mínimo para cada par vizinho (maxprodyneighbors/minprodyneighbors).
    maxprodyneighbors = []
    for j in prodyneighbors:
        if j[0][1] >= j[1][1]: #observação: se o prody for igual para os dois vértices, decide-se ficar no vértice de origem; se for maior, a escolha é óbvia.
            maxprodyneighbors.append(int(j[0][0]))
        elif j[0][1] < j[1][1]:
            maxprodyneighbors.append(int(j[1][0]))
    minprodyneighbors = []
    for j in prodyneighbors:
        if j[0][1] < j[1][1]:
            minprodyneighbors.append(int(j[0][0]))
        elif j[0][1] >= j[1][1]:
            minprodyneighbors.append(int(j[1][0]))

    # Cria listas com a contagem de vezes que o vértice i "ganhou" ou "perdeu" na comparação dois a dois. A soma dos dois valores para o vértice i deve ser igual ao seu degree.
    contar_melhor = []
    contar_pior = []
    for j in nodes:
        contar_melhor.append([j, maxprodyneighbors.count(j)/2])
    for j in nodes:
        contar_pior.append([j, minprodyneighbors.count(j)/2])

    # Cria lista com degree dos vértices.
    degree=nk.centrality.DegreeCentrality(edges)
    degree.run()
    list_degree=degree.scores()

Observe que a soma do número de vezes que um vértice ganha ou perde dos seus vizinhos se igual justamente ao seu degree. Adicionalmente, é fácil perceber que se o vértice é melhor que todos os seus vizinhos, ele configura um máximo local na rede. Por outro lado, se ele é pior que todos os seus vizinhos, ele configura um mínimo local.

Finalmente, vamos para a construção do steepest ascent hill climbing. Primeiro, temos que definir o espaço de possibilidades. Podemos, assim, escolher quem é o melhor vizinho e repetir os passos até chegar a um máximo local, ou seja, no qual o vértice \(i\) é melhor que todos os seus vizinhos.

    # Steepest ascent hill climbing
        # Define o espaço de possibilidades do vértice i (hill_i) e define a melhor escolha para o vértice i (hill_j)
    hill_i = []
    hill_j = []
    for i in prody:
        hill_i.append([i[0], [j[1][0] for j in prodyneighbors if j[0][0] == i[0]], i[1], [j[1][1] for j in prodyneighbors if j[0][0] == i[0]]])
    for j in hill_i:
        if j[2] >= max(j[3]):
            hill_j.append([int(j[0]), j[2], int(j[0]), j[2]])
        elif j[2] < max(j[3]):
            hill_j.append([int(j[0]), j[2], int(j[1][j[3].index(max(j[3]))]), max(j[3])])

        # Executa o algoritmo a partir do vértice i até chegar ao máximo local do vértice k, após n passos
    final_hill = []
    for j in hill_j:
        i_0 = hill_j.index(j)
        prody_0 = j[1]
        i_n = hill_j.index(j)
        prody_n = j[1]
        contar = 0
        while j[0] != j[2]:
            contar = contar + 1
            j = hill_j[j[2]]
            i_n = hill_j.index(j)
            prody_n = j[1]
        final_hill.append([i_0, prody_0, i_n, prody_n, contar])

Agora só falta criar um DataFrame e inserir as estatísticas de interesse, exportando para um .csv ao final:

    # Coleta de dados via DataFrame
    cdata={}
    df=pd.DataFrame(cdata) #cria dataframe vazio a partir do dicionário vazio acima
    df['Degree'] = list_degree
    df['Contar Melhor 1x1'] = [i[1] for i in contar_melhor]
    df['Contar Pior 1x1'] = [i[1] for i in contar_pior]
    df['Prody Node Id'] = [i[1] for i in prody]
    df['Node Id N'] = [i[2] for i in final_hill]
    df['Prody Node Id N'] = [i[3] for i in final_hill]
    df['N de Passos'] = [i[4] for i in final_hill]

    df.to_csv('Hill_Climbing_Results.csv')
...