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

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

Link Prediction in Social Networks based on Spectral Clustering using k-medoids and Landmark

by Asmaa M. Mahmoud, Lamiaa M. El Bakrawy, Neveen I. Ghali
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 168 - Number 7
Year of Publication: 2017
Authors: Asmaa M. Mahmoud, Lamiaa M. El Bakrawy, Neveen I. Ghali
10.5120/ijca2017914441

Asmaa M. Mahmoud, Lamiaa M. El Bakrawy, Neveen I. Ghali . Link Prediction in Social Networks based on Spectral Clustering using k-medoids and Landmark. International Journal of Computer Applications. 168, 7 ( Jun 2017), 1-8. DOI=10.5120/ijca2017914441

@article{ 10.5120/ijca2017914441,
author = { Asmaa M. Mahmoud, Lamiaa M. El Bakrawy, Neveen I. Ghali },
title = { Link Prediction in Social Networks based on Spectral Clustering using k-medoids and Landmark },
journal = { International Journal of Computer Applications },
issue_date = { Jun 2017 },
volume = { 168 },
number = { 7 },
month = { Jun },
year = { 2017 },
issn = { 0975-8887 },
pages = { 1-8 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume168/number7/27884-2017914441/ },
doi = { 10.5120/ijca2017914441 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-07T00:15:28.785619+05:30
%A Asmaa M. Mahmoud
%A Lamiaa M. El Bakrawy
%A Neveen I. Ghali
%T Link Prediction in Social Networks based on Spectral Clustering using k-medoids and Landmark
%J International Journal of Computer Applications
%@ 0975-8887
%V 168
%N 7
%P 1-8
%D 2017
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Social networks have become popular because they provide many services and advantages to its users like helping them to connect with new people, share content and share opinions with likeminded people. To conclude which new interactions between members are likely to occur in the near future? This problem defined as the link prediction problem. The traditional methods of link prediction are based on path features and graph features but few consider clustering information. So two link prediction methods based on spectral clustering using k-medoids and landmark are proposed. The first method uses k-medoids to cluster nodes of the graph based on eigenvectors that obtained from the normalized Laplacian matrix. While the second method selects a subset of data points as the landmarks and represents the original data points as the linear combinations of these landmarks. Experimental results demonstrate that our methods achieve high accuracy compared with LSk-means method (Link prediction using Spectral clustering by k-means).

References
  1. J. Valverde-Rebaza and A. de Andrade Lopes, ”Link Prediction in Complex Networks Based on Cluster Information”, SBIA’12 Proceedings of the 21st Brazilian conference on Advances in Artificial Intelligence, Vol 7589, pp 92-101, 2012.
  2. P.Symeonidis, N. Iakovidou, N. Mantas and Y. Manolopoulos: ”From biological to social networks Link prediction based on multi-way spectral clustering”, data Knowl. Eng, Vol 87, pp 226-242, May 2013.
  3. Li F, He J, Huang G, Zhang Y, Shi Y (2014), ”A clusteringbased link prediction method in social networks”, In: 14th international conference on computational science. ICCS 2014, Vol 29, pp 432-442 ,2014.
  4. M. Al Hasan, V. Chaoji, S. Salem, and M. J. Zaki, ”Link Prediction using Supervised Learning”, In Proceedings of the 4th Workshop of Link analysis, Counterterrorism and Security (with SIAM). Bethesda, MD, USA, pp 1-10, 2006 .
  5. M. Fire, Lena Tenenboim, O. Lesser, R. Puzis, L. Rokach, and Y. Elovici, SocialCom, ”Link Prediction in Social Networks using Computationally Efficient Topological Features”, IEEE Third International Confernece on Social Computing (Social- Com), Vol 2, pp 73-80, 2011.
  6. B.C.Craenen ,A.E. Eiben, ”Computational Intelligence”, ch6 in ARTIFICIAL INTELLIGENCE in Encyclopedia of Life Support Systems (EOLSS), Vol 1, pp 105-118, 2009.
  7. M.C. Nicoletti1, L.C. Jain2, and R.C. Giordano, ”Computational Intelligence Techniques for Bioprocess Modelling”, Supervision and Control Volume 218 of the series Studies in Computational Intelligence, pp 1-23, 2009.
  8. Parodi, ”Annals of Actuarial Science”, Vol 6, part 2, pp 344-380, 2012.
  9. Lamiaa M. El Bakrawy, Abeer S. Desuky, ”A hybrid classification algorithm and its application on four real-world data sets”, International Journal of Computer Science and Information Security (IJCSIS), Vol 13, No. 10,pp 93-97, 2015
  10. Khurram I. Qazi a, H.K. Lam a, Bo Xiao a, Gaoxiang Ouyang b and Xunhe Yin c, ” Classification of epilepsy using computational intelligence techniques”, CAAI Transactions on Intelligence Technology, Vol 1, Issue 2, pp 137149, 2016.
  11. Han Yuan, Yunlong Ma, Feng Zhangaand Min Liu and Weiming Shen, ”A Distributed Link Prediction Algorithm Based on Clustering in Dynamic Social Networks”, IEEE International Conference on Systems, Man, and Cybernetics 2015, pp 1341-1345, 2015.
  12. X. Chen and D. Cai, ”Large Scale Spectral Clustering via Landmark-Based sparse Representation”, IEEE Transactions on Cybernetics, Vol 45, Issue 8, pp 1669-1680, 2015 .
  13. Soundarajan S.,Hopcroft J, ”Using community information to improve the precision of link prediction methods”, in Proceedings of the 21st International Conference Companion on World Wide Web (companion volume), pp 607-608, 2012.
  14. Z. Abbassi and V. S. Mirrokni, ”A Recommender System Based on Local Random Walks and Spectral Methods”, Advances in Web Mining and Web Usage Analysis, Vol 5439 of the series Lecture Notes in Computer Science, pp 139-153, 2007.
  15. E. Hoseini, S. Hashemi and A. Hamzeh, ”Link Prediction in Social Network Using Co-clustering based Approach”, 2012 26th International Conference on Advanced Information Networking and Applications Workshops, Vol 189 ,pp 795-800, 2012.
  16. Kunegis, J. Fay, D.; Bauckhage, C., ”Network Growth and the Spectral Evolution Model”, CIKM ’10 Proceedings of the 19th ACM international conference on Information and knowledge management, pp 739-748, 2010
  17. Z. Huang, ”Link Prediction Based on Graph Topology: The Predictive Value of the Generalized Clustering Coefficient”, In Workshop on Link Analysis, the Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp 20-23, 2006.
  18. J. Kim, M. Choy, D. Kim, U. Kang, ”Link prediction based on generalized cluster information”, WWW’14 companion Proceedings of the 23rd International Conference on World Wide Web (companion volume), pp 317-318, 2014.
  19. X.Wang, D. He, D. Chen and J. Xu, ”Clustering-Based Collaborative Filtering for Link Prediction” , AAAI Publications, Twenty-Ninth AAAI Conference on Artificial Intelligence, pp 332-338, 2015
  20. Dr.T. Velmurugan, ”Efficiency of k-Means and K-Medoids Algorithms for Clustering Arbitrary Data Points”, International Journal of Computer Applications in Technology, Vol 3(5), pp 1758-1764, 2012.
  21. T.S.Madhulatha, ”Comparison between K-Means and KMedoids Clustering Algorithms”, Advances in Computing and Information Technology, Vol 198, pp 472-481, 2011.
  22. S.Chu, J.F Roddick, Yi . Chen, J.S. Pan, ”Efficient search approaches for k-medoids-based algorithms” TENCON ’02. Proceedings. 2002 IEEE Region 10 Conference on Computers, Communications, Control and Power Engineering, 2002.
  23. H.S Park, C.H Jun, ”A simple and fast algorithm for Kmedoids clustering”, Expert Systems with Applications, Vol 36 , pp 3336-3341, 2009.
  24. R. Pratap, K .S.Vani, J .R. Devi and Dr.K Nageswara Rao, ”An Efficient Density based Improved K- Medoids Clustering algorithm”, International Journal of Advanced Computer Science and Applications (IJACSA), Vol 2 Issue 6, pp 49-54, 2011.
  25. S. Saket, S. Pandya, ”Implementation of Extended KMedoids Algorithm to Increase Efficiency and Scalability using Large Datasets”, International Journal of Computer Applications (0975 - 8887), Vol 6, No 5, pp 19-23, 2016.
  26. Ulrike von Luxburg,” A Tutorial on Spectral Clustering”, Statistics and Computing December 2007, Vol 17, Issue 4, pp 395-416, 2007.
  27. D. Yan, L. Huang, M. Jordan, ”Fast approximate spectral clustering”, Proceedings 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp 907-916, (Paris, France), 2009.
  28. Zejun Gan, Chaofeng Sha and Junyu Niu,”Fast Spectral Clustering with Landmark-based Subspace Iteration”, 2013 IEEE 13th International Conference on Data Mining Workshops, pp 773-779, 2013.
  29. Feng X.,Zhao J.,Xu K, ”Link prediction in complex networks: a clustering perspective”, The European Physical Journal B, Vol 85, pp 1-9, 2012.
  30. D. Cai, H Bao, X. He, ”Sparse Concept Coding for Visual Analysis”, Proceeding CVPR, IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2011.
  31. H.Lee, R. Raina, A. Battle and A ng, ”Efficient sparse coding algorithms”, NIPS, Vol 22, pp 801-808, 2007.
  32. L L,Zhou T, ”Link prediction in complex networks: a survey”, Physica A: Statistical Mechanics and its Applications, Vol 390, pp 1150-1170, 2011.
  33. Zachary W, ”An information flow model for conflict and fission in small groups”, Journal of Anthropological Research, Vol 33, pp 452-473, 1977, http://networkdata.ics.uci.edu/data/karate/karate.paj
  34. Batageli V, Mrvar A, Pajek datasets (2006), http://vlado.fmf.uni-lj.si/pub/networks/data/mix/usair97.net.
  35. Ackland R, ”Mapping the US political blogosphere”, Presentation to Blog Talk Downunder, 2005. http://wwwpersonal. umich.edu/mejn/netdata/.
  36. D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, and S. M. Dawson,”The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations” Behavioral Ecology and Sociobiology, VOL 54, pp 396-405 (2003). http://networkdata.ics.uci.edu/data/dolphins/dolphins.paj.
  37. Girvan and M. E. J. Newman, ”Community structure in social and biological networks”, Proc. Natl. Acad. Sci. USA, VOL 99, pp 7821-7826, 2002. http://networkdata.ics.uci.edu/data/football/football.paj.
  38. Hage P. and Harary F, ”Structural models in anthropology”, Cambridge: Cambridge University Press, 1983. http://vlado.fmf.uni-lj.si/pub/networks/Data/ucinet/taro.dat.
  39. Mark E. J. Newman. Finding community structure in networks using the eigenvectors of matrices. Physical Review E, Vol 74(3), 2006. http://konect.unikoblenz. de/networks/adjnoun adjacency
  40. W. de Nooy, A. Mrvar, and V. Batagelj, ”Exploratory Social Network Analysis with Pajek”, Cambridge: Cambridge University Press, 2004. http://vlado.fmf.unilj. si/pub/networks/data./esna/korea.htm.
  41. AM Guhl. ”Social behavior of the domestic fowl”, Manhattan, Kansas: Kansas State College, Agricultural Experiment Station, Technical Bulletin 73, 1953. http://konect.unikoblenz. de/networks/moreno_hens.
Index Terms

Computer Science
Information Sciences

Keywords

Social networks link prediction spectral clustering landmark k-medoids sparse coding

Powered by PhDFocusTM