Redes Complexas: Algoritmo PageRank
Encontrar os nós mais importantes em uma rede complexa é um dos problemas mais importantes em diversas áreas, desde sistemas de busca na Web até sistemas biológicos. Estes nós podem ser representados em formato de uma estrutura de grafo, onde os vértices são o nós e as arestas as ligações.
Existem algumas abordagens para medir a importância de um nó, algumas muito conhecidas são as medidas de centralidades, que medem o quão “central” é um nó. Estas medidas levam em conta as ligações, a influência, a proximidade ou a intermediação entre os nós. Mas existem algoritmos que embora não sejam medidas de centralidade, também trabalham com a importância de um nó, é o caso do algoritmo PageRank.
O algoritmo PageRank foi desenvolvido pelos fundadores do Google, Larry Page e Sergey Brin enquanto cursavam a Universidade de Stanford em 1998. Ele é utilizado no motor de busca do Google para rankeamento de páginas Web utilizando a estrutura de links da web para determinar quais páginas são importantes. Embora o algoritmo tenha sido desenvolvido para a Web, ele também pode ser utilizado para outros problemas de importância de nós em grafos. Um exemplo de aplicação acontece em redes de interação proteína-proteína(PPI) para detetar as proteínas mais “importantes” na rede.
Existem diversas implementações do PageRank disponíveis em algumas bibliotecas, como a NetworkX, uma biblioteca para análises de redes (grafos) em Python. O algoritmo retorna uma estrutura de dicionário, com os nós e seus respectivos valores de PageRank. Uma estrutura em formato de grafo é a entrada do algoritmo conforme a sintaxe a seguir:
import networkx as nxG = nx.DiGraph(nx.path_graph(4)) #G é um grafo
pr = nx.pagerank(G, alpha=0.9)
O parâmetro alpha é opcional, mas o default é 0,85, para outro valor, o parâmetro deve ser informado conforme realizado no exemplo. Um detalhe importante é que o algoritmo PageRank foi projetado para grafos direcionados, mas esse algoritmo não verifica se o grafo de entrada é direcionado. Para ser executado em grafos não direcionados, converte-se cada aresta do grafo direcionado em duas arestas.
Essa é uma introdução ao tema com um algoritmo específico, mas estudos em grafos são muito amplos e resolvem uma gama de problemas, principalmente em análise de dados. Algumas referências são colocadas após o texto para que o leitor possa se aprofundar no tema. Até outro post :)
Referências:
Gábor Iván, Vince Grolmusz, When the Web meets the cell: using personalized PageRank for analyzing protein interaction networks, Bioinformatics, Volume 27, Issue 3, 1 February 2011, Pages 405–407, https://doi.org/10.1093/bioinformatics/btq680
Sergey Brin, Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, Volume 30, Issues 1–7,
1998, Pages 107–117, ISSN 0169–7552, https://doi.org/10.1016/S0169-7552(98)00110-X.
Gleich, David. (2014). PageRank Beyond the Web. SIAM Review. 57. 10.1137/140976649.
https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.link_analysis.pagerank_alg.pagerank.html
