Definição de redes

Prévia do material em texto

Modelos de Redes 
 
Definição de redes: 
 
Uma rede consiste em um conjunto de nós conectados por arcos (ou ramos). Associados 
com cada rede está um fluxo de tráfego de automóveis em rodovias). Em geral, o fluxo de 
rede é limitado pela capacidade de seus arcos, que pode ser finita ou infinita. 
Representação: (N, A), na qual N é o conjunto de nós e A é o conjunto de arcos. 
 
- Um arco é orientado ou dirigido se ele permitir fluxo positivo em uma direção e fluxo 
zero na direção oposta. Uma rede orientada é aquela na qual todos os arcos são orientados. 
- Um Caminho é uma sequência de arcos distintos que ligam dois nós passando por outros 
nos, independentemente da direção de fluxo em cada arco. 
- Um caminho forma um ciclo ou um loop se conectar um nó a si mesmo, passando por 
outros nós. 
- Uma rede conectada é uma rede tal que todos os pares de nós estão ligados por no 
mínimo um caminho. 
- Uma árvore é uma rede conectada sem ciclos formada por um subconjunto de todos os 
nós, e uma árvore geradora é uma arvore que liga todos os nós da rede. 
 
Notação: 
“Um grafo é representado como um conjunto de pontos (vértices) ligados por retas (as 
arestas). Dependendo da aplicação, as arestas podem ser direcionadas, sendo então 
representadas por "setas". 
Árvore de cobertura mínima 
O problema do caminho mínimo determina o caminho mais curto entre um destino e uma 
origem em uma rede de transporte. 
 
Aplicações de “árvore de cobertura mínima” 
- Arquitetura de redes: de transporte – estradas; de comunicação (telefonia, computação) 
- Elétricas, hidráulicas, transporte de líquidos Finanças – mercado de ações Biologia - 
análise genética 
 
Conceitos básicos de modelagem 
Nada no mundo real é um sistema, uma rede, ou um problema de Pesquisa operacional. 
Nós é que optamos por interpretar a realidade através destas representações 
 
Para que se constroem e usam modelos? 
Um modelo é uma representação da realidade projetado para algum propósito definido. 
Um modelo é uma representação externa e explícita de parte da realidade vista pela pessoa 
que deseja usar aquele modelo para entender, mudar, gerenciar e controlar parte daquela 
realidade. 
Tipos de modelos 
Modelos Físicos 
1. Icônicos – reproduzem imagem (simplificada) da realidade 
 
Ex: Fotografia, planta, maquete, etc. 
 
Analógicos – construir um outro sistema concreto que é similar ao fenômeno em estudo 
sob alguns aspectos 
 
Ex: Sistema hidráulico como representação de uma situação de transporte ou problema 
econômico 
 
Modelos Simbólicos. 
 
Modelos Descritivos (permitem simulação) 
Modelos Explanatórios (representam relações causais) 
 
Porque construir um modelo simbólico (matemático) de um problema real? 
 
1.Facilita a experimentação – há vantagens de custo de experimentar 
- Tempo para realizar o experimento e analisar os resultados 
- Experimentar sobre um modelo reduz 
- O risco para o ambiente 
- Problemas de legalidade 
- Facilita a replicação 
 
2. Para facilitar a comunicação entre pessoas 
De acordo com a teoria de comunicação de Habermas, a comunicação entre pessoas pode 
ser: 
1. Instrumental – para transmitir instruções (não contestadas) 
2. Estratégica – visando a vantagem de uma das partes (conflito possível) 
3. Comunicacional 
» Para transmitir conhecimento e 
» Busca conjunta de novo conhecimento, 
»Exploração de possibilidades 
 
O Problema de Fluxo máximo 
 
Serve para determinara a capacidade máxima de uma rede que possua um fluxo. 
 
Enumeração de cortes: Um corte define um conjunto de arcos que, quando eliminado de 
rede, causará um rompimento total do fluxo entre o nó de origem e o nó sorvedouro. 
 
Método de caminho crítico 
Foi desenvolvido para auxiliar no planejamento, na programação e no controle de projetos. 
 
Representação em redes 
Cada atividade do projeto é representada por um arco que aponta na direção do 
desenvolvimento em um projeto. Os nós da rede estabelecem as relações de procedência 
entre as diferentes atividades. 
 
