View
2
Download
0
Category
Preview:
Citation preview
AlbertoBuenoJúnior
Orientação: Prof. Daniel Batista
Exemplos do mundo real
WWW
Internet
Células
LinguísticaDistribuição de Energia Elétrica
Ligações Telefonicas
Relacionamentos
Redes Estruturadas
Redes Aleatórias
Fonte: http://www-news.uchicago.edu/releases/06/images/060807.networks-1.jpg
Redes Complexas
Estrutura&
Aleatoriedade
Redes Complexas
E a evolução da rede?
Algoritmo + Simulador
Grafos
Distribuição do grau
Probabilidade de um nó aleatório ter grau igual a k
P(k) =
Redes Livres de Escala
Fonte: http://plus.maths.org/content/network-news
P(k) = ak-y
Redes Livres de Escala
Fonte: http://upload.wikimedia.org/wikipedia/commons/7/77/Scale-free_network_sample.png
Aplicações de RLE
Computação
Medicina
Economia
PreferentialAttachment
Fonte: http://andysacker.com/how-to-increase-your-reach-and-build-a-network-of-followers/
Modelo Barabàsi-Albert
Inicio:m0 > 2 nós iniciais, com grau >= 1
Passo:Novo nó: m <= m0 conexões
∑
ki π (ki) = kj j
Modelo Barabàsi-Albert
Fim (t passos):N = t + m0 nós
m.t novas arestas
P(k) = k-3
Fonte: http://graphstream-project.org/doc/Generators/Overview-of-generators_1.0/
neteVolve (algoritmo)Extensão do Modelo BA -> Atributos
A: Conjunto de atributos ap, com domínio D(ap)
αp: Peso relativo do atributo ap. (∈ [0, 1] e ∑ αp = 1)
A(i, p): Valor do atributo ap para o nó i. (∈ D(ap)).
m(i, j, p): Valor de similaridade entre os nós i e j para o atributo p:
○ αp, se A(i, p) = A(j, p).○ 0, caso contrário.
neteVolve (algoritmo)Atração Inicial
I(i, j): Atração inicial entre os nós i e j (∈ [0, 1]):
∑ m(i, j, p)
P(i): Valor do π(ki) do modelo de Barabàsi-Albert
C: Fator de “Correção” (importância dos atributos)
p
π(i, j) = min( I(i, j) . C + P(i), 1)
neteVolve (sistema)
Implementação do Algoritmo
Resultados
C = 0 M = 1 300 Nós
Resultados
C = 0.5 M = 1 300 Nós
Resultados
C = 1 M = 1 300 Nós
Estudo de Caso
Estudo de Caso
Evolução
Fonte: Wikipedia
Humphry Davy
/albertobuenojr
abueno@linux.ime.usp.br
Eu :)
Recommended