Abstract
In social media directed links can represent anything from close friendship to common interests. Such directed links determine the flow of information and hence indicate an individual influence on others. The influence of a person X over person Y is defined as the ratio of Y’s investment that Y makes on X. Most contemporary networks return source–target paths in an online social network as a result of search ranked by degrees of separation. This approach fails to reflect tie of social strength (i.e., intimacy of two people in terms of interaction), and does not reflect asymmetric nature of social relations (i.e., if a person X invests time or effort in person Y, then the reverse is not necessarily true). In this paper, it is proved that in social graph result can prove to be more effective by incorporating the concept of directed and weighted influence edges taking into account both asymmetry and tie strength. The study is based on two real-world networks: Twitter capturing its retweet data and DBLP capturing its author–coauthor relationship. The experiments have been conducted based on two algorithms—Dijkstra shortest path algorithm and influence-based strongest path algorithm. Then a comparative study was done capturing different cases in which strongest path algorithm was better than shortest path algorithm in different cases.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
M. Granovetter, The Strength of Weak Ties, The American Journal Sociology, 78(6):1360–1380, 1973.
S. Hangal, D. MacLean, M. S. Lam, and J. Heer, All Friends are Not Equal: Using Weights in Social Graphs to Improve Search, 4th SNA-KDD, Workshop’10, Washington D.C, USA, 2010.
P. Dodds, R. Muhammad, and D. Watts, An study of search in global social networks, Science, 301(5634):827, 2003.
L. Adami and E. Adas, How to search a social network, Social Networks, 27(3):187–203, 2005.
D. Horowitz and S. Kanvar, The Anatomy of a Large-Scale Social Search Engine 2010.
Leskovec and E. Horwitz, Planetary-scale views on a large instant messaging network, In WWW’08: Proceedings of the 17th international conference on World Wide Web, pages 915–924, NewYork, USA, 2008, ACM.
J.R. Tyler, D.M. Wilkinson, and B. A. Huberman, Email as spectroscopy: Automated Discovery of Community Structure within Organizations, pages 81–96, Kluver, B.V., Deventer, The Netherlands, 2003.
J. Leskovec, D. Huttenlocher and J. Kleinberg, Signed networks in social media, Proc. 28th CHI, 2010.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Ahmad, A., Ahmad, T., Vijay, H. (2017). Shortest Path Algorithms for Social Network Strengths. In: Satapathy, S., Bhateja, V., Udgata, S., Pattnaik, P. (eds) Proceedings of the 5th International Conference on Frontiers in Intelligent Computing: Theory and Applications . Advances in Intelligent Systems and Computing, vol 515. Springer, Singapore. https://doi.org/10.1007/978-981-10-3153-3_35
Download citation
DOI: https://doi.org/10.1007/978-981-10-3153-3_35
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-10-3152-6
Online ISBN: 978-981-10-3153-3
eBook Packages: EngineeringEngineering (R0)