BC0506 - Comunicação e Redes

Propriedades Estruturais de Grafos

(Parte 1)

Prof. Vladi
Baseados nos slides dos professores de CR
Jesús, Fabrício, Carlos K.
I. Coeficiente de Clusterização/Agrupamento
(também conhecido como transitividade)
Coeficiente de Clusterização

Granovetter, nos anos 60, mostrou que as pessoas que

mudaram de emprego ficaram sabendo dele através de suas
listas de contatos pessoais.

Olhando para as conexões formadas entre essas pessoas,

notou-se que se A é conhecido de B, e B é conhecido de C,
em algum momento A e C irão se encontrar.
Coeficiente de Clusterização

Esse vínculo que forma A e C, poderá ocorrer com diversas

outras pessoas. Assim, quanto mais conhecidos duas
pessoas tenham em comum, maior a chance de estas se
tornarem conhecidas.

Esse princípio é conhecido como Fechamento triádico, ou

triangulação.
Coeficiente de Clusterização

Assim, uma característica importante de um grafo é sua

correlação das arestas ao redor de um vértice.

Formalmente, considere um vértice que está relacionado a

outro dois.

Quais as chances destes dois também estarem relacionados?

Coeficiente de Clusterização

Assim, uma característica importante de um grafo é sua

correlação das arestas ao redor de um vértice.

Formalmente, considere um vértice que está relacionado a

outro dois.

Quais as chances destes dois também estarem relacionados?

O Coeficiente de Clusterização (agrupamento) captura esta ideia
Coeficiente de Clusterização

Formalmente, considere um vértice que está relacionado a

outro dois.
Quais as chances destes dois também estarem relacionados?
O Coeficiente de Clusterização (agrupamento) captura esta ideia

Esse valor nos indica qual a probabilidade de, ao escolher dois

vizinhos de um certo vértice, eles estarem interligados.
Ou, a probabilidade da existência de triângulos nessa rede.
Coeficiente de Clusterização Local

O Coef. de clusterização do vértice i é a fração de arestas

que os vizinhos de i possuem entre si e o máximo entre
arestas que eles poderiam possuir entre si.

Seja 𝑬𝒊 o número efetivo de arestas entre os vizinhos do

vértice i.
Dado que o grau do vértice i é 𝑑𝑖 , o maior número de arestas
𝑑
entre seus vizinhos é 𝑖 = di ∗ di − 1 ou di ∗ di − 1 / 2
2
Ou seja, todos os pares de vizinhos de i possuem aresta
entre si.
𝑬𝒊
Coeficiente de Clusterização = 𝒅𝒊
𝟐
Coeficiente de Clusterização Local

CC = 3/3 = 1 CC = 1/3 = 0,33 CC = 0/3 = 0

Coeficiente de Clusterização Local

CC = 1/3 = 0,33 CC = 3/3 = 1

CC = 0/15 = 0 CC = 5/15 = 0,33

Coeficiente de Clusterização Local

Exercício: Calcule o coeficiente de clusterização de cada

vértice.
2 ∗ 𝐸𝑖
𝐶𝐶 =
𝑑𝑖 ∗ (𝑑𝑖 − 1)
Coeficiente de Clusterização do Grafo

CC do Grafo (ou Global) 2 ∗ 𝐸𝑖

𝐶𝐶 =
𝑑𝑖 ∗ (𝑑𝑖 − 1)

O CC não está definido

para vértices com grau
zero ou um.
Normalmente o CC nesses
casos é zero.

O CC global é a média
aritmética dos CC de cada
vértice:
1/10*(4,97) = 0,497
Coeficiente de Clusterização do Grafo

Ordem = 236
Tamanho = 336

CC global 0,304
Coeficiente de Clusterização do Grafo

Ordem = 50
Tamanho = 119

CC global 0,723
Coeficiente de Clusterização do Grafo

Vértice com baixa

clusterização pois
existem poucas
arestas entre seus
muitos vizinhos
Coeficiente de Clusterização do Grafo

O CC mede o grau (forma) com que os nós de um grafo

tendem a agrupar-se.

Nas redes sociais:

Em 2012, o coeficiente de agrupamento no Facebook era de

0,27. Ou seja, existe uma chance de 30% de dois amigos de
alguém também serem amigos.

Visto de outra maneira, existe uma chance de 70% de

conhecer alguém novo através de um amigo.
Coeficiente de Clusterização do Grafo

O CC mede o grau (forma) com que os nós de um grafo

tendem a agrupar-se.

Nas redes tecnológicas:

Em 2010, o coeficiente de agrupamento de transmissão de

energia da parte lestes dos Estados Unidos era de 0,07.
Reflete a ideia de que não são necessárias tantas conexões
para transportar a energia (grafo esparso).
Coeficiente de Clusterização do Grafo

O CC mede o grau (forma) com que os nós de um grafo

tendem a agrupar-se.

Nas redes de informação (autoria):

Em 2014, o coeficiente de agrupamento de co-autoria na

