Random Walks

Random Walks em grafos, ou caminhadas aleatórias, são processos que consistem na escolha aleatória de vértices para formar caminhos em um grafo. Este processo estocástico, ou aleatório, é conhecido como Cadeia de Markov Homogênea (CMH), que também pode ser definida como um autômato não-determinístico, sendo portanto um processo não-determinístico.

Uma CMH é importante para a obtenção da distribuição estacionária.  Podemos dizer que uma distribuição estacionária é um conjunto de probabilidades de se passar por cada vértice do grafo durante a caminhada. Ela é muito utilizada em diversas áreas, como por exemplo na computação ao se fazer rankings, como um page rank, pois com esta distribuição estacionária é possível descobrir em um grafo quais são os vértices mais "populares" ou no caso do pagerank, quais são os sites que recebem um maior número de visitas.

Para se obter uma distribuição estacionária única é necessário que a CMH seja irredutível e aperiódica. Para isso, é necessário que o grafo G utilizado para a caminhada aleatória seja conexo, não-direcionado e não-bipartido.

Para se obter tal distribuição estacionária foram usados três métodos:

1. Solução Analítica (Teórica)
2. Power Method
3. Andar do Bêbado

O grafo utilizado para a demonstração foi o Dolphin Social Network (DSN), que representa uma rede social de golfinhos:

Solução Analítica (Teórica)

Esta é a solução considerada ideal. É obtida através do seguinte cálculo:

w(i) = d(vi) / 2|E| 

Onde w(i) é a probabilidade de estar no estado i, d(vi) é o grau do vértice vi e |E| é o número de arestas do grafo. Ou seja, basta dividir o grau de cada vértice por 2 vezes o número de arestas do grafo. Cada valor w(i) que for obtido é armazenado em um vetor de probabilidades W, tendo um elemento para cada vértice:

W = [d(v1) / 2|E|, d(v2) / 2|E|, ... , d(vi) / 2|E|]

Usando o seguinte código em Python

Obtivemos o seguinte vetor de probabilidades, que descreve a distribuição estacionária do grafo DSN:

Power Method

Agora utilizaremos outro método para aprender a distribuição estacionária chamado Power Method, ou Lei da Caminhada Aleatória. Para usar este método devemos primeiramente escolher um número N de passos. Também devemos fazer um "chute" das probabilidades iniciais de se iniciar a caminhada em cada vértice do grafo para obter o vetor de probablidades iniciais w(0). 

Vamos usar um exemplo simples para deixar o conceito mais claro. Tomemos o grafo abaixo:

Figura 1

Podemos escolher valores aleatórios para montar w(0), desde que a soma de todas as probabilidades seja igual a 1. Por exemplo, temos 6 vértices no grafo acima, podemos colocar probabilidades iniciais iguais para todo vértice, sendo portanto 1/6 para cada um, ou seja: 

            v1    v2   v3   v4   v5   v6

w(0) = [1/6, 1/6, 1/6, 1/6, 1/6, 1/6]

Então devemos multiplicar w(0), nosso passo 0, por uma matriz P para encontrar o valor de w(1), nosso próximo passo. P é o resultado da seguinte multiplicação:

  P = Δ-1 * A

Onde A é a matriz de adjacência do grafo, demonstrando quais vértices estão ligados com quais vértices. No exemplo acima A seria igual a:

Δ-1 é igual a uma matriz preenchida com 0 e apenas em sua diagonal com valores correspondentes a 1/d(vi). Em nosso exemplo Δ-1 seria igual a: 

Com esses dados agora seria possível realizar o Power Method para o grafo do exemplo realizando os cálculos:

w(1) = w(0) * P

w(2) = w(1) * P

w(3) = w(2) * P

...

w(N) = w(N-1) * P

Sendo N o número de passos escolhidos inicialmente. Desta forma a cada passo saberemos qual é a probabilidade de se passar por cada vértice. 

Agora que já entendemos os conceitos utilizaremos o Power Method no grafo DSN.

O código em Python utilizado para o Power Method é o seguinte:

O resultado para N = 5 foi:

O resultado para N = 100 foi:

Note as diferenças de valores nas duas tentativas. Se continuarmos a aumentar o número de passos N os valores obtidos serão cada vez mais próximos aos obtidos na solução analítica.

Andar do Bêbado

Figura 2

O andar do bêbado é um método que pode ser ilustrado, como o nome já diz, por um bêbado caminhando. Inicialmente selecionamos aleatóriamente um vértice inicial. É necssário decidir também um número máximo de passos N.

Então, após dar todos os passos, é feito o seguinte cálculo para cada vértice:

w(i)  ≈ n(i)/N

