Comparative Analysis of Algorithms to Discover Shortest Path in Social Networks

The huge growth and popularity of social media networks have created unprecedented research opportunities. Finding the affiliation networks and shared interest of user groups within the social network are important and well-studied problems. Graph algorithms provide a measure to characterize the social network structure. Bipartite graphs can be used as a representative model of these problems. The solution depends on efficient discovery of geodesic distance between any two random nodes. To this end, two algorithms are studied and parallelized for comparative performance analysis. In this paper we present the formulation of both algorithms on Graphic Processing Unit platform. The performance is compared on random-generated social network data-sets. General Terms Graphs, Algorithms, Floyd Warshall Algorithm, Tropical algebra, Matrix Multiplication.