Search for Paths Between Social Network Users in Real Time

• Wladston Viana Federal University of Minas Gerais
• Mirella M. Moro Federal University of Minas Gerais

Abstract

The average distance between us in a social network is small, considering the theory of the six degrees of separation. However, online social networks offer no way to find ways among their users. Traditional algorithms are applicable for offline copying of your graphs. However, in the Web, the ideal is to find ways using online data, which is a difficult task considering the limitations of access imposed by social networks. In this work, we introduced an algorithm to find ways in temporeal, called CUTE. It uses a heuristic that considers the geographic distance between users. In our experimental evaluation with Twitter, oCUTE finds short paths between users, expanding less than 40 nodes.

Keywords: Social Network Analysis, Real Time, Path Search

References

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.