Onde w(i) é a probabilidade de o bêbado passar pelo vértice vi e n(i) é a quantidade de vezes que o bêbado passou pelo vértice vi durante a caminhada.


Os valores de cada vértice são armazenados, então, em um vetor que descreverá a distribuição estacionária do grafo analisado. Quanto maior o número de passos N mais próximos serão os valores da distribuição estacionária obtidos aqui com os obtidos na solução analítica.

Utilizando o grafo DSN podemos verificar o funcionamento do método.

O código utilizado foi:

Tomemos dois exemplos, um com um número relativamente baixo de passos e outro com mais passos. Após chegar aos resultados comparemos com os obtidos na solução analítica.

Primeiramente com N = 100 passos obtemos os seguintes resultados:

Com N = 1000000 temos:

Comparemos com o resultado da solução analítica:

Agora podemos ver na prática que quanto maior o N mais próximo da solução ideal (solução analítica) será o nosso resultado, ou seja, neste caso o resultado mais próximo do ideal foi com N = 1000000.

Entendendo estes conceitos e métodos podemos agora descobrir quais são os 10 golfinhos mais populares do DSN. O código usado para descobrir isto foi:

E aqui temos o TOP 10 dos Golfinhos:

Isto ilustra de forma simplificada como buscadores, como Google, fazem para rankear as páginas da internet.



Referências

Figura 1
http://danielamaral.wikidot.com/introducao-a-teoria-dos-grafos

Figura 2
https://en.wikipedia.org/wiki/Barney_Gumble

Árvores Geradoras Mínimas e Comunidades

Vamos falar sobre  Árvores Geradoras Mínimas e Comunidades desta vez. Primeiro precisamos esclarecer alguns conceitos como o que é uma árvore:

Figura 1

Uma árvore é um grafo conexo e acíclico. Um grafo conexo não tem vértice ou partes isoladas do restante do grafo. Tudo precisa estar conectado. Um grafo acíclico é, como o nome diz, um grafo sem ciclos, ou seja, sem um circuito fechado formado por suas arestas e vértices. Uma árvore possui um vértice inicial chamado raiz, os vértices seguintes são seus filhos que também podem ter filhos, sendo vértices pai desta forma, e assim por diante até chegar às folhas, ou seja, até chegar àqueles vértices que não possuem filhos.

Como este exemplo abaixo:

Figura 2

Sabendo o que é uma árvore podemos agora descobrir o que é uma árvore geradora. Árvore Geradora é aquela originária de um grafo G e que seja formada por todos os vértices de G.

Figura 3

Dá pra notar que existirão várias árvores geradoras de um mesmo grafo:

Figura 4

Uma delas é especial, trata-se da Árvore Geradora Mínima. Uma Árvore Geradora Mínima (MST) é uma árvore geradora de um grafo G ponderado que tem custo total mínimo.

Figura 5 - Árvore geradora mínima desenhada em vermelho

Há alguns algoritmos utilizados para a extração de MST's e o utilizado neste exemplo foi o Algoritmo de Prim:

Ok, vamos explicar como o algoritmo funciona.

O Algoritmo de Prim consiste em escolher um vértice inicial conhecido como raiz, sem aresta alguma ainda, do qual a árvore irá crescer. Então fazemos a árvore crescer, ou seja,  vamos visitando outros vértices adicionando a aresta que está entre o vértice de partida e o novo à árvore.

Esta escolha é feita levando-se em conta o peso das arestas analisadas. A cada descoberta de nova aresta durante o crescimento da árvore o seu peso é colocado em uma lista de prioridades e substitui o seu valor antigo na lista caso seja menor. Esta lista será usada para saber qual aresta deve ser inserida na árvore. A aresta de menor peso na lista de prioridades é sempre escolhida e inserida na árvore.

Caso mais adiante outra aresta que chegue o mesmo vértice tenha uma peso menor que o atual a antiga aresta é retirada e a nova descoberta é inserida. Quando não houver mais vértices para serem visitados teremos uma árvore geradora com a menor soma de pesos de arestas possível, ou seja, encontraremos a Árvore Geradora Mínima.

Agora vamos falar de Comunidades.

Comunidades são, basicamente, conjuntos de vértices isolados. É possível obter comunidades ao retirar arestas da árvore geradora mínima.

Figura 6 - Árvore geradora mínima

Da árvore geradora mínima acima podemos retirar a aresta entre os vértices 'b' e 'e' para obter duas comunidades, chamadas aqui de A e B:

Figura 7 

Há entretanto alguns métodos diferentes para se obter comunidades à partir da remoção de arestas da MST. Utilizaremos dois deles aqui.

A primeira forma é decidir um número k de comunidades que se deseja obter e então retirar as k-1 maiores arestas da MST.

