lista 2 - Comunicação e Redes - UFABC

Prévia do material em texto

Lista 2 – Comunicação e Redes 2021.1 – UFABC
Aritanan Gruber
aritanan.gruber@ufabc.edu.br
http://professor.ufabc.edu.br/∼aritanan.gruber
Questionamentos e desenvolvimento das questões juntamente com os alunos:
Pedro Holland de Oliveira
Leandro Diomar Gomes da Silva
Ana Livia Rocha Silva
Cada vértice está conectado a pelo menos n/2 outros vértices
Escolhendo quaisquer 2 vértices, ambos irão ter pelo menos 1 vizinho em comum
Então, qualquer distância mínima entre 2 vértices do grafo é de no máximo 2 arestas.
Sendo assim, o diâmetro de G é no máximo 2
2. I ♦ Centralities. Considere o grafo definido pelas lista de arestas abaixo:
(a) Esboce um desenho do grafo.
Alice = 5
Bob = 2
Carl = 3
David = 2
Ernst = 2
Frank = 3
Gail = 4
Harry = 3
Jen = 3
Irene = 3
(b)
Quantos vértices e quantas arestas existem? Qual a densidade do grafo?
No grafo existem 15 arestas e 10 vértices.
A densidade seria: 15/(10(10-1))/2 = 0,33 ou 1/3
(c) Determine o grau de cada vértice e identifique os vértices centrais.
U A B C D E F G H I J
D(U) 5 2 3 2 2 3 4 3 3 3
Temos que A (Alice) e G(Gail) são os vértices centrais do grafo
(d) Calcule a centralidade por autovetor de cada vértice e identifique os vértices centrais.
Vértice A B C D E F G H I J
Centralidade 1 0,604 0,723 0,548 0,548 0,723 0,911 0,766 0,766 0,766
Obs: na centralidade por autovetor os números estão aproximados
Os vértices centrais são Alice e Gail
(e) Calcule a centralidade por proximidade de cada vértice e identifique os vértices centrais.
Vértice A B C D E F G H I J
10/16 10/16 10/22 10/23 10/23 10/22 10/18 10/24 10/24 10/24
Proximidade 0,625 0,625 0,454 0,435 0,435 0,454 0,555 0,416 0,416 0,416
Os vértices centrais são Alice e Bob
(f) Calcule a centralidade por proximidade harmônica de cada vértice e identifique os vértices centrais.
Vértice A B C D E F G H I J
6,5/9 5,5/9 5,083/9 4,583/9 4,583/9 5,083/9 5,83/9 4,83/9 4,83/9 4,83/9
Proximidade
Harmônica
0,72 0,61 0,565 0,509 0,509 0,565 0,647 0,536 0,536 0,536
Os vértices centrais são Alice e Gail
(g) Calcule a centralidade por intermediação (betweenness) de cada vértice e identifique os vértices
centrais.
Temos que
u A B C D E F G H I J
B(u) 0,612 0,556 0,014 0 0 0,014 0,5 0 0 0
Existe somente um caminho para cada par de vértice
Os vértices centrais são Alice e Bob
(h) Calcule o coeficiente de clusterização da cada vértice e o coeficiente médio de clusterização do grafo.
u A B C D E F G H I J
D(u) 3/10
(0,3)
0 2 /3
(0,667)
1 1 2 /3
(0,667)
3 /6
(0,5)
3 /3
(1)
3 /3
(1)
3 /3
(1)
O Clustering é igual a 0,618
(i) Existe uma conspiração contra o vértice central por intermediação determinado no item (g). Se você fosse
adicionar uma única aresta no grafo de forma a reduzir a centralidade por intermediação de tal vértice, qual
seria?
Aresta {C, J} ou Aresta {D,G}
Tomando a Aresta {D,G} como exemplo, temos que a centralidade por intermediação seria
u A B C D E F G H I J
B(u) 0,338 0,148 0,050 0,296 0 0,014 0,514 0 0 0
(j) Esboce o gráfico dos graus versus coeficientes de intermediação dos vértices. Estas variáveis são
correlacionadas? Calcule o coeficiente de correlação e seu. Quais são os maiores outliers nesta relação?
Utilize a figura feita no item (a) na interpretação dos outliers.
O coeficiente mostra que existe relação entre os graus e as intermediações mas não é tão forte, o maior outlier
é o B, possível ponto de fragilidade de ambos os lados. E em segundo está a Alice pela maior concentração de
vértices
Cu = ⅓
Cv = ⅓
1/0,333 + 2/2 = 1/0,333 + 2/2