Skip to main content
Top
Published in: New Generation Computing 2/2023

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

Log in

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

search-config
loading …

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.

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!

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!

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!

Literature
1.
go back to reference Adamic, L.A., Adar, E.: Friends and neighbors on the web. Soc. Netw. 25, 211–230 (2003) CrossRef Adamic, L.A., Adar, E.: Friends and neighbors on the web. Soc. Netw. 25, 211–230 (2003) CrossRef
2.
go back to reference 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) 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)
3.
go back to reference Aziz, F., Gul, H., Muhammad, I., Uddin, I.: Link prediction using node information on local paths. Phys. A 557, 124980 (2020) CrossRef Aziz, F., Gul, H., Muhammad, I., Uddin, I.: Link prediction using node information on local paths. Phys. A 557, 124980 (2020) CrossRef
6.
go back to reference 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 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
7.
go back to reference 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) 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)
9.
go back to reference 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) 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.
go back to reference Erciyes, K.: Complex Networks: An Algorithmic Perspective, 1st edn. CRC Press Inc., Boca Raton (2014) CrossRefMATH Erciyes, K.: Complex Networks: An Algorithmic Perspective, 1st edn. CRC Press Inc., Boca Raton (2014) CrossRefMATH
11.
go back to reference 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 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.
go back to reference 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) 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.
go back to reference Katz, L.: A new status index derived from sociometric analysis. Psychometrika 18, 39–43 (1953) CrossRefMATH Katz, L.: A new status index derived from sociometric analysis. Psychometrika 18, 39–43 (1953) CrossRefMATH
14.
go back to reference 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 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.
go back to reference 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) 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)
18.
go back to reference Liben-Nowell, D., Kleinberg, J.: The link-prediction problem for social networks. J. Am. Soc. Inf. Sci. Technol. 58, 1019–1031 (2007) CrossRef Liben-Nowell, D., Kleinberg, J.: The link-prediction problem for social networks. J. Am. Soc. Inf. Sci. Technol. 58, 1019–1031 (2007) CrossRef
19.
go back to reference 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 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
23.
go back to reference Martínez, V., Cano, C., Blanco, A.: Prophnet: a generic prioritization method through propagation of information. BMC Bioinform. 15, 1–13 (2014) CrossRef Martínez, V., Cano, C., Blanco, A.: Prophnet: a generic prioritization method through propagation of information. BMC Bioinform. 15, 1–13 (2014) CrossRef
24.
go back to reference 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) 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.
go back to reference 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) 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.
go back to reference Newman, M.E.: Clustering and preferential attachment in growing networks. Phys. Rev. E 64, 025102 (2001) CrossRef Newman, M.E.: Clustering and preferential attachment in growing networks. Phys. Rev. E 64, 025102 (2001) CrossRef
28.
go back to reference Oliveira, M., Gama, J.: An overview of social network analysis. Wiley Interdiscip. Rev. Data Min. Knowl. Discov. 2, 99–115 (2012) CrossRef Oliveira, M., Gama, J.: An overview of social network analysis. Wiley Interdiscip. Rev. Data Min. Knowl. Discov. 2, 99–115 (2012) CrossRef
29.
go back to reference Page, L., Brin, S., Motwani, R., Winograd, T.: The PageRank citation ranking: Bringing order to the web.. Technical report Stanford InfoLab (1999) Page, L., Brin, S., Motwani, R., Winograd, T.: The PageRank citation ranking: Bringing order to the web.. Technical report Stanford InfoLab (1999)
30.
go back to reference 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) 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.
go back to reference 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) 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.
go back to reference 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) 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.
go back to reference 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) 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.
go back to reference Wang, L., Chen, C., Li, H.: Link prediction of complex network based on eigenvector centrality. J. Phys. Conf. Ser. 2337, 012018 (2022) CrossRef Wang, L., Chen, C., Li, H.: Link prediction of complex network based on eigenvector centrality. J. Phys. Conf. Ser. 2337, 012018 (2022) CrossRef
35.
go back to reference 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) 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.
go back to reference Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393, 440 (1998) CrossRefMATH Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393, 440 (1998) CrossRefMATH
39.
go back to reference Zeng, S.: Link prediction based on local information considering preferential attachment. Phys. A 443, 537–542 (2016) CrossRef Zeng, S.: Link prediction based on local information considering preferential attachment. Phys. A 443, 537–542 (2016) CrossRef
40.
go back to reference Zhou, T., Lü, L., Zhang, Y.-C.: Predicting missing links via local information. Eur. Phys. J. B 71, 623–630 (2009) CrossRefMATH Zhou, T., Lü, L., Zhang, Y.-C.: Predicting missing links via local information. Eur. Phys. J. B 71, 623–630 (2009) CrossRefMATH
Metadata
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

Other articles of this Issue 2/2023

New Generation Computing 2/2023 Go to the issue

Premium Partner