Por exemplo, para se obter duas comunidades (k = 2), ou agrupamentos, da MST utilizada acima bastaria retirar as k-1 maiores arestas, ou seja, se k = 2 então k - 1 = 1, bastaria remover a maior aresta da MST. Neste exemplo a aresta a ser retirada será a entre 'b' e 'c', que tem peso 4, formando os agrupamentos A e B:

Figura 8

Se quisermos um número maior, como k = 5 agrupamentos, basta aplicar a mesma regra e retirar as k-1 maiores arestas, ou seja, as 4 maiores, formando os agrupamentos A, B, C, D e E:

Figura 9

Note como há vários vértices isolados, comunidades de um vértice só, isso se deve em parte ao tamanho do grafo utilizado mas o maior problema foi o método utilizado. Note no primeiro exemplo, com k = 2, como seria possível formar agrupamentos com um número de vértices mais parecidos mas ao invés disso o método utilizado fez com que se formasse uma comunidade com um vértice e outra com cinco. Muitas vezes não é desejável que haja tamanha discrepância entre o tamanho das comunidades e por isso utilizaremos agora outro método.

Desta vez ao invés de simplesmente remover as k-1 maiores arestas da MST para se obter k comunidades iremos utilizar o seguinte cálculo para descobrir qual é a melhor aresta a ser removida da MST de forma a deixar o número de vértices em cada agrupamento mais parecido entre si:

w(A,B) * min{Na, Nb}

Onde w(A,B) é o peso da aresta analisada e min{Na, Nb} é o mínimo entre o número de vértices do grupo A (Na) e o número de vértices do grupo B (Nb), pois sempre que uma aresta for removida serão formados exatamente dois agrupamentos (A e B, neste caso). Após fazer os cálculos para todas as arestas selecionaremos o maior valor e removeremos a aresta correspondente.

Na prática ficaria assim, utilizando o seguinte grafo e sua MST para criar dois agrupamentos:

Figura 10 - Grafo G com sua MST escurecida

Figura 11 - MST resultante sem as outras arestas do grafo G

Fazemos então o cálculo descrito para cada aresta da MST:

ab: 4 * min{1,8} = 4*1 = 4
bc: 8 * min{2,7} = 8*2 = 16
cd: 7 * min{2,7} = 7*2 = 14
de: 9 * min{1,8} = 9*1 = 9
ci: 2 * min{1,8} = 2*1 = 2
cf: 4 * min{3,6} = 4*3 = 12
fg: 2 * min{2,7} = 2*2 = 4
gh: 1 * min{1,8} = 1*1 = 1

O maior valor obtido corresponde a aresta 'bc', que será então removida, obtendo assim dois agrupamentos:

Figura 12

Faremos agora o processo para a obtenção de cinco comunidades. Para isso basta repetir os cálculos com valores e arestas atualizados a cada remoção:

ab: 4 * min{1,1} = 4*1 = 4
cd: 7 * min{2,5} = 7*2 = 14
de: 9 * min{1,6} = 9*1 = 9
ci: 2 * min{1,6} = 2*1 = 2
cf: 4 * min{3,4} = 4*3 = 12
fg: 2 * min{2,5} = 2*2 = 4
gh: 1 * min{1,6} = 1*1 = 1

Desta vez o maior valor obtido corresponde a aresta 'cd', então removendo-a teremos:

Figura 13

Temos três agrupamentos. Retiremos mais uma aresta para obter quatro agrupamentos:

ab: 4 * min{1,1} = 4*1 = 4
de: 9 * min{1,1} = 9*1 = 9
ci: 2 * min{1,4} = 2*1 = 2
cf: 4 * min{2,3} = 4*2 = 8
fg: 2 * min{2,3} = 2*2 = 4
gh: 1 * min{1,4} = 1*1 = 1

A aresta 'de' deve ser removida agora:

Figura 14

Calculamos uma última vez:

ab: 4 * min{1,1} = 4*1 = 4
ci: 2 * min{1,4} = 2*1 = 2
cf: 4 * min{2,3} = 4*2 = 8
fg: 2 * min{2,3} = 2*2 = 4
gh: 1 * min{1,4} = 1*1 = 1

Removemos 'cf' e obtemos os cinco agrupamentos abaixo, como desejado inicialmente:

Figura 15

Podemos notar que desde a primeira remoção este método acabou por evitar que vértices ficassem isolados. É claro que depois de algumas iterações alguns vértices isolados acabaram formando comunidades mas houve uma divisão mais parecida com relação à quantidade de vértices em cada comunidade por fim.

O código em Python utilizado para o primeiro método foi o seguinte:

O código usado para o segundo método foi este:

Caso tenha alguma dúvida, por favor, deixe seu comentário aqui no blog.

Referências das imagens:

