Machine learning approach for link predic-tion in large stochastic online social net-works (SOSNs)
DOI:
https://doi.org/10.63503/j.ijaimd.2024.6Keywords:
Social Networks, Machine Learning, Social CommunitiesAbstract
Social networks are growing every day at a tremendous pace. A social network is an online community that allows users to interact and exchange ideas, in-formation, activities, and interests. Millions of users are contributing to its character and behaviour, and the information being generated has a multi-tude of dimensional aspects that provide new opportunities and perspectives for the computation of network properties. Every individual quickly spreads messages and information throughout all linked groupings. Social networks give users the ability to make a profile, connect with others, and communicate with them through a variety of tools like chatting, updating their status, leav-ing comments, and sharing text, images, audio, and animated videos. With billions of users globally, social media platforms have emerged as an essential part of contemporary social interaction and communication. Along with changing how individuals share and consume information, they have also had a big impact on social, political, and cultural developments. These days, social communities, governmental agencies, and commercial enterprises all depend heavily on online social networks. Understanding networks' evolutionary na-ture requires the ability to predict missing links in existing networks and emerging or broken linkages in future networks. Since SNs undergo dynamic changes over time, link inference in these networks is an extremely difficult task. The dynamic character of supernovae is not well-accounted for in link prediction techniques. In this study, link prediction techniques in dynamic SNs will be thoroughly reviewed, analysed, discussed, and evaluated.
References
P. Wang, X. U. Baowen, W. U. Yurong, and X. Y. Zhou, "Link prediction in social networks: the state-of-the-art", Sci Chin, vol.58, no. (1), Jan 2015, pp. 11101-011101.
Liben-Nowell, D. and Kleinberg, J. (2007), ‘The link-prediction problem for social networks’, Journal of the American society for information science and technology 58(7), 1019–1031
Ricci, F., Rokach, L. and Shapira, B. (2011), Introduction to recommender systems handbook, Springer.
R. Albert, A.-L. Barab´asi, Statistical mechanics of complex networks, Rev. Mod. Phys. 74 (2002) 47.
Z. Huang, X. Li, H. Chen, Link prediction approach to collaborative filtering,In Proceedings of the 5th ACM/IEEE-CS joint conference on Digital libraries,ACM Press, New York, 2005.
Hasan, Mohammad A., and Chaoji, Vineet, and Salem, Saeed and Zaki, Mohammed. (2006) Link Prediction using Supervised Learning. In Proceedings of SDM Workshop of Link Analysis, Counterterrorism and Security.
Doppa, Janardhan R., and Yu, Jun, and Tadepalli, Prasad, and Getoor, Lise. (2009). Chance-Constrained Programs for Link Prediction. In Proceedings of Workshop on Analyzing Networks and Learning with Graphs at NIPS Conference.
E. A. Leicht, P. Holme, M. E. J. Newman, Vertex similarity in networks, Phys. Rev. E 73 (2006) 026120.
D. Sun, T. Zhou, J.-G. Liu, R.-R. Liu, C.-X. Jia, B.-H. Wang, Information filtering based on transferring similarity, Phys. Rev. E 80 (2009) 017101.
D. R. White, K. P. Reitz, Graph and semigrouphomomorphisms on networks of relations, Social Networks 5 (1983) 193.
P. Holme, M. Huss, Role-similarity based functional prediction in networked systems: application to the yeast proteome, J. R. Soc. Interface 2 (2005) 327.
P. Jaccard, ´Etude comparative de la distribution floraledansune portion des Alpeset des Jura, Bulletin de la SocieteVaudoise des Science Naturelles 37 (1901) 547.
T. Sørensen, A method of establishing groups of equal amplitude in plant sociology based on similarity of species content and its application to analyses of the vegetation on Danish commons, Biol. Skr. 5 (1948) 1.
T. Zhou, L. L¨u, Y.-C. Zhang, Predicting missing links via local information,Eur. Phys. J. B 71 (2009) 623.
Q. Ou, Y.-D. Jin, T. Zhou, B.-H. Wang, B.-Q. Yin, Power-law strength-degree correlation from resource-allocation dynamics on weighted networks, Phys. Rev. E 75 (2007) 021102.
M. Molloy, B. Reed, A critical point for random graphs with a given degree sequence, Random Structure and Algorithms 6 (1995) 161.
R. Yang, C. Yang, X. Peng, and A. Rezaeipanah, “A novel similarity measure of link prediction in multi‐layer social networks based on reliable paths,” Concurrency Computation:Pract. Experience, p. e6829, 2022. DOI: 10.1002/cpe.6829.
S. Najari, M. Salehi, V. Ranjbar, and M. Jalili, “Link prediction in multiplex networks based on interlayer similarity,” Phys. A: Stat. Mech. Appl., vol. 536, p. 120978, 2019.
M. K. Manshad, M. R. Meybodi, and A. Salajegheh, “A new irregular cellular learning automata-based evolutionary computation for time series link prediction in social networks,” Appl. Intell., vol. 51, no. 1, pp. 71–84, 2021.
A. Zareie and R. Sakellariou, “Similarity-based link prediction in social networks using latent relationships between the users,” Sci. Rep., vol. 10, no. 1, pp. 1–11, 2020.
R. Xiang, J. Neville, and M. Rogati, “Modeling relationship strength in online social networks,” in International Conference on World WideWeb, 2010.
Ali, Haider, et al. “Energy Efficient Heuristic Algorithm for TaskMapping on Shared-Memory Heterogeneous MPSoCs.” 2018 IEEE20th International Conference on High Performance Computing andCommunications; IEEE 16th International Conference on Smart City;IEEE 4th International Conference on Data Science and Systems(HPCC/SmartCity/DSS).IEEE, 2018.
Ali, Haider, et al. “Contention & Energy-Aware Real-Time TaskMapping on NoC Based Heterogeneous MPSoCs.” IEEE Access 6(2018): 75110-75123.
Ali, Haider, et al. “Energy Efficient Task Mapping & Scheduling onHeterogeneous NoC-MPSoCs in IoT Based Smart City.” 2018 IEEE20th International Conference on High Performance Computing andCommunications; IEEE 16th International Conference on Smart City;IEEE 4th International Conference on Data Science and Systems(HPCC/SmartCity/DSS). IEEE, 2018.
Sharma, Upasana, Sharma, Khatri, and S. Kumar, “Elimination basedalgorithm for link prediction on social networks,” International Journalof System Assurance Engineering & Management, vol. 6, no. 1, pp. 78-82, 2015.
L. A. Adamic and E. Adar, “Friends and neighbours on the Web,” Social Networks, vol. 25, no. 3, pp. 211-230, 2003.
S. N. Dorogovtsev and J. F. Mendes, “Evolution of networks,” Advances in physics, vol. 51, pp. 1079-1187, 2002.
J. A. Hanley and B. J. McNeil, “A method of comparing the areas under receiver operating characteristic curves derived from the same cases,” Radiology, vol. 148, pp. 839-843, 1983.
J. L. Herlocker, J. A. Konstan, L. G. Terveen and J. T. Riedl, “Evaluating collaborative filtering recommender systems,” ACM Transactions on Information Systems (TOIS), vol. 22, pp. 5-53, 2004.
Kuo T T, Yan R, Huang Y Y, et al. Unsupervised link prediction using aggregative statistics on heterogeneous social networks[C]//Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2013: 775-783.
M. E. Newman, “Clustering and preferential attachment in growing networks,” Physical Review E, vol. 64, 025102, 2001.
Liben-Nowell, D 2005, An Algorithmic Approach to Social Networks, Ph.D thesis at MIT Computer Science and Artificial Intelligence Laboratory.
Leskovec, J, Kleinberg, J & Faloutsos, C 2005, 'Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations', Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, 21-24 August 2005.
CHOUDHURY, N. & UDDIN, S. 2016. Time-aware link prediction to explore network effects on temporal knowledge evolution. Scientometrics, 108, 745-776.
AHMED, N. M. & CHEN, L. 2016. An efficient algorithm for link prediction in temporal uncertain social networks. Information Sciences, 331, 120-136.
PAN, L., ZHOU, T., LÜ, L. & HU, C.-K. 2016. Predicting missing links and identifying spurious links via likelihood analysis. Scientific reports, 6
XIE, F., LIU, J., TANG, M., ZHOU, D., CAO, B. & SHI, M. Multi-relation Based Manifold Ranking Algorithm for API Recommendation. Advances in Services Computing: 10th Asia-Pacific Services Computing Conference, APSCC 2016, Zhangjiajie, China, November 16-18, 2016, Proceedings 10, 2016. Springer, 15-32.
CHEN, H.-H., MILLER, D. J. & GILES, C. L. 2013. The predictive value of young and old links in a social network. Proceedings of the ACM SIGMOD
Barabasi, A. L., Linked – The New Science of Networks, Perseus, 2002.
Getoor, L., Diehl, C. P., Link Mining: A Survey. SIGKDD Explorations, Vol.7, No.2, pp.3-12, 2005.
Hasan, M. A., Chaoji, V., Salem, S., Zaki, M. Link Prediction using Supervised Learning, in workshop on link discovery; issues, approaches and applications, 2005.
Huang, Z., Link Prediction Based on Graph Topology: The Predictive Value of the Generalized Clustering Coefficient, in Proceedings of LinkKDD, 2006.
Kautz, H., Selman, B., Shah, M. The Hidden Web. AI Magazine, Vol. 18, No. 2, 27-36, 1997.
O’Madadhaim, J., Hutchins, J., Smyth, P., Prediction and ranking algorithms for event-based network data, SIGKDD Explorations, Vol.7, No.2, pp.23-30, 2005.
Popescul, A., Ungar, L. H. Statistical relational learning for link prediction, in IJCAI workshop on learning statistical models from relational data, 2003.
Julian, K., & Lu, W. (2016). Application of Machine Learning to Link Prediction.
Caiyan, D., Chen, L., Li, B. (2107). Link prediction in complex network based on modularity. Journal of Soft Computing, 2017, 21(15): 4,197–4,214.
Moradabadi, B. and Meybodi, M. R. (2108). Link prediction in stochastic social networks: Learning automata approach. Journal of Computational Science, 2018, 24: 313–328.
Niladri S., Saptarshi B. , Sukumar N., Sanasam R. S. (2018). Temporal link prediction in multi-relational network. World Wide Web Journal, 2018, 21(2): 395–419.
Almansoori W., Gao S., Jarada T. N., et al. Link prediction and classification in social networks and its application in healthcare and systems biology. Network Modeling Analysis Health Informatics Bioinformatics, 2012, 1: 27–36.
Ibrahim, N. M. A. and Chen, L. (2015). Link prediction in dynamic social networks by integrating different types of information. Applied Intelligence, 42(4), 738–750.
Bliss, C. A., Frank, M. R., Danforth, C. M. and Dodds, P. S. (2014). An evolutionary algorithm approach to link prediction in dynamic social networks. Journal of Computational Science, 5(5), 750–764.
Bhat, S. Y. and Abulaish, M. (2015). HOCTracker: Tracking the evolution of hierarchical and overlapping communities in dynamic social networks. IEEE Transactions on Knowledge and Data Engineering, 27(4), 1,019–1,013.
Juszczyszyn, K., Musial, K. and Budka, M. (2011, October). Link prediction based on subgraph evolution in dynamic social networks. In Privacy, Security, Risk and Trust (PASSAT) and 2011 IEEE Third International Conference on Social Computing (SocialCom), 2011 IEEE Third International Conference on (pp. 27–34). IEEE.
enda, T., Angelova, R. and Bedathur, S. (2009, June). Towards timeaware link prediction in evolving social networks. In Proceedings of the 3rd workshop on social network mining and analysis (p. 9). ACM.
Greene, D., Doyle, D. and Cunningham, P. (2010, August). Tracking the evolution of communities in dynamic social networks. In Advances in social networks analysis and mining (ASONAM), 2010 International Conference (pp. 176–183). IEEE.
Gao, S., Denoyer, L. and Gallinari, P. (2011, October). Temporal link prediction by integrating content and structure information. In Proceedings of the 20th ACM International Conference on Information and Knowledge Management (pp. 1,169–1,174). ACM.
Sarkar, P., Chakrabarti, D. and Jordan, M. (2012). Nonparametric link prediction in dynamic networks. arXiv preprint arXiv:1206.6394.
Kunegis, J., De Luca, E.W. and Albayrak, S. 2010. The link prediction problem in bipartite networks. In International Conference on Information Processing and Management of Uncertainty in Knowledge-based Systems. 380-389. Springer, Berlin, Heidelberg. DOI= https://doi.org/10.1007/978-3-642-14049-5_39.
Su Z, Zheng X, Ai J, Shang L, Shen Y (2019) Link prediction in recommender systems with confidence measures. Chaos Inter J Nonlinear Sci 29(8):083133.
Daud NN, Ab Hamid SH, Saadoon M, Sahran F, Anuar NB (2020) Applications of link prediction in social networks: a review. J Netw Comput Appl 166:102716.
Kumar A, Singh SS, Singh K, Biswas B (2020) Link prediction techniques, applications, and performance: a survey. Physica A 553:124289.
Mishra S, Singh SS, Kumar A, Biswas B (2022) Elp: link prediction in social networks based on ego network perspective. Physica A 605:128008.
Arrar, D., Kamel, N. & Lakhfif, A. A comprehensive survey of link prediction methods. J Supercomput 80, 3902–3942 (2024). https://doi.org/10.1007/s11227-023-05591-8.
Y. V. Nandini, T. Jaya Lakshmi, Murali Krishna Enduri and Hemlata Sharma, Link Prediction in Complex Networks Using Average Centrality-Based Similarity Score Journal: Entropy, 2024, Volume 26, Number 6, Page 433.DOI: 10.3390/e26060433
Y. V. Nandini, T. Jaya Lakshmi, Murali Krishna Endur, Link Prediction in Complex Networks: An Empirical Review Intelligent Data Engineering and Analytics, 2023, Volume 371.ISBN : 978-981-99-6705-6.
Li, M., Zhou, S., Chen, G. (2023). Link Prediction of Complex Networks Based on Local Path and Closeness Centrality. In: Dinh, T.N., Li, M. (eds) Computational Data and Social Networks . CSoNet 2022. Lecture Notes in Computer Science, vol 13831. Springer, Cham. https://doi.org/10.1007/978-3-031-26303-3_5.
Stanford Large Network Dataset Collection
Bhanodia PK, Khamparia A, Pandey B. Supervised shift k-means based machine learning approach for link prediction using inherent structural properties of large online social network. Computational Intelligence. 2020;1–18
