MODELO TRABALHO REDES Estacio

Prévia do material em texto

Descrição do Projeto:
O presente trabalho tem como objetivo apresentar os resultados obtidos através da análise de uma rede com 20 nós. Para isso, foi utilizado o software Matlab e gerado um programa em que a partir de uma entrada com número de nós desejado para a rede, fosse calculado automaticamente os seguintes dados: 
Diagrama de Grafos na Rede;
Matriz de Adjacência;
Matriz de Grau;
Matriz Laplaciana;
Autovalores;
Conectividade Algébrica;
Raio Espectral;
Matriz dos Menores Caminhos;
Diâmetro do Grafo;
Menor Caminho Médio;
Entropia;
Coeficiente de Clusterização;
Coeficiente de Agrupamento.
Código utilizado:
%Trabalho de ciência das redes.
%Alunos: Eros Girão e Ewerton Figueiroa.
 
clear
 
%Solicitando o número de nós do grafo:
nos=input('Digite a quantidade de nós do grafo a ser gerado:');
 
%Gerando a matriz adjacência de um grafo:
A= [round(rand(nos)); 
for i=1:nos
 for j=1:nos
 A(i,j)=A(j,i);
 if i==j
 A(i,j)=0;
 end
 end
end
 
%Representando o grafo:
cm = A; 
ids = [];
bg2 = biograph(cm,ids,'LayoutType','equilibrium','ShowArrows','off');
get(bg2.nodes,'ID')
view(bg2)
 
%Menores caminhos do grafo:
DG=sparse(cm);
MC=graphallshortestpaths(DG,'directed',false);
 
%Diâmetro do grafo:
Di=max(MC);
Diametro=0;
for i=1:nos;
 if Di(1,i)>Diametro
 Diametro=Di(1,i);
 end
end
 
%Histograma de menores caminhos:
z=1:Diametro;
[bincounts] = histc(MC,z);
y=bincounts';
w=sum(y);
figure
bar(z,w)
title({'Histograma de menores caminhos'});
xlabel({'Menores caminhos'});
ylabel({'Frequência'});
 
%Menor caminho médio:
Le=mean(MC);
mcm=mean(Le);
 
%Gerando a matriz D:
AB=sum(A,2);
D=diag(AB);
 
%Calculando a matriz Laplaceana:
L=D-A;
 
%Conectividade algébrica:
autov=eig(L);
CA=autov(2,1);
 
%Histograma de autovalores:
figure
bar(autov)
title({'Histograma de autovalores'});
xlabel({'Sequência de autovalores'});
ylabel({'Autovalor'});
 
%Raio espectral:
Ra=autov(nos,1);
 
%Entropia:
EN=0;
BC=AB';
for j=1:nos
 EN=BC(1,j)*log2(BC(1,j))+EN;
end
 
%Coeficiente de clusterização global:
CC=clustercoeffs(A);
 
%Coeficiente de agrupamento:
CG=sum(CC)/nos;
 
%Mostrando as matrizes e métricas:
disp('Matriz adjacência:');
disp(A);
disp('Matriz de grau:');
disp(D);
disp('Matriz laplaceana:');
disp(L);
disp('Autovalores:');
disp(autov);
disp('Conectividade algébrica:');
disp(CA);
disp('Raio espectral:');
disp(Ra);
disp('Matriz de menores caminhos:');
disp(MC);
disp('Diâmetro do grafo:');
disp(Diametro);
disp('Menor caminho médio:');
disp(mcm);
disp('Entropia:');
disp(-EN);
disp('Coeficiente de clusterização global:');
disp(CC);
disp('Coeficiente de agrupamento:');
disp(CG);
Resultados Obtidos:
A Figura abaixo representa o diagrama de grafos, onde é possível verificar de forma visual a conexão entre os nós (quadrados em amarelo), com os outros nós na rede. Essa conexões são estabelecidas através de enlaces (linhas pretas que interligam os nós).
Figura 1: Diagrama de Rede
A Matriz de Adjacência representa se existe uma conexão estabelecida entre dois nós na rede. São testados se existe conexão estabelecida entre os nós e determinado o número 1 caso os nós estejam conectados. Em caso negativo atribuísse o número 0.
Matriz adjacência (A):
 0 1 0 1 1 0 0 1 1 1 0 1 1 0 1 0 0 1 1 1
 1 0 1 1 1 1 1 0 1 0 1 0 0 0 0 1 1 0 1 0
 0 1 0 1 0 0 0 1 1 1 0 1 1 0 0 0 1 0 1 0
 1 1 1 0 1 1 1 0 0 0 1 0 1 0 1 0 0 0 1 0
 1 1 0 1 0 0 1 1 0 1 0 0 1 1 1 0 1 0 0 0
 0 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0
 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 1 0
 1 0 1 0 1 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0
 1 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 1 0
 1 0 1 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1
 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0
 1 0 1 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 1
 1 0 1 1 1 0 0 1 1 0 0 1 0 0 0 1 1 0 0 1
 0 0 0 0 1 1 0 1 0 0 0 1 0 0 1 1 1 0 1 0
 1 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 1 1 1 0
 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0
 0 1 1 0 1 1 1 0 1 1 0 0 1 1 1 0 0 0 0 0
 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 0 0 1 0
 1 1 1 1 0 0 1 0 1 1 0 0 0 1 1 0 0 1 0 1
 1 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0
A Matriz de Grau representa o quão conectado é um nó na rede. Ele pode ser representado como um vetor inserido na diagonal principal de uma matriz em que o número na diagonal principal mostra o número de conexões com nós diferentes na rede.
Matriz de grau (G):
 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 11 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5
A Matriz Laplaciana é obtida a partir da subtração da Matriz de Grau pela Matriz de Adjacência (L=G-A). Essa Matriz é importante para calcular os autovalores e outras métricas importante para o estudo da rede.
Matriz laplaciana (L):
 12 -1 0 -1 -1 0 0 -1 -1 -1 0 -1 -1 0 -1 0 0 -1 -1 -1
 -1 11 -1 -1 -1 -1 -1 0 -1 0 -1 0 0 0 0 -1 -1 0 -1 0
 0 -1 9 -1 0 0 0 -1 -1 -1 0 -1 -1 0 0 0 -1 0 -1 0
 -1 -1 -1 10 -1 -1 -1 0 0 0 -1 0 -1 0 -1 0 0 0 -1 0
 -1 -1 0 -1 10 0 -1 -1 0 -1 0 0 -1 -1 -1 0 -1 0 0 0
 0 -1 0 -1 0 9 0 -1 -1 -1 0 0 0 -1 0 -1 -1 -1 0 0
 0 -1 0 -1 -1 0 8 0 0 -1 0 -1 0 0 0 0 -1 -1 -1 0
 -1 0 -1 0 -1 -1 0 7 0 0 0 0 -1 -1 0 0 0 -1 0 0
 -1 -1 -1 0 0 -1 0 0 8 0 0 0 -1 0 0 0 -1 -1 -1 0
 -1 0 -1 0 -1 -1 -1 0 0 11 -1 -1 0 0 0 0 -1 -1 -1 -1
 0 -1 0 -1 0 0 0 0 0 -1 4 0 0 0 -1 0 0 0 0 0
 -1 0 -1 0 0 0 -1 0 0 -1 0 7 -1 -1 0 0 0 0 0 -1
 -1 0 -1 -1 -1 0 0 -1 -1 0 0 -1 10 0 0 -1 -1 0 0 -1
 0 0 0 0 -1 -1 0 -1 0 0 0 -1 0 8 -1 -1 -1 0 -1 0
 -1 0 0 -1 -1 0 0 0 0 0 -1 0 0 -1 8 0 -1 -1 -1 0
 0 -1 0 0 0 -1 0 0 0 0 0 0 -1 -1 0 5 0 -1 0 0
 0 -1 -1 0 -1 -1 -1 0 -1 -1 0 0 -1 -1 -1 0 10 0 0 0
 -1 0 0 0 0 -1 -1 -1 -1 -1 0 0 0 0 -1 -1 0 9 -1 0
 -1 -1 -1 -1 0 0 -1 0 -1 -1 0 0 0 -1 -1 0 0 -1 11 -1
 -1 0 0 0 0 0 0 0 0 -1 0 -1 -1 0 0 0 0 0 -1 5
Os Autovalores são calculados a partir da Matriz Laplaciana e indicam o quão fácil é separar a rede. Como propriedade sempre o primeiro autovalor possui o valor 0. A partir disso, o segundo autovalor significa a facilidade de separar a rede em duas redes independentes ou comunidades independentes. 
Autovalores:
 0.0000
 3.5592
 4.0485
 5.0695
 6.3945
 6.5664
 6.8286
 7.5778
 7.9761
 8.2688
 9.3476
 9.5563
 9.7519
 10.6801
 11.0454
 12.0988
 12.2370
 13.0021
 13.5562
 14.4352
A conectividade Algébrica representa o valor do segundo autovalor e índica o grau de conectividade na rede. Chamamos de conectividade algébrica o segundo menor autovalor da matriz laplaciana de um grafo. Esse autovalor é uma medida de compacidade do grafo: quando grande indica um grafo compactado, enquanto pequeno indica estrutura alongada.
Conectividade algébrica:
 3.5592
O Raio Espectral é o maior dos autovalores da Matriz Laplaciana e índica o raio do intervalo de centro na origem que contém todos os autovalores de G.
Raio espectral:
 14.4352
A Matriz de Menores Caminhos estabelece quantos saltos são necessários para que um nó se conecte a outro nó. 
Matriz de menores caminhos:
 0 1 2 1 1 2 2 1 1 1 2 1 1 2 1 2 2 1 1 1
 1 0 1 1 1 1 1 2 1 2 1 2 2 2 2 1 1 2 1 2
 2 1 0 1 2 2 2 1 1 1 2 1 1 2 2 2 1 2 1 2
 1 1 1 0 1 1 1 2 2 2 1 2 1 2 1 2 2 2 1 2
 1 1 2 1 0 2 1 1 2 1 2 2 1 1 1 2 1 2 2 2
 2 1 2 1 2 0 2 1 1 1 2 2 2 1 2 1 1 1 2 2
 2 1 2 1 1 2 0 2 2 1 2 1 2 2 2 2 1 1 1 2
 1 2 1 2 1 1 2 0 2 2 3 2 1 1 2 2 2 1 2 2
 1 1 1 2 2 1 2 2 0 2 2 2 1 2 2 2 1 1 1 2
 1 2 1 2 1 1 1 2 2 0 1 1 2 2 2 2 1 1 1 1
 2 1 2 1 2 2 2 3 2 1 0 2 2 2 1 2 2 2 2 2
 1 2 1 2 2 2 1 2 2 1 2 0 1 1 2 2 2 2 2 1
 1 2 1 1 1 2 2 1 1 2 2 1 0 2 2 1 1 2 2 1
 2 2 2 2 1 1 2 1 2 2 2 1 2 0 1 1 1 2 1 2
 1 2 2 1 1 2 2 2 2 2 1 2 2 1 0 2 1 1 1 2
 2 1 2 2 2 1 2 2 2 2 2 2 1 1 2 0 2 1 2 2
 2 1 1 2 1 1 1 2 1 1 2 2 1 1 1 2 0 2 2 2
 1 2 2 2 2 1 1 1 1 1 2 2 2 2 1 1 2 0 1 2
 1 1 1 1 2 2 1 2 1 1 2 2 2 1 1 2 2 1 0 1
 1 2 2 2 2 2 2 2 2 1 2 1 1 2 2 2 2 2 1 0
O diâmetro do grafo é o maior dos menores caminhos e mostra qual o máximo número de saltos para conectar dois nós na rede.
Diâmetro do grafo:
 3
O menor caminho médio é a soma de todos os caminhos na rede, calculados partir da matriz de caminho médio e dividido pelo número de conexões.
Menor caminho médio:
 1.4750
A entropia calcula a desordem no grafo.
Entropia:
 -542.1681
Coeficiente de clusterização global:
 0.4242
 0.4000
 0.4167
 0.4222
 0.4667
 0.3611
 0.4643
 0.3810
 0.5357
 0.3455
 0.3333
 0.3810
 0.3556
 0.2857
 0.4286
 0.3000
 0.4222
 0.3889
 0.4182
 0.7000
Coeficiente de agrupamento:
 0.4115
Figura 2: Histograma de Menores Caminhos
Figura 3: Histograma de Autovalores