Redes Complexas

Renato VicenteComplex Systems EACH USP

Grafos

Grafos são definidos por seus vértices e arestas G=(V,E).

Para o grafo G acima: V={u,v,w,x,y} e E={a,b,c,d,e,f,g,h}.

As arestas conectam dois vértices adjacentes. O número de

vértices v(G)=5 é a ordem do grafo. O número de arestas

e(G)=8 é o tamanho do grafo.

Grafos

Se todos os vértices são adjacentes o grafo é completo (a).

Se o conjunto de vértices puder ser dividido em duas partes de forma que

cada aresta iniciando em uma parte termine na outra parte o grafo é bipartite

(b).

Se o gráfico é bipartite e cada vértice em uma parte é adjacente a cada

vértice na outra parte o grafo é bipartite completo . Uma estrela é um grafo

bipartite completo com um elemento apenas em uma de suas partes (c).

Grafos

Num caminho (a) dois vértices são adjacentes se estão em sequência.

Um caminho fechado é um ciclo (b).

O comprimento de um caminho é o número de arestas entre os dois

vértices extremos ou, no caso do ciclo, o número de arestas até que o

vértice se repita.

Grafos

Um grafo é conexo se para qualquer partição de seus vértices em dois

conjuntos existe uma aresta com um final em um conjunto e o outro no outro

conjunto (a), caso contrário, o grafo é disconexo (b).

Grafos

Um grafo pode ser representado por sua matriz de incidência M, listando os

pares de vértices e arestas que são conectados.

Outra opção é representar o grafo por sua matriz de adjacência A, listando

vértices adjacentes.

Grafos

Dois grafos são isomórficos se a matriz de adjacência puder ser feita

idêntica através de um mapeamento de vértices. Por exemplo, no grafo

acima:

Grafos

Um grafo infinito é uma rede. Acima, da esquerda para a direita: rede

quadrada, rede triangular e rede hexagonal.

Digrafos

Um grafo dirigido ou digrafo é especificado pelo par G=(V,A), onde V é o

conjunto de vértices e A é o conjunto de pares ordenados denominados

arcos.

Orientações de um grafo completo como o da figura acima são denominadas

torneios.

Medidas de Centralidade

Qual é a importância de um dado vértice?

• Centralidade de grau• Betweenness• Closeness• Autovetor

Centralidade de grau

Percentual de vértices do grafo que estão conectados ao vértice em questão. Se o grafo é dirigido definem-se duas centralidades de grau: de saída e de entrada.

No grafo acima o vértice v=11 tem centralidade de grau de entrada e . (11) 2in

DC (11) 3out

DC

Centralidade de grau

A centralidade de grau pode ser medida para um grafo inteiro definindo

Aqui v* representa o vértice com maior centralidade de grau. A centralidade máxima é igual a 1 e é atingida quando o grafo é uma estrela. Um grafo regular tem centralidade 0. O grafo acima tem centralidade igual a 0.5

Centralidade de betweenness

Um vértice que ocorre em muitos caminhos mais curtos entre outros dois vértices tem maior betweenness.

Aqui σst(v) é o número de caminhos mais curtos começando em s e terminando em t que passam por v. σst

é o número total de caminhos mais curtos entre s e t. Na figura os vértices em azul tem maior centralidade de betweenness seguidos pelos em verde, amarelo, laranja e vermelho.

Centralidade de closeness(proximidade)

A centralidade de closeness mede a distância geodésica (menor distância) média entre um vértice os outros vértices do grafo.

Neste caso quanto maior a centralidade maior a distância média dos outros vértices em relação ao vértice em consideração. Uma alternativa mais consistente é

Neste caso quanto menor a distância média maior a centralidade de proximidade.

Centralidade de closeness(proximidade)

A centralidade de closeness mede a distância geodésica (menor distância) média entre um vértice os outros vértices do grafo.

Centralidade de autovalor

A centralidade de autovalor (e.g. PageRank do Google) mede a importância de um vértice na rede considerando cada aresta como um voto. Os votos são ponderados pelo número de votos recebidos por cada vértice adjacente. Vértices mais votados tendo peso proporcional a seu número de votos. Se representar o score do vértice i teremos:

ix

Centralidade de autovalor

Authors: Shamma, D.A.; Kennedy, L.; Churchill, E.F.

Source: ACM Multimedia, ACM, Beijing, China (2009)

A centralidade de autovalor do twitter de Obama é maior que a de McCain pois é citado por usuários mais citados.

Assortividade

O coeficiente de assortatividade é a correlação entre graus de vértices adjacentes.

Assortividade

Coeficiente de ClusteringO coeficiente de clustering de um vértice é a razão entre as arestas existentes e as arestas possíveis entre vizinhos de um dado vértice. Para digrafos temos:

Para grafos não dirigidos:

O coeficiente de clustering do grafo é a média dos coeficientes locais

Redes de Mundo Pequeno

Coeficiente de Clustering

Distribuição de graus: Redes Livre de Escala

Distribuição de graus

Conexão Preferencial

http://ccl.northwestern.edu/netlogo/models/PreferentialAttachment

Comunidades

Comunidades