Figura 2
http://luizricardo.org/2014/03/desafio-de-programacao-algoritmo-lca-lower-common-ancestor/

Figuras 3 e 4
http://theory.cs.uvic.ca/inf/subg/Spanning.html

Figura 5
http://redesavanzadas2013b.blogspot.com.br/

Figura 10
https://www.cs.indiana.edu/~achauhan/Teaching/B403/LectureNotes/09-mst.html

O Caixeiro Viajante

O problema

O problema do caixeiro viajante é a representação de um problema de minimizar o custo de um ciclo hamiltoniano. Esta representação consiste em um caixeiro que tem que visitar n diferentes cidades levando seus produtos para vender. No entanto, este caminho deve passar somente uma vez por cada cidade e deve começar e terminar no mesma cidade (que pode ser tanto sua casa, quanto a empresa em que trabalha). Assim, para minimizar o custo de visitar estas cidades, devemos responder a seguinte pergunta: qual é a rota mínima para a viagem?

Pensando neste problema, logo vem à nossa cabeça: devemos verificar todas as possíveis rotas e assim identificar a menor delas. Contudo, o cálculo das rotas pode, muitas vezes, ser muito custoso e inviável computa-los. Vejamos:

Se tivermos 3 cidades para visitar, temos 3 opções iniciais para começar, depois 2 para visitar e depois somente 1 para visitar. Ou seja, este problema cresce em tempo exponencial. Para este caso, temos 3! (= 6) possíveis rotas.

Se pegarmos 4 cidades, temos 5! (= 120) possíveis rotas.

No entanto, se tivermos 30 cidades, nosso problema terá um cálculo muito mais custoso e difícil, pois temos 30! ou 2.10^32 (!!!!) possíveis rotas. Além disso, se adicionarmos apenas mais uma cidade, teremos 31! ou 8.10^33 (!!!!) possíveis rotas. Logo, a adição de apenas uma cidade em instâncias grandes, o problema cresce muito em questão de custo de computação.

Complexidade computacional

Por todos estes motivos descritos anteriormente, este problema é considerado da classe NP_Hard.

Logo, pode-se perceber, por termos diferentes escolhas de cidades em todos os momentos do problema (exceto a última iteração), que este é um problema de otimização combinatória.

Para facilitar o cálculo, devemos reduzi-lo a um problema de enumeração e, para isto, devemos:

• acharmos todas as rotas possíveis
• calcularmos o comprimento
• verificarmos qual é a menor rota

Como resolver?

Para resolver este problema, podemos seguir algumas técnicas, como:

• Métodos de busca heurística (algoritmo guloso)
• Métodos de computação bioinspirada
• Algoritmos genéticos
• Colônia de formigas

Porém, para fins de apresentar mais facilmente uma solução deste problema, iremos usar a abordagem de busca heurística, como o Twice Around e o algoritmo 2-optimal.

Ainda mais, para resolver este problema devemos responder a 2 questões:

1. G é hamiltoniano?
2. Se sim, como obter ciclo Hamiltoniano de custo mínimo? -> Não trivial

Para isto, vamos utilizar o algoritmo Twice Around.

Algoritmo Twice Around

Este algoritmo consiste de 3 passos principais:

1. Encontrar uma Minimum Spanning Tree, a fim de ter os menores custos entre os nós (representados pelas cidades)
2. Encontrar um Tour de Euler, para percorrer todas os nós/cidades
3. Obter um ciclo Hamiltoniano a partir deste Tour de Euler, pois devemos passar uma única vez por cada nó/cidade

MST - Algoritmo de Prim

Para encontrarmos a MST do grafo que representa as cidades em que o caixeiro viajante deve passar usaremos o Algoritmo de Prim. Vejamos o exemplo: 

Em relação ao nosso trabalho, fizemos a seguinte implementação para descobrir o MST pelo algoritmo de Prim:

Tour de Euler - Algoritmo de Fleury

O tour de Euler significa que é possível percorrer todas arestas de G sem repetí-las, começando e terminando em um mesmo vértice v qualquer.

Assim, usaremos o Algoritmo de Fleury para identificar este tour que passa por todas as arestas uma única vez.

Ciclo Hamiltoniano

Um ciclo Hamiltoniano significa que é possível percorrer todos os vértices de G uma única vez, começando e terminando em um mesmo vértice v qualquer, que é exatamente o que procuramos para solucionar o problema do caixeiro viajante.

Para encontrarmos este ciclo, basta tomarmos o tour de Euler como base e tirarmos as repetições.

O seguinte trecho de código, representa a obtenção do tour de Euler e em seguida o ciclo Hamiltoniano:

Já para executar todo o algoritmo, criamos um grafo, inicializamos todas suas arestas e depois mostramos o resultado, como pode ser observado a seguir: