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

como implementar algoritmos de distâncias mínimas e de centralidade em redes?

0 votos
4 visitas
perguntada Set 14 em Ciência da Computação por Sergio Costa (1 ponto)  

Comparação de algoritmos de mínimas distâncias entre nós de uma rede; e aplicação de cálculos de centralidade. Questão 2.4 do livro "Complex Networks: Principles, Methods and Applications", por Vitor Latora, Vincenzo Nicosia e Giovanni Russo (Capítulo 2, pág 67).

Compartilhe

1 Resposta

0 votos
respondida Set 14 por Sergio Costa (1 ponto)  
editado 3 dias atrás por Sergio Costa

Olá, amigos!

A comparação e a implementação dos algoritmos serão feitas com base na resolução do exercício 2.4 do livro citado acima.

A resolução terá duas partes:

a. Implementar e checar o algoritmos de distâncias mínimas sobre a rede na figura 2.1(a), que trata de casamento entre famílias florentinas proeminentes no século XV. Mais especificamente, comparar um algoritmo que mede a distância mínima entre os nós por meio da matriz de adjacência com outro algoritmo advindo de uma variação do BFS (Breadth First Search) no Apêndice A.6 que passa a distância mínima e o caminho traçado.

b. Calcular medidas de centralidade de uma outra rede apresentada no mesmo exercício (closeness centrality para os nós 1 e 4, e betweenness centrality do nó 4).


a. O item "a" tem como base a seguinte rede de famílias proeminentes do século XV. Para desenhar a rede, utilizei o pacote networkx. Abaixo, segue código para edição da imagem.

import networkx as nx

if __name__=="__main__":
    f = nx.Graph()
    f.add_edges_from([(0,8),(9,13),(13,8),(8,2),(8,1),(1,5),(1,6),(6,7),
                      (6,3),(3,10),(3,14),(10,14),(10,4),(4,14),(4,2),
                      (14,12),(12,15),(15,6),(15,8),(12,8)])
    f.add_node(11)
    labeldict ={}
    labeldict[0]='Acciaiuoli'
    labeldict[1]='Albizzi'
    labeldict[2]='Barbadori'
    labeldict[3]='Bischeri'
    labeldict[4]='Castellani'
    labeldict[5]='Ginori'
    labeldict[6]='Guadagni'
    labeldict[7]='Lamberteschi'
    labeldict[8]='Medici'
    labeldict[9]='Pazzi'
    labeldict[10]='Peruzzi'
    labeldict[11]='Pucci'
    labeldict[12]='Ridolfi'
    labeldict[13]='Salviati'
    labeldict[14]='Strozzi'
    labeldict[15]='Tornabuoni'

    nx.draw(f, labels = labeldict,with_labels=True)     

Figura Famiglie
A imagem será apresentada aqui.

A primeira maneira de calcular distâncias mínimas entre nós \(i\) e \(j\) é a partir da matriz de adjacências. Em uma rede não direcionada e sem pesos, se os nós são conectados o valor do elemento \(A_{ij}\) da matriz de adjacências será \(1\), caso contrário \(0\). A distância mínima entre dois nós \(i\) e \(j\) não conectados pode ser encontrada pelo número \(k\) que a matriz é elevada até que o elemento de \((A^k)_{ij}\) fique diferente de zero. Em uma rede com \(n\) nós, \(k\) fica limitado a \(n-1\).

O código deste algoritmo é apresentado a seguir.

import numpy as np

def dist(x):
    l = len(x)
    D = np.zeros((l,l))
    matrizes = [np.empty((l,l)) for i in range(l+1)]
    #for inicial para guardar matrizes A^n
    for k in range (l+1):
        a = np.linalg.matrix_power(x, k)
        matrizes[k] = a
    #laços para cada elemento   
    for i in range(l):
        for j in range(l):
            n = 2
            # diagonal da matriz de adjacência é 0
            if i == j:
                D[i][j]=0
            # vértices já conectados
            elif x[i][j] == 1:
                D[i][j] = 1
            # demais vértices    
            else:
                while matrizes[n][i][j] == 0 and n < l :
                    n = n + 1
                D[i][j] = n
    return D

