Top

New Generation Computing

Published in:

18-03-2023

Similarity-Based Hybrid Algorithms for Link Prediction Problem in Social Networks

Authors: Hassen Mohamed Kerkache, Lamia Sadeg-Belkacem, Fatima Benbouzid-Si Tayeb

Published in: New Generation Computing | Issue 2/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this study, we propose two hybrid algorithms for link prediction problem in static networks that combine the benefits of both local and global scoring methods, with the objective of compensating the weaknesses of each approach using two strategies: sequential and integrated. In the sequential strategy global scoring methods are used in a pipeline mode after local ones if the full graph is explored and the desired number of edges is not met, in an attempt to complete the missing links in the network. The integrated one combines local and global scoring algorithms together in order to add a missing link to the network. Furthermore, we present four distinct approaches to explore the network’s nodes and edges. Experiments on real-world and synthetic networks revealed that our proposed hybrid algorithms can outperform some of the state-of-the-art link-prediction methods.

previous article A Systematic Literature Review and Future Perspectives for Handling Big Data Analytics in COVID-19 Diagnosis

next article A Novel ORLLTMLP-Based Attack Detection and Blockchain-Aware Security Framework Using LCTFA in Smart City Applications

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Adamic, L.A., Adar, E.: Friends and neighbors on the web. Soc. Netw. 25, 211–230 (2003)CrossRef

Al Hasan, M., Chaoji, V., Salem, S., Zaki, M.: Link prediction using supervised learning. In: SDM06: Workshop on Link Analysis, Counter-Terrorism and Security, Vol. 30, pp. 798–805 (2006)

Aziz, F., Gul, H., Muhammad, I., Uddin, I.: Link prediction using node information on local paths. Phys. A 557, 124980 (2020)CrossRef

Barabási, A.-L., Albert, R.: Emergence of scaling in random networks. Science 286, 509–512 (1999)MathSciNetCrossRefMATH

Batagelj, V., Mrvar, A.: Pajek datasets. http://vlado.fmf.uni-lj.si/pub/networks/data/mix.USAir97.net (2006)

Bliss, C.A., Frank, M.R., Danforth, C.M., Dodds, P.S.: An evolutionary algorithm approach to link prediction in dynamic social networks. J. Comput. Sci. 5, 750–764 (2014)MathSciNetCrossRef

Chen, H., Li, X., Huang, Z.: Link prediction approach to collaborative filtering. In: Proceedings of the 5th ACM/IEEE-CS Joint Conference on Digital Libraries (JCDL’05), pp. 141–142. IEEE (2005)

Cohen, E., Delling, D., Pajor, T., Werneck, R.F.: Computing classic closeness centrality, at scale. In: Proceedings of the Second ACM Conference on Online Social Networks COSN ’14, pp. 37-50. Association for Computing Machinery, New York, NY, USA. https://doi.org/10.1145/2660460.2660465 (2014)

Daud, N.N., Ab Hamid, S.H., Saadoon, M., Sahran, F., Anuar, N.B.: Applications of link prediction in social networks: a review. J. Netw. Comput. Appl. p. 102716 (2020)

10.

Erciyes, K.: Complex Networks: An Algorithmic Perspective, 1st edn. CRC Press Inc., Boca Raton (2014)CrossRefMATH

11.

Isella, L., Stehlé, J., Barrat, A., Cattuto, C., Pinton, J.-F., Van den Broeck, W.: What’s in a crowd? analysis of face-to-face behavioral networks. J. Theor. Biol. 271, 166–180 (2011)MathSciNetCrossRefMATH

12.

Jaccard, P.: Étude comparative de la distribution florale dans une portion des alpes et des jura. Bull. Soc. Vaudoise Sci. Nat. 37, 547–579 (1901)

13.

Katz, L.: A new status index derived from sociometric analysis. Psychometrika 18, 39–43 (1953)CrossRefMATH

14.

Kerkache, M.H., Sadeg-Belkacem, L., Benbouzid-Si Tayeb, F., Ali, A.: Supervised learning using community detection for link prediction. In: Senouci, M.R., Boulahia, S.Y., Benatia, M.A. (eds.) Advances in Computing Systems and Applications, pp. 85–94. Springer International Publishing, Cham (2022)CrossRef

15.

Kim, M., Leskovec, J.: The network completion problem: Inferring missing nodes and edges in networks. In: tProceedings of the 2011 SIAM International Conference on Data Mining, pp. 47–58. SIAM (2011)

16.

Jérôme Kunegis. KONECT – The Koblenz Network Collection. In: Proceedings of the International Conference on World Wide Web Companion, pp. 1343–1350 (2013). http://konect.cc/networks/dimacs10-polbooks/

17.

Kumar, A., Singh, S.S., Singh, K., Biswas, B.: Link prediction techniques, applications, and performance: a survey. Phys. A Stat. Mech. Appl. 553, 124289 (2020). https://doi.org/10.1016/j.physa.2020.124289MathSciNetCrossRefMATH

18.

Liben-Nowell, D., Kleinberg, J.: The link-prediction problem for social networks. J. Am. Soc. Inf. Sci. Technol. 58, 1019–1031 (2007)CrossRef

19.

