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

Como representar um grafo?

0 votos
9 visitas
perguntada Set 12 em Ciência da Computação por Pedro Watuhã (1 ponto)  
Compartilhe

1 Resposta

0 votos
respondida Set 13 por Pedro Watuhã (1 ponto)  
 
Melhor resposta

Boa Tarde a todos,
A seguinte resposta refere-se à questão 1.6 How to represent a Graph do livro Complex Networks: Principles, Methods and Applications por Vincenzo Nicosia, Giovanni Russo, Vito Latora.

(a) Escreva a matriz de incidência e a lista de vizinhos para o grafo descrito pela matriz de adjacência no exercício 1.3.

A matriz indicada no exercício 1.3 é
\begin{bmatrix}
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 1 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0
\end{bmatrix}

e pode ser representada visualmente pelo seguinte código:

import networkx as nx
import matplotlib.pyplot as plt
G=nx.DiGraph(directed=True)
G.add_edges_from([('A','B'),('B','C'),
                  ('B','D'),('B','E'),
                  ('D','E'),('E','A')])
nx.draw(G,cmap = plt.get_cmap('jet'),with_labels=True)

A imagem será apresentada aqui.

De forma equivalente, podemos representar o grafo por uma matriz de incidência ou por uma lista de vizinhos das seguintes formas:

\begin{bmatrix}
& (A,B) & (B,C) & (B,D) & (B,E) & (D,E) & (E,A) \\
A & -1 & 0 & 0 & 0 & 0 & 1 \\
B & 1 & -1 & -1 & -1 & 0 & 0 \\
C & 0 & 1 & 0 & 0 & 0 & 0 \\
D & 0 & 0 & 1 & 0 & -1 & 0 \\
E & 0 & 0 & 0 & 1 & 1 & -1
\end{bmatrix}

graph = {"A":{"B"},
     "B":{"C","D","E"},
     "C":{},
     "D":{"E"},
     "E":{"A"}}

(b) Escreva a forma ij da matriz adjacente exposta.

\[ i = \begin{Vmatrix} A \\ B \\ B \\ B \\ D \\ E \end{Vmatrix} \]

\[ j = \begin{Vmatrix} B \\ C \\ D \\ E \\ E \\ A \end{Vmatrix} \]

(c) Considere o grafo bipartido com N=4 e V=6 correspondente à matriz A NxV abaixo e imagine que o grafo descreva como N usuários selecionaram V objetos. Suponha, então, que você quer recomendar objetos aos usuários por meio do método CF. Utilize as equações 1.1 e 1.2 para isso.

\[ (1.1) s_{ij} = \frac{\sum^V_{\alpha=1}a_{i\alpha}a_{j\alpha}}{min\{k_{ui},k_{uj}\}} \]

\[ (1.2) r_{i\alpha} = \frac{\sum_{j=1 j!=i}^{N} s_{ij}a_{j\alpha}} {\sum_{j=1 j!=i}^{N} s_{ij}}\]

\begin{Vmatrix}
1 & 0 & 1 & 0 & 0 & 1 \\
1 & 1 & 1 & 1 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 & 1 \\
0 & 0 & 1 & 1 & 1 & 0
\end{Vmatrix}

Podemos representar esse grafo da seguinte forma:

from networkx.algorithms import bipartite
B=nx.Graph()
B.add_nodes_from(["A", "B", "C", "D"], bipartite=0)
B.add_nodes_from(["a", "b", "c","d","e","f"], bipartite=1)
B.add_edges_from([("A","a"),("A","c"),("A","f"),
                  ("B","a"),("B","b"),("B","c"),("B","d"),
                  ("C","b"),("C","c"),("C","e"),("C","f"),
                  ("D","c"),("D","d"),("D","e")])
X, Y = bipartite.sets(B)
edges=B.edges()
pos = dict()
pos.update( (n, (1, i)) for i, n in enumerate(X))
pos.update( (n, (2, i)) for i, n in enumerate(Y))
nx.draw_networkx(B, pos=pos, edges=edges)

A imagem será apresentada aqui.

Para solucionar esse problema, criar-se-á uma função para calcular a matriz de similaridade e outra para realizar a recomendação.

import numpy as np
def similarity_matrix(graph):
    people = len(graph)
    objects = len(graph[1])
    S = np.ones([people,people])
    for n in range(1,people+1):
        for m in range(1,people+1):
            s=0
            for o in range(0,objects):
                s = s + graph[n][o]*graph[m][o]
            s = s/min([sum(graph[n]),sum(graph[m])])
            S[n-1,m-1] = s   
    return S

def recommendation(graph):
    S = similarity_matrix(graph)
    people = len(graph)
    objects = len(graph[1])
    R = np.ones([people,objects])
    for o in range(0,objects):
        for n in range(1,people+1):
            r=0           
            for m in range(1,people+1):
                if m!=n:
                    if graph[n][o] == 0:    #Evitaremos recomendar objetos já consumidos
                        r= r + S[n-1,m-1]*graph[m][o]
                        R[n-1,o] = r/(sum(S[n-1])-1)
                    else:
                        R[n-1,o] = 0
    return R

if __name__ == "__main__":
    graph = {1:[1,0,1,0,0,1],
             2:[1,1,1,1,0,0],
             3:[0,1,1,0,1,1],
             4:[0,0,1,1,1,0]}
    print(recommendation(graph))

A imagem será apresentada aqui.

Dessa forma, podemos observar quais objetos são mais recomendáveis aos usuários.

...