Busca de Caminhos entre Usuários de Redes Sociais em Tempo Real
Resumo
A distância média entre nós em uma rede social é pequena, considerando a teoria dos seis graus de separação. No entanto, as redes sociais online não oferecem formas de descobrir caminhos entre seus usuários. Algoritmos tradicionais são aplicáveis para cópias offline de seus grafos. Contudo, na Web, o ideal é encontrar caminhos utilizando dados online, o que é uma tarefa difícil considerando as limitações de acesso impostas pelas redes sociais. Neste trabalho, introduzimos um algoritmo para encontrar caminhos em tempo real, chamado CUTE. Ele utiliza uma heurística que considera a distância geográfica entre os usuários. Na nossa avaliação experimental com o Twitter, o CUTE encontra caminhos curtos entre usuários, expandindo menos de 40 nós.
Palavras-chave:
Análise de Redes Sociais, Tempo Real, Busca de Caminhos
Referências
Bigonha, C., Cardoso, T. N. C., Moro, M. M., Gonçalves, M. A., and Almeida, V. A. F. (2011). Sentiment-based influence detection on twitter. J. Braz. Comput. Soc., online first.
Bollen, J., Mao, H., and Zeng, X. (2011). Twitter mood predicts the stock market. Journal of Computational Science, 2(1):1 – 8.
Cohen, E., Halperin, E., Kaplan, H., and Zwick, U. (2002). Reachability and distance queries via 2-hop labels. In Procs. of ACM-SIAM Symposium on Discrete Algorithms, pages 937–946, San Francisco, California.
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 Procs. of ACM Int’l Conf. on Information and Knowledge Management, 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.
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 Procs. of ACM Conf. on Information and Knowledge Management, pages 867–876, Hong Kong, China.
Sarcevic, A., Palen, L., White, J., Starbird, K., Bagdouri, M., and Anderson, K. (2012). “beacons of hope” in decentralized coordination: learning from on-the-ground medical twitterers during the 2010 haiti earthquake. In Procs. of ACM Conference on Computer Supported Cooperative Work, pages 47–56, Seattle, Washington, USA.
Takhteyev, Y., Gruzd, A., and Wellman, B. (2012). Geography of twitter networks. Social Networks, 34(1):73–81.
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.
Zhao, X., Sala, A., Wilson, C., Zheng, H., and Zhao, B. Y. (2010). Orion: shortest path estimation for large social graphs. In Procs. of Conference on Online Social Networks, page 9, Boston, MA, USA.
Bollen, J., Mao, H., and Zeng, X. (2011). Twitter mood predicts the stock market. Journal of Computational Science, 2(1):1 – 8.
Cohen, E., Halperin, E., Kaplan, H., and Zwick, U. (2002). Reachability and distance queries via 2-hop labels. In Procs. of ACM-SIAM Symposium on Discrete Algorithms, pages 937–946, San Francisco, California.
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 Procs. of ACM Int’l Conf. on Information and Knowledge Management, 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.
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 Procs. of ACM Conf. on Information and Knowledge Management, pages 867–876, Hong Kong, China.
Sarcevic, A., Palen, L., White, J., Starbird, K., Bagdouri, M., and Anderson, K. (2012). “beacons of hope” in decentralized coordination: learning from on-the-ground medical twitterers during the 2010 haiti earthquake. In Procs. of ACM Conference on Computer Supported Cooperative Work, pages 47–56, Seattle, Washington, USA.
Takhteyev, Y., Gruzd, A., and Wellman, B. (2012). Geography of twitter networks. Social Networks, 34(1):73–81.
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.
Zhao, X., Sala, A., Wilson, C., Zheng, H., and Zhao, B. Y. (2010). Orion: shortest path estimation for large social graphs. In Procs. of Conference on Online Social Networks, page 9, Boston, MA, USA.
Publicado
17/07/2012
Como Citar
VIANA, Wladston; MORO, Mirella M..
Busca de Caminhos entre Usuários de Redes Sociais em Tempo Real. In: BRAZILIAN WORKSHOP ON SOCIAL NETWORK ANALYSIS AND MINING (BRASNAM), 1. , 2012, Curitiba.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2012
.
p. 48-59.
ISSN 2595-6094.
