Classification Algorithm for Link Prediction Based on Generated Features of Local Similarity-Based Method

Siti Apryanti Koni’ah, Herman Yuliansyah

Abstract


A social network is a social structure that consists consisting of nodes, edges, or links and describes activity on a social media platform. Later, link prediction is a technique to predict new relationships for future networks based on information explored from the current network topology. Several local similarity-based methods use topological information to predict the link. However, these methods have different performances and depend on the network topology. This study proposes using classification algorithms of machine learning to predict future links. The classification algorithms compared are k-Nearest Neighbors (KNN), Naive Bayes, Decision Tree, and Random Forest by comparing six social network datasets with features generated from local similarity-based methods. This research was conducted in three stages: preprocessing, classification comparison, and performance evaluation. The findings of this study are that the Random Forest algorithm outperforms for testing accuracy, precision, and F1-Score. However, in the recall test results, Random Forest only outperformed other benchmark algorithms in the four datasets: soc-karate, soc-dolphin, soc-highschool M, and Soc-sparrowlyon-flock-season 03. Meanwhile, in the datasets soc-tribes and soc-aves-weaver-social-05, the Decision Tree algorithm outperformed other benchmark algorithms.

Full Text:

PDF

References


J. Valverde-Rebaza and A. de Andrade Lopes, “Exploiting behaviors of communities of twitter users for link prediction,” Soc. Netw. Anal. Min., vol. 3, no. 4, pp. 1063–1074, 2013, doi: 10.1007/s13278-013-0142-8.

R. Diestel, Graph Theory, Fifth Edit. Springer Nature, 2018.

P. Wang, B. Xu, Y. Wu, and X. Zhou, “Link prediction in social networks: the state-of-the-art,” Sci. China Inf. Sci., vol. 58, no. 1, pp. 1–38, Jan. 2015, doi: 10.1007/s11432-014-5237-y.

A. K. S. Kushwah and A. K. Manjhvar, “A review on link prediction in social network,” Int. J. Grid Distrib. Comput., vol. 9, no. 2, pp. 43–50, 2016, doi: 10.14257/ijgdc.2016.9.2.05.

C. Chen, S. Deng, and J. Lu, “Link prediction in author collaboration network based on BP neural network,” MATEC Web Conf. Conf., vol. 139, 2017, doi: 10.1051/matecconf/201713900073.

H. Yuliansyah, Z. A. Othman, and A. A. Bakar, “Taxonomy of Link Prediction for Social Network Analysis: A Review,” IEEE Access, vol. 8, pp. 183470–183487, 2020, doi: 10.1109/access.2020.3029122.

A. Kumar, S. S. Singh, K. Singh, and B. Biswas, “Link prediction techniques, applications, and performance: A survey,” Phys. A Stat. Mech. its Appl., vol. 553, p. 124289, 2020, doi: 10.1016/j.physa.2020.124289.

T. Zhou, L. Lü, and Y. C. Zhang, “Predicting missing links via local information,” Eur. Phys. J. B, vol. 71, no. 4, pp. 623–630, 2009, doi: 10.1140/epjb/e2009-00335-8.

Z. Tao and J. Zhang, “A Survey of Link Prediction in Complex Networks V´ICTOR,” Proc. - 2013 4th World Congr. Softw. Eng. WCSE 2013, vol. 49, no. 4, pp. 217–220, 2013, doi: 10.1109/WCSE.2013.39.

E. C. Mutlu, T. Oghaz, A. Rajabi, and I. Garibay, “Review on Learning and Extracting Graph Features for Link Prediction,” Mach. Learn. Knowl. Extr., vol. 2, no. 4, pp. 672–704, 2020, doi: 10.3390/make2040036.

X. Liu, “Full-Text Citation Analysis : A New Method to Enhance,” J. Am. Soc. Inf. Sci. Technol., vol. 64, no. July, pp. 1852–1863, 2013, doi: 10.1002/asi.

A. P. S. Nisha S Sarma, “Friend Recommendation in KNN Classification,” Int. J. Innov. Res. Comput. Commun. Eng., vol. 4, no. 6, pp. 2320–9798, 2016, doi: 10.15680/IJIRCCE.2016. 0406294.

E. Medina-Acuña, P. Shiguihara-Juárez, and N. Murrugarra-Llerena, “Link prediction in co-authorship networks using scopus data,” Commun. Comput. Inf. Sci., vol. 898, pp. 91–97, 2019, doi: 10.1007/978-3-030-11680-4_10.

J. chao Li, D. ling Zhao, B. F. Ge, K. W. Yang, and Y. W. Chen, “A link prediction method for heterogeneous networks based on BP neural network,” Phys. A Stat. Mech. its Appl., vol. 495, pp. 1–17, 2018, doi: 10.1016/j.physa.2017.12.018.

Z. Yang, D. Li, R. Lin, Y. Tang, W. Li, and H. Liu, “An academic social network friend recommendation algorithm based on decision tree,” Proc. - 2018 IEEE SmartWorld, Ubiquitous Intell. Comput. Adv. Trust. Comput. Scalable Comput. Commun. Cloud Big Data Comput. Internet People Smart City Innov. SmartWorld/UIC/ATC/ScalCom/CBDCo, pp. 1311–1316, 2018, doi: 10.1109/SmartWorld.2018.00228.

R. A. Rossi and N. K. Ahmed, “NetworkRepository: An Interactive Data Repository with Multi-scale Visual Analytics,” pp. 4292–4293, 2014, [Online]. Available: http://arxiv.org/abs/1410.3560.

K. E. Read, “Cultures of the central highlands, New Guinea,” Southwest. J. Anthropol., vol. 10, no. 1, pp. 1–43, 2015.

W. W. Zachary, “Flow Modelfor Conflict An Information Fission in Small Groups,” Small, vol. 33, no. 4, pp. 452–473, 2009.

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: Can geographic isolation explain this unique trait?,” Behav. Ecol. Sociobiol., vol. 54, no. 4, pp. 396–405, 2003, doi: 10.1007/s00265-003-0651-y.

D. Shizuka, A. S. Chaine, J. Anderson, O. Johnson, I. M. Laursen, and B. E. Lyon, “Across-year social stability shapes network structure in wintering migrant sparrows,” Ecol. Lett., vol. 17, no. 8, pp. 998–1007, 2014, doi: 10.1111/ele.12304.

R. E. van Dijk, J. C. Kaden, A. Argüelles-Ticó, D. A. Dawson, T. Burke, and B. J. Hatchwell, “Cooperative investment in public goods is kin directed in communal nests of social birds,” Ecol. Lett., vol. 17, no. 9, pp. 1141–1148, 2014, doi: 10.1111/ele.12320.




DOI: https://doi.org/10.32520/stmsi.v11i2.1641

Article Metrics

Abstract view : 147 times
PDF - 58 times

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.