TRABALHO DE REDES Grupo 6

Prévia do material em texto

CENTRO UNIVERSITÁRIO ESTÁCIO DO RECIFE
UNIDADE SAN MARTIN
ENGENHARIA ELÉTRICA
TRABALHO DE REDES INDUSTRIAIS E SISTEMAS SUPERVISÓRIOS 
Equipe:
Anderson Cunha Gonzaga – 201301237256
André Paixão e Silva – 201301334731
Adriano Barros Vital - 201301701254
Gabriel Paim Gomes de Freitas - 201301806919
Marcelo Nonato Araújo Carneiro - 201301873004
Severino do Nascimento Júnior - 201102192317
Recife – PE
2017
Grupo 6:
Descrição do Projeto:
O presente trabalho tem como objetivo apresentar os resultados obtidos através da análise de uma Topologia em anel com 10 nós interligadados através de enlaces de 10km. 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: 
Matriz de Adjacência;
Matriz de Grau;
Matriz Laplaciana;
Matriz dos Menores Caminhos (Saltos);
Matriz dos Menores Caminhos (Distância);
Autovalores;
Conectividade Algébrica;
Raio Espectral;
Diâmetro do Grafo;
Menor Caminho Médio;
Histograma dos Menores Caminhos;
Código utilizado:
nos = 10;
 
ma = zeros(nos,nos);
for i = 1:nos
 for j = 1:nos
 ma(i,j) = ma(j,i);
 if i == j-1
 ma(i,j) = 1;
 end
 end
 if (i == 1)&& (j == nos)
 ma(i,j) = 1;
 end 
end
 
% ----- Representando o grafo:
cm = ma;
ids = [];
bg2 = biograph(cm,ids,'LayoutType','equilibrium','ShowArrow','off');
get (bg2.nodes,'ID');
view(bg2)
 
%Matriz de Grau%
 
NumConx = sum(ma,2);
Grau = diag(NumConx);
 
%Matriz Laplaciana%
 
Laplace = Grau - ma;
 
%Matriz de Menores Caminhos (Saltos)%
 
DG=sparse(ma);% 
MCS=graphallshortestpaths(DG);
 
%Matriz de Menores Caminhos (Distancia)%
 
DG=sparse(ma)*10;% 
MCD=graphallshortestpaths(DG);
 
% ----Conectividade Algébrica
autovalores = eig(Laplace);
 
% ----Conectividade Algébrica
Conectividade=autovalores(2,1);
 
% ---Raio Espectral
RaioEspectral=autovalores(10,1);
 
% ---Diâmetro do Grafo
Di=max(MCS);
DiametroGrafo=0;
for i=1:10;
 if Di(1,i)>DiametroGrafo
 DiamentroGrafo=Di(1,i);
 end
end
DiametroGrafo = DiametroGrafo;
 
%---Calculo do Menor Caminho Médio
MenorCaminhoMedio = ((10*25))/((100)-10);
 
figure
 bar(MCS)%Define as variáveis dos eixos
 title({'Histograma de Menores Caminhos'});%Dá o título a gráfico
 xlabel({'Menores Caminhos'});% Denominação do eixo X
 ylabel({'Frequência'});% Denominação do eixo Y
 
 %Gerando a matriz D:
 AB=sum(ma,2); %Soma as colunas
 D=diag(AB); %Cria uma matriz cuja a diagonal e os valores de AB, outros valores são zeros.
 