if __name__ == "__main__":
    #matriz de adjacência 
    Acciaiuoli = np.array([0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0])
    Albizzi = np.array([0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0])
    Barbadori = np.array([0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0])
    Bischeri = np.array([0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0])
    Castellani = np.array([0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0])
    Ginori = np.array([0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0])
    Guadagni = np.array([0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,1])
    Lamberteschi = np.array([0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0])
    Medici = np.array([1,1,1,0,0,0,0,0,0,0,0,0,1,1,0,1])
    Pazzi = np.array([0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0])
    Peruzzi = np.array([0,0,0,1,1,0,0,0,0,0,0,0,0,0,1,0])
    Pucci = np.array([0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0])
    Ridolfi = np.array([0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,1])
    Salviati = np.array([0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0])
    Strozzi = np.array([0,0,0,1,1,0,0,0,0,0,1,0,1,0,0,0])
    Tornabuoni = np.array([0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0]) 

    Famiglie = np.array([Acciaiuoli, Albizzi, Barbadori, Bischeri, 
                  Castellani, Ginori, Guadagni, Lamberteschi,
                  Medici, Pazzi, Peruzzi, Pucci, Ridolfi, 
                  Salviati, Strozzi, Tornabuoni])

    print(dist(Famiglie))

O segundo algoritmo é uma variação do BFS (uma busca exaustiva em grafos usado para encontrar caminhos mais curtos) que guarda não só o caminho, mas os nós percorridos nas distâncias mais curtas.

Nesta adaptação para Python do código presente no Apêndice 6 do referido livro os resultados dos nós do caminho foram suprimidos, apesar de presentes no código como preds. Em vez de matriz de adjacências, aqui usamos conjuntos de vizinhos para cada nó.

import numpy as np

def BFS(theGraph, source):
    n=len(theGraph)
    marked=np.empty(n)
    dist=np.empty(n)
    preds=[set() for i in range(n)]
    for j in range(0,n):
        dist[j]=n
        marked[j]=n+1
    dist[source]=0
    marked[0]=source
    d=0
    s=0
    nd=1
    ndp=0
    while d<n and nd>0:
        for k in range(s,s+nd):
            cur_node = int(marked[k])            
            for j in list(theGraph[cur_node]):
                if dist[j]==d+1:
                    preds[j].add(cur_node)
                if dist[j]==n:
                    dist[j]=d+1
                    preds[j].add(cur_node)
                    marked[s+nd+ndp]=j
                    ndp=ndp+1
        s=s+nd
        nd=ndp
        ndp=0
        d=d+1
    return dist, preds
if __name__ == '__main__':

    n=16 #number of nodes

    theGraph=[set() for i in range(n)]

    theGraph[0].update([8])
    theGraph[1].update([5,6,8])
    theGraph[2].update([4,8])
    theGraph[3].update([6,10,14])
    theGraph[4].update([2,10,14])
    theGraph[5].update([1])
    theGraph[6].update([1,3,7,15])
    theGraph[7].update([6])
    theGraph[8].update([0,1,2,12,13,15])
    theGraph[9].update([13])
    theGraph[10].update([3,4,14])
    theGraph[12].update([8,14,15])
    theGraph[13].update([8,9])
    theGraph[14].update([3,4,10,12])
    theGraph[15].update([6,8,12])


    [print(BFS(theGraph,i)[0]) for i in range(n)]

Ambos algoritmos apresentam os mesmos resultados. Convencionou-se aqui colocar a distância de \(n\) quando o nó não está conectado (equivalente a \(16\) na rede em questão), visto que a maior distância entre nós é de \(n-1\).

Enquanto o primeiro algoritmo tem complexidade \(O(N(NK))\), calculando todas as matrizes no pior cenário (o que efetivamente foi feito), onde \(K\) é o número de arestas e \(N\) o número de nós. Por outro lado, segundo código é mais eficiente pois apresenta complexidade de \(O(N(N+K))\) perpassando por todos nós e arestas.

