Busca de Caminhos em Redes Sociais Geolocalizadas em Tempo Real
Resumo
Este artigo foca no problema de encontrar um caminho entre dois usuários de uma rede social. Soluções clássicas realizam a busca usando a cópia estática do grafo inteiro da rede; o que é impraticável para redes sociais grandes (como Twitter e Facebook) uma vez que elas não fornecem acesso amplo e irrestrito aos seus dados. Nesse trabalho, propomos um algoritmo para buscar caminhos em redes sociais em tempo real, chamado CUTE, e uma ferramenta online que o utiliza, chamada FriendRouter. Na nossa avaliação experimental utilizando o Twitter, o algoritmo encontra caminhos curtos para diversos pares de usuários através da expansão de menos de 40 listas de amigos.Referências
Benevenuto et al, F. (2012). Characterizing user navigation and interactions in online social networks. Information Sciences, 195(15):1–24.
Bigonha, C., Cardoso, T. N. C., Moro, M. M., Gonçalves, M. A., and Almeida, V. A. F. (2012). Sentiment-based inuence detection on twitter. J. Braz. Comput. Soc., 18(3):169–183.
Brodersen, A., Scellato, S., and Wattenhofer, M. (2012). YouTube around the world: geographic popularity of videos. In WWW, pages 241–250.
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1):269–271.
Gubichev, A., Bedathur, S., Seufert, S., and Weikum, G. (2010). Fast and accurate estimation of shortest paths in large graphs. In CIKM, pages 499–508, Toronto, Canada.
Hart, P., Nilsson, N., and Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost path. IEEE Transactions on Systems Science and Cybernetics, 2(2):100–107.
Noulas et al, A. (2011). An empirical study of geographic user activity patterns in foursquare. In ICWSM.
Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA.
Potamias, M., Bonchi, F., Castillo, C., and Gionis, A. (2009). Fast shortest path distance estimation in large networks. In CIKM, pages 867–876, Hong Kong, China.
Rodrigues et al, T. (2011). On word-of-mouth based discovery of the web. In IMC, pages 381–393.
Takhteyev, Y., Gruzd, A., and Wellman, B. (2012). Geography of twitter networks. Social Networks, 34(1):73–81.
Thomsen, J. R., Yiu, M. L., and Jensen, C. S. (2012). Effective caching of shortest paths for location-based services. In SIGMOD, pages 313–324.
Topa, G. (2001). Social interactions, local spillovers and unemployment. Review of Economic Studies, 68(2):261–95.
Travers, J. and Milgram, S. (1969). An experimental study of the small world problem. Sociometry, 32(4):425–443.
Ugander, J., Karrer, B., Backstrom, L., and Marlow, C. (2011). The anatomy of the facebook social graph. CoRR, abs/1111.4503.
Viana, W. and Moro, M. M. (2012). Busca de caminhos entre usuários de redes sociais em tempo real. In BRASNAM, Curitiba, Brazil.
Viana, W. and Moro, M. M. (2013). Friendrouter real-time path nder in social networks. In SIGMOD Undergrad Research Competition, New York City, USA.
Bigonha, C., Cardoso, T. N. C., Moro, M. M., Gonçalves, M. A., and Almeida, V. A. F. (2012). Sentiment-based inuence detection on twitter. J. Braz. Comput. Soc., 18(3):169–183.
Brodersen, A., Scellato, S., and Wattenhofer, M. (2012). YouTube around the world: geographic popularity of videos. In WWW, pages 241–250.
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1):269–271.
Gubichev, A., Bedathur, S., Seufert, S., and Weikum, G. (2010). Fast and accurate estimation of shortest paths in large graphs. In CIKM, pages 499–508, Toronto, Canada.
Hart, P., Nilsson, N., and Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost path. IEEE Transactions on Systems Science and Cybernetics, 2(2):100–107.
Noulas et al, A. (2011). An empirical study of geographic user activity patterns in foursquare. In ICWSM.
Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA.
Potamias, M., Bonchi, F., Castillo, C., and Gionis, A. (2009). Fast shortest path distance estimation in large networks. In CIKM, pages 867–876, Hong Kong, China.
Rodrigues et al, T. (2011). On word-of-mouth based discovery of the web. In IMC, pages 381–393.
Takhteyev, Y., Gruzd, A., and Wellman, B. (2012). Geography of twitter networks. Social Networks, 34(1):73–81.
Thomsen, J. R., Yiu, M. L., and Jensen, C. S. (2012). Effective caching of shortest paths for location-based services. In SIGMOD, pages 313–324.
Topa, G. (2001). Social interactions, local spillovers and unemployment. Review of Economic Studies, 68(2):261–95.
Travers, J. and Milgram, S. (1969). An experimental study of the small world problem. Sociometry, 32(4):425–443.
Ugander, J., Karrer, B., Backstrom, L., and Marlow, C. (2011). The anatomy of the facebook social graph. CoRR, abs/1111.4503.
Viana, W. and Moro, M. M. (2012). Busca de caminhos entre usuários de redes sociais em tempo real. In BRASNAM, Curitiba, Brazil.
Viana, W. and Moro, M. M. (2013). Friendrouter real-time path nder in social networks. In SIGMOD Undergrad Research Competition, New York City, USA.
Publicado
23/07/2013
Como Citar
VIANA, Wladston; MORO, Mirella M.; BENEVENUTO, Fabrício.
Busca de Caminhos em Redes Sociais Geolocalizadas em Tempo Real. In: CONCURSO DE TRABALHOS DE INICIAÇÃO CIENTÍFICA DA SBC (CTIC-SBC), 32. , 2013, Maceió.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2013
.
p. 211-220.
