CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

Comparative Analysis of Algorithms to Discover Shortest Path in Social Networks

by Rida Fatima, Muhammad Asif, Muhammad Kashif Hanif
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 155 - Number 9
Year of Publication: 2016
Authors: Rida Fatima, Muhammad Asif, Muhammad Kashif Hanif
10.5120/ijca2016912435

Rida Fatima, Muhammad Asif, Muhammad Kashif Hanif . Comparative Analysis of Algorithms to Discover Shortest Path in Social Networks. International Journal of Computer Applications. 155, 9 ( Dec 2016), 37-42. DOI=10.5120/ijca2016912435

@article{ 10.5120/ijca2016912435,
author = { Rida Fatima, Muhammad Asif, Muhammad Kashif Hanif },
title = { Comparative Analysis of Algorithms to Discover Shortest Path in Social Networks },
journal = { International Journal of Computer Applications },
issue_date = { Dec 2016 },
volume = { 155 },
number = { 9 },
month = { Dec },
year = { 2016 },
issn = { 0975-8887 },
pages = { 37-42 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume155/number9/26636-2016912435/ },
doi = { 10.5120/ijca2016912435 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-07T00:00:51.125743+05:30
%A Rida Fatima
%A Muhammad Asif
%A Muhammad Kashif Hanif
%T Comparative Analysis of Algorithms to Discover Shortest Path in Social Networks
%J International Journal of Computer Applications
%@ 0975-8887
%V 155
%N 9
%P 37-42
%D 2016
%I Foundation of Computer Science (FCS), NY, USA
Abstract

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.

References
  1. D. M. Boyd and N. B. Ellison, “Social Network Sites: Definition, History, and Scholarship,” J. Comput. Commun., vol. 13, pp. 210–230, 2007.
  2. V. Batagelj and A. Mrvar, “Pajek – program for large network analysis,” Connections, pp. 47–57, 1998.
  3. I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “Wireless sensor networks : a survey,” vol. 38, pp. 393–422, 2002.
  4. J. J. Hopfield, “Neural networks and physical systems with emergent collective computational abilities Biophysics : Hopfield I T ., V .,” vol. 79, no. April, pp. 2554–2558, 1982.
  5. M. E. J. Newman, D. J. Watts, and S. H. Strogatz, “Random graph models of social networks,” vol. 99, 2002.
  6. M. Tavakolifard, Mozhgan Tavakolifard On Some Challenges for Online Trust and Reputation Systems, no. August. 2012.
  7. M. Potamias, F. Bonchi, C. Castillo, and A. Gionis, “Fast shortest path distance estimation in large networks,” Proc. 18th ACM Conf. Inf. Knowl. Manag., p. 867, 2009.
  8. X. Zhao, A. Sala, H. Zheng, and B. Y. Zhao, “Efficient shortest paths on massive social graphs,” 7th Int. Conf. Collab. Comput. Networking, Appl. Work., pp. 77–86, 2011.
  9. J. Sanders, “CUDA by example: an introduction to general-purpose GPU programming,” p. 290, 2011.
  10. S. Torgasin, “Graph-based methods for the design of DNA computations,” 2012.
  11. B. F. S. Revisited, “CS2 Algorithms and Data Structures Note 11 Breadth-First Search and Shortest Paths,” no. February, pp. 1–10, 2005.
  12. R. La, G. F. Italiano, D. Informatica, S. Produzione, and R. Tor, “Speeding Up Dijkstra ’ s Algorithm for All Pairs Shortest Paths ∗ Dipartimento di Informatica e Sistemistica An all pairs variant of Dijkstra ’ s algorithm,” pp. 1–7.
  13. A. B. Sadavare and R. Kulkarni, “A Review of Application of Graph Theory for Network,” Ijcsit.Com, vol. 3, no. 6, pp. 5296–5300, 2012.
  14. and C. T. Mohar, Bojan, “No Title,” Graphs on surfaces., vol. JHU PRESS , 2001.
  15. L. W. Beineke, F. Harary, and J. W. Moon, “Cambridge Philosophical Society,” vol. 60, pp. 1–5, 1964.
  16. B. J. D. Owens, M. Houston, D. Luebke, S. Green, J. E. Stone, and J. C. Phillips, “GPU Computing,” 2008.
  17. R.W. Floyd, “No Title,” Algorithm 97 Shortest path, vol. 5, no. 6, p. 345, 1962.
  18. S. Warshall, “No Title,” A theorem boolean matrices, vol. 1, no. ACM, 9(1):11, p. 12, 1962.
  19. D. Der Naturwissenschaften, “Graph-based Methods for the Design of DNA Computations Svetlana Torgasin aus,” 2012.
  20. S. Torgasin and K. Zimmermann, “An all-pairs shortest path algorithm for bipartite graphs,” vol. 3, no. 4, pp. 149–157, 2013.
  21. M. K. Hanif, “Mapping Dynamic Programming Algorithms on Graphics Processing Units Muhammad Kashif Hanif,” 2014.
  22. M. Kurant and P. Thiran, “On the bias of BFS ( Breadth First Search ).”
  23. M. Gjoka, U. C. Irvine, C. T. Butts, U. C. Irvine, and U. C. Irvine, “Walking in Facebook : A Case Study of Unbiased Sampling of OSNs.”
  24. S. A. Catanese, P. De Meo, E. Ferrara, G. Fiumara, and A. Provetti, “Crawling Facebook for Social Network Analysis Purposes,” pp. 0–7, 2011.
  25. L. Luo and W. Hwu, “An Effective GPU Implementation of Breadth-First Search ∗,” pp. 52–55, 2010.
  26. J. Lee and J. Yang, “A Fast and Scalable Re-routing Algorithm based on Shortest Path and Genetic Algorithms 1 Introduction Related Work : Genetic Algorithm for Shortest Path Problem,” vol. 7, no. 3, pp. 482–493, 2012.
  27. A. Roozbeh, “Resource monitoring in a Network Embedded Cloud Resource monitoring in a Network Embedded Cloud.”
  28. H. Garg, “An Improved Algorithm for Finding All Pair Shortest Path,” vol. 47, no. 25, pp. 35–37, 2012.
  29. A. Aini and A. Salehipour, “Speeding up the Floyd – Warshall algorithm for the cycled shortest path problem,” Appl. Math. Lett., vol. 25, no. 1, pp. 1–5, 2012.
  30. P. Swarnambigai, A. Govt, and A. College, “An Efficient algorithm to compute all pairs shortest path using DNA sequence,” pp. 1–4.
  31. B. Ca, “On the All-Pairs-Shortest-Path.”
  32. F. F. Dragan, “Estimating all pairs shortest paths in restricted graph families : a unified approach ✩,” vol. 2204, no. June 2001, pp. 1–21, 2005.
  33. S. Hougardy, “The Floyd-Warshall Algorithm on Graphs with Negative Cycles,” vol. 110, pp. 279–281, 2010.
  34. L. Roditty, “All-Pairs Shortest Paths with a Sublinear Additive Error.”
  35. P. Harish and P. J. Narayanan, “Accelerating Large Graph Algorithms on the GPU Using CUDA,” pp. 197–208, 2007.
  36. G. J. Katz, “All-Pairs Shortest-Paths for Large Graphs on the GPU All-Pairs Shortest-Paths for Large Graphs on the GPU,” pp. 47–55, 2008.
  37. T. Okuyama, F. Ino, and K. Hagihara, “for Finding All-Pairs,” 2004.
  38. T. M. Chan, “Downloaded 12 / 27 / 12 to 129 . 173 . 72 . 87 . Redistribution subject to SIAM license or copyright ; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM . Unauthorized reproduction of this article is prohibited . Copyright © by SIAM . Unauthorized reproduction of this article is prohibited .,” vol. 39, no. 5, pp. 2075–2089, 2010.
  39. T. Takaoka, “A simplified algorithm for the all pairs shortest path problem with O ( n 2 log n ) expected time,” pp. 326–337, 2013.
  40. B. Lund, R. Hall, J. W. Smith, and R. Hall, “A Multi-Stage CUDA Kernel for Floyd-Warshall.”
Index Terms

Computer Science
Information Sciences

Keywords

Social Network Online Social network Shortest Path Graphs Bipartite Graphs APSP.

Powered by PhDFocusTM