%Entropia:
 EN=0;
 BC=AB';
 for j=1:nos %Inicia um for para a linha, que vai de 1 até o valor setado "nos"
 EN=BC(1,j)*log2(BC(1,j))+EN;
 end %Fim do for
 
 
 %Mostrando as matrizes e métricas:
 disp('Matriz adjacência:');
 disp(ma);
 disp('Matriz de grau:');
 disp(Grau);
 disp('Matriz laplaciana:');
 disp(Laplace);
 disp('Autovalores:');
 disp(autovalores);
 disp('Conectividade algébrica:');
 disp(Conectividade);
 disp('Raio espectral:');
 disp(RaioEspectral);
 disp('Matriz de menores caminhos:');
 disp(MCS);
 disp('Matriz de menores caminhos:');
 disp(MCD);
 disp('Diâmetro do grafo:');
 disp(DiametroGrafo);
 disp('Menor caminho médio:');
 disp(MenorCaminhoMedio);
 disp('Entropia:');
 disp(-EN);
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. Essas conexões são estabelecidas através de enlaces (linhas pretas que interligam os nós).
Figura – Topologia em Anel
Fonte: Próprio Autor
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:
 0 1 0 0 0 0 0 0 0 1
 1 0 1 0 0 0 0 0 0 0
 0 1 0 1 0 0 0 0 0 0
 0 0 1 0 1 0 0 0 0 0
 0 0 0 1 0 1 0 0 0 0
 0 0 0 0 1 0 1 0 0 0
 0 0 0 0 0 1 0 1 0 0
 0 0 0 0 0 0 1 0 1 0
 0 0 0 0 0 0 0 1 0 1
 1 0 0 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:
 2 0 0 0 0 0 0 0 0 0
 0 2 0 0 0 0 0 0 0 0
 0 0 2 0 0 0 0 0 0 0
 0 0 0 2 0 0 0 0 0 0
 0 0 0 0 2 0 0 0 0 0
 0 0 0 0 0 2 0 0 0 0
 0 0 0 0 0 0 2 0 0 0
 0 0 0 0 0 0 0 2 0 0
 0 0 0 0 0 0 0 0 2 0
 0 0 0 0 0 0 0 0 0 2
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:
 2 -1 0 0 0 0 0 0 0 -1
 -1 2 -1 0 0 0 0 0 0 0
 0 -1 2 -1 0 0 0 0 0 0
 0 0 -1 2 -1 0 0 0 0 0
 0 0 0 -1 2 -1 0 0 0 0
 0 0 0 0 -1 2 -1 0 0 0
 0 0 0 0 0 -1 2 -1 0 0
 0 0 0 0 0 0 -1 2 -1 0
 0 0 0 0 0 0 0 -1 2 -1
 -1 0 0 0 0 0 0 0 -1 2
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 (SALTOS):
0 1 2 3 4 5 4 3 2 1
1 0 1 2 3 4 5 4 3 2
2 1 0 1 2 3 4 5 4 3
3 2 1 0 1 2 3 4 5 4
4 3 2 1 0 1 2 3 4 5
5 4 3 2 1 0 1 2 3 4
4 5 4 3 2 1 0 1 2 3
3 4 5 4 3 2 1 0 1 2
2 3 4 5 4 3 2 1 0 1
1 2 3 4 5 4 3 2 1 0
A Matriz de Menores Caminhos estabelece a distância que é necessário para que um nó se conecte a outro nó. 
Matriz de menores caminhos em km:
 0 10 20 30 40 50 40 30 20 10
 10 0 10 20 30 40 50 40 30 20
 20 10 0 10 20 30 40 50 40 30
 30 20 10 0 10 20 30 40 50 40
 40 30 20 10 0 10 20 30 40 50
 50 40 30 20 10 0 10 20 30 40
 40 50 40 30 20 10 0 10 20 30
 30 40 50 40 30 20 10 0 10 20
 20 30 40 50 40 30 20 10 0 10
 10 20 30 40 50 40 30 20 10 0
Os Autovalores são calculados a partirda 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
 0.3820
 0.3820
 1.3820
 1.3820
 2.6180
 2.6180
 3.6180
 3.6180
 4.0000
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:
 0.3820
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:
 4
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:
 0
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:
 2.7778
No histograma de menores caminhos pode-se analisar a frequências que os nós apresentam conexões em relação ao demais nós da malha pelo menor caminho de saltos e distância.
Figura: Histograma de Menores Caminhos
Fonte: Próprio Autor