Há três regras simples para construir uma rede. 
1 – Cada atividade é representada por um, e somente um, arco. 
2 – Cada atividade deve ser identificada por dois nós finais distintos 
3 – Para manter as relações corretas de precedência, é preciso responde às seguintes 
perguntas quando cada atividade for adicionada a rede: 
A – Quais atividades deve preceder imediatamente a atividade atual? 
B – Quais atividades devem vir após a atividade atual? 
C – Quais atividades devem ocorrer concorrentemente com atividade atual. 
 
Analise de aplicações de métricas em redes sociais 
 
Métricas relevantes na modelagem do sistema: 
 
Centralidade do grau(degree). 
- Proporção de nós diretamente conectados e um nó em em questão. 
Ex: O cara mais popular da escolar tem uma alta centralidade do grau, pois muita gente 
está diretamente ligada até ele. 
 
Centralidade de closeness 
- Distância/impedimento médio entre o nó em questão e todos os outros nós. 
Ex: Se você quer divulgar uma festa, fale primeiro a quem tem alta centralidade de 
closeness, pois essa pessoas consegue dizer facilmente para um grande número de 
pessoas. 
 
Centralidade de betweenness 
- Proporção média de caminhos entre quaisquer dois nós que passa pelo nó em questão. 
Ex: Se você quer evitar uma greve, tire do grupo a pessoa com maior centralidade de 
betweenness, pois ela é essencial para comunicação do grupo, uma vez que uma grande 
número de pessoas tem que falar com ela antes de se comunicar com outras pessoas. 
 
Cálculo da métrica BETWEENNESS 
(CENTRALIDADE DE INTERMEDIAÇÃO) 
1.Enumerar todos os pares de nós ligados entre os quais há caminho possível 
2.Para cada par de nós do item 1 verificar em que fração dos caminhos cada um dos nós 
restantes é intermediário (frações de intermediação) 
3.Somar as frações de intermediação de cada nó 
4.Nor malizar as somas (no caso de rede orientada: dividir por (n-1)*(n-2) e no caso de 
redes não orientadas dividir por (n-1)*(n-2)/2 
 
 
 
 
 
 
Cadeia de Markov 
 
Probabilidades de transição: Probabilidades de transição em uma cadeia de Markov em n 
etapas: 
a°: Vetor de estado no instante 0 
a¹ = a° . P, onde P é a matriz de transição. 
Donde: 
an=a° . Pn e 
Pn=Pn-m . Pm 
(equações de Chapman-Kolmogorov) 
O estado a que satisfaz à equação: 
 
a = a . P é denominado “estado de equilíbrio” 
 
 
Definição de estados em uma Cadeia de Markov 
 
1. Um Estado j é alcançável a partir do Estado i se P(ij)n>0 para algum n>0 { (B,A); (E,C), 
etc} 
2. Um Estado i é comunicante com um Estado j se i é alcançável a partir de j e vice-versa 
{(A,B); (D,E)} 
3. Um Estado é transiente (temporário) se, após sair o sistema jamais pode voltar a este 
Estado (C) 
4. Um Estado não transiente é chamado recorrente (o sistema certamente voltará a ele) 
5. Um Estado é absorvente se o sistema não pode deixá-lo após nele entrar {(F), (D E)} 
6. Um Estado é periódico com período p se o sistema voltar a ele após cada p transições 
 
Cadeia ergódica 
 
Uma Cadeia de Markov será denominada Ergódica se todos os seus estados forem 
recorrentes e aperiódicos. Para uma cadeia ergódica o tempo médio do primeiro retorno 
a um estado, também chamado de tempo médio de recorrência é dado por: 
 
|TRj = 
1
Soma de Pij
̅̅ ̅̅ ̅̅ ̅̅ ̅̅ ̅̅ ̅̅ ̅̅ ̅̅ ̅̅ ̅̅ ̅̅ ̅
| 
n para todo i 
 
Um processo estocástico é um processo de markov se a ocorrência de um estado futuro, 
depender somente o estado imediatamente precedente. 
 
O teorema de markov prova que não importa o começo, e sim as transições. Quando o 
número de transições é muito grande, o número que começa não importa. 
A cadeia de markov testa o resultado de mudanças em buscas de melhorias,o que é mais 
difícil de calcular, são as probabilidades.