Resultados de ambos:

[[ 0.  2.  2.  4.  3.  3.  3.  4.  1.  3.  4. 16.  2.  2.  3.  2.]
 [ 2.  0.  2.  2.  3.  1.  1.  2.  1.  3.  3. 16.  2.  2.  3.  2.]
 [ 2.  2.  0.  3.  1.  3.  3.  4.  1.  3.  2. 16.  2.  2.  2.  2.]
 [ 4.  2.  3.  0.  2.  3.  1.  2.  3.  5.  1. 16.  2.  4.  1.  2.]
 [ 3.  3.  1.  2.  0.  4.  3.  4.  2.  4.  1. 16.  2.  3.  1.  3.]
 [ 3.  1.  3.  3.  4.  0.  2.  3.  2.  4.  4. 16.  3.  3.  4.  3.]
 [ 3.  1.  3.  1.  3.  2.  0.  1.  2.  4.  2. 16.  2.  3.  2.  1.]
 [ 4.  2.  4.  2.  4.  3.  1.  0.  3.  5.  3. 16.  3.  4.  3.  2.]
 [ 1.  1.  1.  3.  2.  2.  2.  3.  0.  2.  3. 16.  1.  1.  2.  1.]
 [ 3.  3.  3.  5.  4.  4.  4.  5.  2.  0.  5. 16.  3.  1.  4.  3.]
 [ 4.  3.  2.  1.  1.  4.  2.  3.  3.  5.  0. 16.  2.  4.  1.  3.]
 [16. 16. 16. 16. 16. 16. 16. 16. 16. 16. 16.  0. 16. 16. 16. 16.]
 [ 2.  2.  2.  2.  2.  3.  2.  3.  1.  3.  2. 16.  0.  2.  1.  1.]
 [ 2.  2.  2.  4.  3.  3.  3.  4.  1.  1.  4. 16.  2.  0.  3.  2.]
 [ 3.  3.  2.  1.  1.  4.  2.  3.  2.  4.  1. 16.  1.  3.  0.  2.]
 [ 2.  2.  2.  2.  3.  3.  1.  2.  1.  3.  3. 16.  1.  2.  2.  0.]]

b. A segunda parte do exercício consiste em calcular medidas de centralidade de redes complexas, o que também foi realizado por meio do pacote networkx. O exemplo utilizado foi desta rede:

A imagem será apresentada aqui.

import networkx as nx

if __name__ == "__main__":
    c = nx.Graph()
    c.add_edges_from([(1,3),(1,2),(3,4),(2,4),(2,5),(4,6),(5,6),(6,7)])
    nx.draw(c, with_labels=True)
    print('Closeness e betweeness centrality do nó 1: %.2f e %.2f.' 
          % (nx.closeness_centrality(c,1), nx.betweenness_centrality(c)[1]))      
    print('\nBetweeness centrality do nó 4: %.2f.' 
          % (nx.betweenness_centrality(c)[4]))

A closeness centrality comprrende o inverso da média das menores distâncias de um nó \(u\) aos demais de certa rede. Quanto maior o seu valor, maior é a centralidade do nó.

\(C(u)=\frac{n-1}{\sum_{n-1}^{v=1}d(v,u))}\)

onde, \(d(v,u)\) é o menor caminho entre os nós \(v\) e \(u\).

Já a betweenness centrality indica a fração de menores caminhos \(\sigma (s,t)\) que passam por um nó \(v\), \(sigma (s,t|v)\). Onde \(V\) é o conjunto de nós da rede. Mais uma vez, quanto maior a medida, maior é a centralidade do nó.

\(C_{B}(v)=\sum_{s,t\epsilon V}^{}\frac{\sigma (s,t|v)}{\sigma (s,t)}\)

Resultados:

Closeness e betweeness centrality do nó 1: 0.46 e 0.06.

Betweeness centrality do nó 4: 0.37.
...