Desenvolvimento de um Algoritmo de Busca por Vértices Específicos em Redes
Resumo
Muitas redes reais não estão disponíveis de forma imediata mas podem ser coletadas através de um processo de mineração. Entretanto, em alguns cenários estamos interessados em descobrir apenas vértices que possuem determinadas características, sendo irrelevantes os demais vértices. Para esse problema, algoritmos de busca clássicos (ex. busca em largura) se mostram ineficientes. Neste trabalho utilizamos a homofilia - inerente em muitas redes reais - para propor um modelo matemático que determina a probabilidade de um vértice não explorado possuir a característica. O modelo utiliza as características dos vértices vizinhos já explorados e parâmetros globais da rede. As probabilidades atribuídas pelo modelo guiam um algoritmo de busca informada, que a cada passo faz uma escolha gulosa. Avaliamos o algoritmo em três redes reais, comparando diferentes variações do modelo e outros algoritmos de busca. Os resultados indicam que nenhum dos métodos testados é consistentemente mais eficiente que os demais.
Referências
Avrachenkov, K., Basu, P., Neglia, G., and Ribeiro, B. (2014). Pay Few, Influence Most: Online Myopic Network Covering. In Computer Communications Workshops (INFO-COM WKSHPS), 2014 IEEE Conference on.
Bnaya, Z., Puzis, R., Stern, R., and Felner, A. (2013). Bandit algorithms for social network queries. In Social Computing (SocialCom), 2013 International Conference on, pages 148–153. IEEE.
Bondy, J. A. and Murty, U. S. R. (1976). Graph Theory with Applications. Macmillan/Elsevier, 5 edition. ISBN 0-44-19451-7.
Garnett, R., Krishnamurthy, Y., Xiong, X., Schneider, J., and Mann, R. (2012). Bayesian optimal active search and surveying. In International Conference on Machine Learning, ACM, pages 1239–1246.
Leskovec, J. and Krevl, A. (2014). SNAP Datasets: Stanford large network dataset collection. [link].
Ma, Y., Huang, T.-K., and Schneider, J. G. (2015). Active Search and Bandits on Graphs using Sigma-Optimality. In Conference on Uncertainty Artificial Inteligence, pages 542–551.
Murai, F., Renno, D., Ribeiro, B., Gisele, P., Towsley, D., and Gile, K. (2017). Selective Harvesting over Networks. arXiv preprint arXiv:1703.05082.
Netto, P. O. B. (1996). Grafos: teoria, modelos, algoritmos. Edgard Blücher.
Pfeiffer, J. J., Neville, J., and Bennett, P. (2012). Active sampling of networks. In Workshop on Mining and Learning with Graphs.
Russel, S. and Norvig, P. (2003). Artificial intelligence: A modern approach. EUA: Prentice Hall.
Wang, X., Garnett, R., and Schneider, J. (2013). Active Search on Graphs. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 731–738. ACM.
Xie, P., Zhu, J., and Xing, E. P. (2016). Diversity-promoting bayesian learning of latent variable models. In International Conference on Machine Learning.