área de saúde no Brasil era de 0,24. Reflete a medida obtida
na rede social do Facebook.
II. Densidade do Grafo
Densidade do Grafo

É a fração de arestas que o grafo possui se comparado com

um grafo completo.

Considere um grafo de ordem n, e tamanho m.

O maior número de arestas que o grafo poderia ter é:
n*(n-1)/2.

ρ = m / [n*(n-1)/2]
ρ = 2*m / [n*(n-1)]
Densidade do Grafo

 ρ = 2*m/n(n-1)

 n=10
 m= 11
 ρ = 0,244
Densidade do Grafo

 ρ = 2*m/n(n-1)

 n=236
 m= 336
 ρ = 0,012
Densidade do Grafo

 ρ = 2*m/n(n-1)

 n=20
 m=8
 ρ = 0,042
Densidade do Grafo

 ρ = 2*m/n(n-1)

 n=20
 m=16
 ρ = 0,084
Densidade do Grafo

 ρ = 2*m/n(n-1)

 n=20
 m=27
 ρ = 0,142
Densidade do Grafo

 ρ = 2*m/n(n-1)

 n=20
 m=70
 ρ = 0,368
Densidade do Grafo

 ρ = 2*m/n(n-1)

 n=20
 m=154
 ρ = 0,811
Densidade do Grafo

 ρ = 2*m/n(n-1)

 n=20
 m=190
 ρ=1
III. Distribuição de grau
Distribuição de Grau

A distribuição empírica de grau é a fração de vértices do

grafo que possui determinado grau.

Seja nk o número de vértices com grau igual a k.

A fração de vértices com grau k é dada por:

Distribuição de Grau

*1/10
Distribuição de Grau

*1/10
Distribuição Complementar Cumulativa

A Distribuição Complementar Cumulativa (CCDF) do grau

é a fração de vértices que tem grau maior ou igual a k.
geralmente é usado no eixo Y

Para calcular esse valor, somamos todos os graus

menores do que k e obtemos o complemento.

𝑛𝑖
𝑓𝑖 =
𝑛
 Distribuição Complementar Cumulativa

𝑛𝑖
𝑓𝑖 =
𝑛

*1/10
k Fk
k=0 1-(0) 1
k=1 1-(0+3/10) 0,7
k=2 1-(0+3/10+0) 0,7
k=3 1-(0+3/10+0+2/10) 0,5
k=4 1-(0+3/10+0+2/10+3/10) 0,2
k=5 1-(0+3/10+0+2/10+3/10+1/10) 0,1
k=6 1-(0+3/10+0+2/10+3/10+1/10+1/10) 0
 Distribuição Complementar Cumulativa

*1/10

Fk
 Distribuição Complementar Cumulativa

*1/10

Fk
Distribuição Complementar Cumulativa

3.651.512 documentos
(vértices)

80.737.121 hiperlinks
(arestas direcionadas).

Distribuição CCDF do grau de entrada e saída do Wikipedia (em inglês obtida em 2011),
Distribuição Complementar Cumulativa

3.651.512 documentos
(vértices)

80.737.121 hiperlinks
(arestas direcionadas).

Prob. de ter páginas com

poucos links é alta

Ou seja, a maioria das

páginas apontam (ou são
apontadas) poucas vezes.
Pense no seu site.

Distribuição CCDF do grau de entrada e saída do Wikipedia (em inglês obtida em 2011)
Distribuição Complementar Cumulativa

3.651.512 documentos
(vértices)

80.737.121 hiperlinks
(arestas direcionadas).

Prob. de ter páginas com

muitos links é baixa

Ou seja, poucas páginas

apontam (ou são
apontadas) muitas vezes.
Pense no site da UOL.

Distribuição CCDF do grau de entrada e saída do Wikipedia (em inglês obtida em 2011)
Distribuição Complementar Cumulativa

3.651.512 documentos
(vértices)

80.737.121 hiperlinks
(arestas direcionadas).

Grau médio 22,1.

relativamente baixo
comparado com a faixa de
valores (eixo x)

Distribuição CCDF do grau de entrada e saída do Wikipedia (em inglês obtida em 2011)
Distribuição Complementar Cumulativa

3.651.512 documentos
(vértices)

80.737.121 hiperlinks
(arestas direcionadas).

Distribuições distintas:
Entrada → atinge valores maiores
Saída → atinge valores menores

Apesar de ambas terem a mesma

media 22,1

Distribuição CCDF do grau de entrada e saída do Wikipedia (em inglês obtida em 2011)
Distribuição Complementar Cumulativa

3.651.512 documentos
(vértices)

80.737.121 hiperlinks
(arestas direcionadas).

A cauda da distribuição de entrada

é mais pesada do que a de saída

Distribuição CCDF do grau de entrada e saída do Wikipedia (em inglês obtida em 2011)
Distribuição Complementar Cumulativa
Referências

Para mais informações sobre as propriedades:

https://pt.wikipedia.org/wiki/Coeficiente_de_agrupamento

https://mathinsight.org/degree_distribution