Lim, M., Abdullah, A., Jhanjhi, N., Supramaniam, M.: Hidden link prediction in criminal networks using the deep reinforcement learning technique. Computers 8, 8 (2019)CrossRef

20.

Liu, Z., Zhang, Q.-M., Lü, L., Zhou, T.: Link prediction in complex networks: a local naïve bayes model. CoRR, arXiv:1105.4005. https://doi.org/10.1209/0295-5075/96/48007 (2011)

21.

Lu, Y., Guo, Y., Korhonen, A.: Link prediction in drug-target interactions network using similarity indices. BMC Bioinform. (2017). https://doi.org/10.1186/s12859-017-1460-zCrossRef

22.

Ma, H., Lu, Z., Li, D., Zhu, Y., Fan, L., Wu, W.: Mining hidden links in social networks to achieve equilibrium. Theor. Comput. Sci. 556, 13–24 (2014). https://doi.org/10.1016/j.tcs.2014.08.006. (combinatorial optimization and applications)MathSciNetCrossRefMATH

23.

Martínez, V., Cano, C., Blanco, A.: Prophnet: a generic prioritization method through propagation of information. BMC Bioinform. 15, 1–13 (2014)CrossRef

24.

Martínez, V., Galiano, F.B., Cubero, J.C.: A survey of link prediction in complex networks. ACM Comput. Surv. 49, 69:1-69:33 (2016)

25.

Navarro, E.: Métrologie des graphes de terrain, application à la construction de ressources lexicales et à la recherche d’information. Ph.D. thesis Institut National Polytechnique de Toulouse-INPT (2013)

26.

Newman, M.E.: Clustering and preferential attachment in growing networks. Phys. Rev. E 64, 025102 (2001)CrossRef

27.

Newman, M.E.J.: Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E 74, 036104 (2006). https://doi.org/10.1103/PhysRevE.74.036104MathSciNetCrossRef

28.

Oliveira, M., Gama, J.: An overview of social network analysis. Wiley Interdiscip. Rev. Data Min. Knowl. Discov. 2, 99–115 (2012)CrossRef

29.

Page, L., Brin, S., Motwani, R., Winograd, T.: The PageRank citation ranking: Bringing order to the web.. Technical report Stanford InfoLab (1999)

30.

Rossi, R., Ahmed, N.: The network data repository with interactive graph analytics and visualization. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 29 (2015)

31.

Singh, S. S., Mishra, S., Kumar, A., Biswas, B.: Link Prediction on Social Networks Based on Centrality Measures. Principles of Social Networking: The New Horizon and Emerging Challenges, 71–89 (2022)

32.

Srilatha, P., Manjula, R.: Structural similarity based link prediction in social networks using firefly algorithm. In: 2017 International Conference On Smart Technologies For Smart Nation (SmartTechCon), pp. 560–564. IEEE (2017)

33.

Tong, H., Faloutsos, C., Pan, J.-Y.: Fast random walk with restart and its applications. In: Sixth International Conference on Data Mining (ICDM’06), pp. 613–622. IEEE (2006)

34.

Wang, L., Chen, C., Li, H.: Link prediction of complex network based on eigenvector centrality. J. Phys. Conf. Ser. 2337, 012018 (2022)CrossRef

35.

Wang, P., Xu, B., Wu, Y., Zhou, X.: Link prediction in social networks: the state-of-the-art. Sci. China Inf. Sci. 58, 1–38 (2014)

36.

Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393, 440 (1998)CrossRefMATH

37.

Xu, J., Chen, H.: The topology of dark networks. Commun. ACM 51, 58–65 (2008). https://doi.org/10.1145/1400181.1400198CrossRef

38.

Zachary, W.W.: An information flow model for conflict and fission in small groups. J. Anthropol. Res. 33, 452–473 (1977). https://doi.org/10.1086/jar.33.4.3629752CrossRef

39.

Zeng, S.: Link prediction based on local information considering preferential attachment. Phys. A 443, 537–542 (2016)CrossRef

40.

Zhou, T., Lü, L., Zhang, Y.-C.: Predicting missing links via local information. Eur. Phys. J. B 71, 623–630 (2009)CrossRefMATH

Title: Similarity-Based Hybrid Algorithms for Link Prediction Problem in Social Networks
Authors: Hassen Mohamed Kerkache
Lamia Sadeg-Belkacem
Fatima Benbouzid-Si Tayeb
Publication date: 18-03-2023
Publisher: Springer Japan
Published in: New Generation Computing / Issue 2/2023
Print ISSN: 0288-3635
Electronic ISSN: 1882-7055
DOI: https://doi.org/10.1007/s00354-023-00208-3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 2/2023

Application of Evolutionary Algorithms in Social Networks: A Comparative Machine Learning Perspective

Application of Convolutional Neural Networks for COVID-19 Detection in X-ray Images Using InceptionV3 and U-Net

GUI Enabled Optimized Approach of CNN for Automatic Diagnosis of COVID-19 Using Radiograph Images

Improving the Generalisation Ability of Neural Networks Using a Lévy Flight Distribution Algorithm for Classification Problems

Deep Convolutional Neural Networks for Detecting COVID-19 Using Medical Images: A Survey

Deep Learning Model for COVID-19 Sentiment Analysis on Twitter

Premium Partner