Baixe o app para aproveitar ainda mais
Leia os materiais offline, sem usar a internet. Além de vários outros recursos!
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
Compartilhar