Análise de navegação na rede do Facebook

A navegação em redes é uma abordagem na literatura que estuda a forma de encontrar um caminho apenas utilizando informação local, onde podem ser analisados em vista do grau do vértice, centralidade, closeness e etc. O estudo nessa área ajuda entender como a internet ou sistema de telecomunicação funciona através do comportamento dos algoritmos nas respectivas redes.

Nesse artigo irei abordar o comportamento na navegação de uma rede do Facebook disponibilizada pelo Repositório de redes complexas de Stanford em relação ao betweenness. Como métodos de comparação será utilizado a navegação aleatória e grau máximo para servir como contraponto para a técnica mencionada. Além disso, terá duas abordagens de algoritmos, a primeira sendo com memória global onde cada nó visitado guarda a informação de quais nós foram visitados, e a segunda sendo sem memória a qual não apresenta informação se os nós foram visitados.

Algoritmo

O algoritmo base para a análise é de busca em profundidade. Para análise em busca com memória global foi utilizado as seguintes estratégias:

• Busca aleatória: Na abordagem aleatória a partir de um vértice qualquer é escolhido um vizinho aleatoriamente que não foi visitado.
• Grau maior: Na abordagem de grau máximo foi escolhido sempre o vértice que apresenta o maior grau que não foi visitado.
• Maior betweenness: Nessa abordagem é escolhido o vértice que apresenta o maior betweenness que não foi visitado

Para a busca local um vértice pode ser visitado mais de uma vez, portanto para auxiliar o tempo de busca foi utilizado uma estratégia na qual se um dos vizinhos for o destino o algoritmo irá encaminhar para ele. Para a busca aleatória cada vértice tem possibilidade uniforme de ser escolhido, entretanto, para as estratégias de grau e betweenness os vértices serão escolhidos aleatoriamente seguindo uma probabilidade para os nós com valores maiores de terem mais chance de serem escolhidos. Para essa abordagem é necessário alguma condição de parada chamada condição de falha, assim foi definido que número de pulos máximo, a condição, será a quantidade de vértices na rede.

Rede em estudo

A rede em questão apresenta as seguintes métricas:

• Número de vértices: 4039
• Número de enlaces: 88234
• Grau médio: 43.69
• Grau Hub: 107
• Tamanho médio dos caminhos: 3.69
• Coeficiente de aglomeração: 0.60

Método

A rede contém muitos enlaces, portanto para executar todos eles o custo computacional seria muito alto. Então foi necessário utilizar algum método para analisar as conexões da rede em questão de forma que pudesse reduzir esse custo. Dessa forma foi observado que o valor máximo dos menores caminho entre os pares era 8. Com esse valor foi analisado a distribuição dos menores caminhos dos pares a qual pode ser observado logo abaixo:

A distância que apresenta a menor quantidade em sua distribuição é com o tamanho 8 com 19659 pares com essa distância. Então foi decidido pegar 1000 pares de forma aleatória de cada distância observada, dando 8000 pares de caminhos para serem calculados e analisados. Todos os algoritmos foram implementados e executados na linguagem Python.

Resultados

Global Search

Abaixo podemos ver o resultado da distribuição para cada método em estudo

Distribuição do número de pulos

Observa-se que com o método aleatório a distribuição se contém mais uniforme em relação às outras, o que torna um modelo com mais caminhos longos, mais de 25% dos caminhos calculados tem uma distância maior de 1800 pulos. Já na perspectiva do grau nota-se que há uma concentração mais ao centro, em torno de 50% dos caminhos calculados estão entre 583 a 1066 pulos, isso influencia muito na diminuição nos caminhos mais longos mostrado na abordagem aleatória.

E entre os modelos em estudos está o betweenness que contém uma boa distribuição para caminhos mais curtos em relação aos métodos anteriores. Para ter uma noção da sua distribuição, mais de 75% dos pares calculados se apresentam menores que o primeiro quartil da análise com grau máximo. Isso significa que a abordagem de procurar o vértice maior betweenness ajuda a encontrar o caminho mais curto. Se formos observar sua distribuição para cada classe de menor caminho podemos perceber algumas características:

Quando o nó destino está a uma distância mais próxima, as distâncias se mantém mais uniformes e com a presença de valores grandes, isso é perceptível nas classes com menor caminho com valores iguais a 1, 2 e 3 que contém uma distância média de 331.794, 206.8, 130.991, respectivamente. O valor da distância média vai diminuindo com os pares com menor caminho maior, aqueles que apresentam o valor de 8 pulos tem uma média de 6.337 pulos.

Local Search

A busca local apresentou um comportamento decrescente para todos os método, porém teve um que sobressai com uma distribuição maior inicialmente como podemos ver logo abaixo:

A taxa de erro para o método aleatório, grau máximo e betweenness máximo é 39.15%, 36.575% e 2.275%, respectivamente. O betweenness contém o melhor resultado, com mais de 75% dos caminhos com distância menores ou igual a 13 pulos com sua maior distância com valor de 781 pulos, o que representa menos que a metade do maior caminho dos outros dois modelos. A sua distribuição para cada classe de tamanho mínimo está representado logo abaixo:

Com a classe com menor caminho igual 1 o resultado foi unânime, o motivo está pela abordagem mencionada no tópico explicando sobre o algoritmo. A concentração inicial foi diminuindo com o aumento da classe de menor caminho, com o caminho igual a 8 com um caminho médio de 110 pulos e com porcentagem de erro de 13.9%. As classes 1, 2 , 3, 4 e 6 tiveram a taxa de erro inferior a um ou igual a zero.

Conclusão

No contexto da rede em estudo (Facebook), a técnica de navegação por betweenness se portou muito bem com resultados melhores que as técnicas em comparação. Isso significa que não necessariamente os usuários com maior conexões (grau máximo) levarão a outros usuários mais fácilmente, mas sim aqueles que servem como caminho para múltiplas conexões (Betweenness)

Com isso em mente é importante notar o desempenho do betweenness em relação a busca local a qual teve uma taxa de erro muito baixa em relação aos outros modelos. Assim o algoritmo se comporta bem quando a busca utiliza o método preferencial para nós com maiores betweenness representando um boa abordagem para análise para esse tipo de rede. Outras abordagens poderiam ser feitas em outras redes que contém relações em redes sociais para fixar tal abordagem.

Referência

Ted G. Lewis — Network Science: Theory and Practice (2009)

https://redesemexame.blogspot.com/2020/11/navegando-em-redes-complexas.html

https://redesemexame.blogspot.com/2020/11/usando-informacao-local-para-navegar-em.html