Link prediction using betweenness centrality and graph neural networks
Tóm tắt
Social networks are widely considered as the most important tool to connect people. The last century saw a massive increase in the number of links between users. Many nodes and/or edges are included or removed repeatedly as time passes. In order to understand the patterns of relations among people or organizations, social network analysis (SNA) sheds light on users and links dynamics. Link prediction (LP) is one of the most important research areas of SNA. The main objective of link prediction is to determine whether two nodes will form a link or not in the future. LP uses similarity-based methods such as common neighbors, resource allocation, and Adamic–Adar metrics to forecast potential connections from the current state of networks. Although using the similarity-based methods is highly time efficient, the measures still suffer from low accuracy. The main focus of this paper is to address this drawback by defining a new metric called LSBC that uses the combination of a similarity metric and the betweenness centrality which defines the node’s power over the entire network. The method was illustrated with nine datasets from different types of networks. Experiments show that LSBC captures the similarity of a pair of nodes accurately and surpasses all the state-of-the-arts methods. Furthermore, we use neural network model to address the link prediction as a classification task. The results show that the adding LSBC as additional feature increases the accuracy and reduces the cross-entropy loss.
Tài liệu tham khảo
https://github.com/axe-331/LinkPrediction-using-Betweenness-centrality
citation_journal_title=Social Netw; citation_title=Friends and neighbors on the web; citation_author=LA Adamic, E Adar; citation_volume=25; citation_issue=3; citation_publication_date=2003; citation_pages=211-230; citation_doi=10.1016/S0378-8733(03)00009-1; citation_id=CR2
citation_journal_title=Phys A Stat Mech Appl; citation_title=A new similarity measure for link prediction based on local structures in social networks; citation_author=F Aghabozorgi, MR Khayyambashi; citation_volume=501; citation_publication_date=2018; citation_pages=12-23; citation_doi=10.1016/j.physa.2018.02.010; citation_id=CR3
citation_journal_title=Sci Rep; citation_title=Missing link prediction using common neighbor and centrality based parameterized algorithm; citation_author=I Ahmad, MU Akhtar, S Noor, A Shahnaz; citation_volume=10; citation_issue=1; citation_publication_date=2020; citation_pages=1-9; citation_id=CR4
Al Hasan M, Chaoji V, Salem S, Zaki M (2006) Link prediction using supervised learning. In: SDM06: workshop on link analysis, counter-terrorism and security, vol. 30, pp 798–805
Al Hasan M, Zaki MJ (2011) A survey of link prediction in social networks. In: Social network data analytics, pp 243–275. Springer, Boston, MA
citation_journal_title=Information; citation_title=Mean received resources meet machine learning algorithms to improve link prediction methods; citation_author=J Ayoub, D Lotfi, A Hammouch; citation_volume=13; citation_issue=1; citation_publication_date=2022; citation_pages=35; citation_doi=10.3390/info13010035; citation_id=CR7
citation_journal_title=Phys A Stat Mech Appl; citation_title=Link prediction using node information on local paths; citation_author=F Aziz, H Gul, I Muhammad, I Uddin; citation_volume=557; citation_publication_date=2020; citation_doi=10.1016/j.physa.2020.124980; citation_id=CR8
Backstrom L, Leskovec J (2011) Supervised random walks: predicting and recommending links in social networks. In: Proceedings of the fourth ACM international conference on Web search and data mining, pp. 635–644
citation_journal_title=PhysicaA: Stat Mech Appl; citation_title=Evolution of the social network of scientific collaborations; citation_author=AL Barabâsi, H Jeong, Z N’eda, E Ravasz, A Schubert, T Vicsek; citation_volume=311; citation_issue=3–4; citation_publication_date=2002; citation_pages=590-614; citation_doi=10.1016/S0378-4371(02)00736-7; citation_id=CR10
Bhardwaj S, Niyogi R, Milani A (2011, June) Performance analysis of an algorithm for computation of betweenness centrality. In: International conference on computational science and its applications, pp 537–546. Springer, Berlin, Heidelberg
Bruna J, Zaremba W, Szlam A, LeCun Y (2013) Spectral networks and locally connected networks on graphs. arXiv preprint
http://arxiv.org/abs/arXiv:1312.6203
citation_journal_title=Sci Rep; citation_title=From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks; citation_author=CV Cannistraci, G Alanis-Lobato, T Ravasi; citation_volume=3; citation_issue=1; citation_publication_date=2013; citation_pages=1-14; citation_doi=10.1038/srep01613; citation_id=CR13
Chen H, Li X, Huang Z (2005, June) 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
citation_journal_title=IEEE Trans Knowl Data Eng; citation_title=Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation; citation_author=F Fouss, A Pirotte, J Renders, M Saerens; citation_volume=19; citation_issue=3; citation_publication_date=2007; citation_pages=355-369; citation_doi=10.1109/TKDE.2007.46; citation_id=CR15
citation_journal_title=Sociometry.; citation_title=A set of measures of centrality based upon betweenness; citation_author=L Freeman; citation_volume=40; citation_issue=1; citation_publication_date=1977; citation_pages=35-41; citation_doi=10.2307/3033543; citation_id=CR16
Gu S, Chen L (2016, November) Link prediction based on precision optimization. In: International conference on geo-informatics in resource management and sustainable ecosystem, pp. 131–141, Springer, Singapore
Hanneke S, Xing EP (2009) Network completion and survey sampling. In: Artificial intelligence and statistics, pp 209–215. PMLR
citation_journal_title=Bull Soc Vaudoise Sci Nat; citation_title=Etude comparative de la distribution florale dans une portion des Alpes et des Jura; citation_author=P Jaccard; citation_volume=37; citation_publication_date=1901; citation_pages=547-579; citation_id=CR19
Jeh G, Widom J (2002, July) Simrank: a measure of structural-context similarity. In: Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pp 538–543
citation_journal_title=IEEE Access; citation_title=A comprehensive survey for intelligent spam email detection; citation_author=A Karim, S Azam, B Shanmugam, K Kannoorpatti, M Alazab; citation_volume=7; citation_publication_date=2019; citation_pages=168261-168295; citation_doi=10.1109/ACCESS.2019.2954791; citation_id=CR21
citation_journal_title=Psychometrika; citation_title=A new status index derived from sociometric analysis; citation_author=L Katz; citation_volume=18; citation_issue=1; citation_publication_date=1953; citation_pages=39-43; citation_doi=10.1007/BF02289026; citation_id=CR22
citation_journal_title=Phys A Stat Mech Appl; citation_title=Link prediction techniques, applications, and performance: a survey; citation_author=A Kumar, SS Singh, K Singh, B Biswas; citation_volume=553; citation_publication_date=2020; citation_doi=10.1016/j.physa.2020.124289; citation_id=CR23
citation_journal_title=Phys A Stat Mech Appl; citation_title=Collaborative filtering approach to link prediction; citation_author=YL Lee, T Zhou; citation_volume=578; citation_publication_date=2021; citation_doi=10.1016/j.physa.2021.126107; citation_id=CR24
citation_journal_title=Phys. Rev. E; citation_title=Vertex similarity in networks; citation_author=EA Leicht, P Holme, ME Newman; citation_volume=73; citation_issue=2; citation_publication_date=2006; citation_doi=10.1103/PhysRevE.73.026120; citation_id=CR25
Leskovec J, Mcauley JJ (2012) Learning to discover social circles in ego networks. In: Advances in neural information processing systems, pp 539–547
citation_journal_title=J Am Soc Inf Sci Tech; citation_title=The link-prediction problem for social networks; citation_author=D Liben-Nowell, J Kleinberg; citation_volume=58; citation_issue=7; citation_publication_date=2007; citation_pages=1019-1031; citation_doi=10.1002/asi.20591; citation_id=CR27
citation_journal_title=EPL (Europhysics Letters); citation_title=Link prediction based on local random walk; citation_author=W Liu, L Lü; citation_volume=89; citation_issue=5; citation_publication_date=2010; citation_pages=58007; citation_doi=10.1209/0295-5075/89/58007; citation_id=CR28
Li P, Wang Y, Wang H, Leskovec J (2020) Distance encoding: Design provably more powerful neural networks for graph representation learning. arXiv preprint
http://arxiv.org/abs/arXiv:2009.00142
citation_title=Machine learning: a probabilistic perspective; citation_publication_date=2012; citation_id=CR30; citation_author=KP Murphy; citation_publisher=MIT Press
citation_journal_title=Eur J Neurosci; citation_title=Prediction of the main cortical areas and connections involved in the tactile function of the visual cortex by network analysis; citation_author=L Negyessy, T Nepusz, L Kocsis, F Bazso; citation_volume=23; citation_issue=7; citation_publication_date=2006; citation_pages=1919-1930; citation_doi=10.1111/j.1460-9568.2006.04678.x; citation_id=CR31
citation_journal_title=Phys Rev E; citation_title=Clustering and preferential attachment in growing networks; citation_author=ME Newman; citation_volume=64; citation_issue=2; citation_publication_date=2001; citation_doi=10.1103/PhysRevE.64.025102; citation_id=CR32
Niepert M, Ahmed M, Kutzkov K (2016, June) Learning convolutional neural networks for graphs. In: International conference on machine learning, pp 2014–2023. PMLR
citation_journal_title=Science; citation_title=Hierarchical organization of modularity in metabolic networks; citation_author=E Ravasz, AL Somera, DA Mongru, ZN Oltvai, AL Barabási; citation_volume=297; citation_issue=5586; citation_publication_date=2002; citation_pages=1551-1555; citation_doi=10.1126/science.1073374; citation_id=CR34
Rossi RA, Ahmed NK (2015) The network data repository with interactive graph analytics and visualization. In: AAAI.
http://networkrepository.com
Salton G, McGill MJ (1986) Introduction to modern information retrieval
citation_journal_title=Biol. Skar.; citation_title=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; citation_author=TA Sorensen; citation_volume=5; citation_publication_date=1948; citation_pages=1-34; citation_id=CR37
citation_journal_title=Phys A Stat Mech Appl; citation_title=Enhancing link prediction via network reconstruction; citation_author=M Wu, S Wu, Q Zhang, C Xue, H Kan, F Shao; citation_volume=534; citation_publication_date=2019; citation_pages=122346; citation_doi=10.1016/j.physa.2019.122346; citation_id=CR38
Zhang M, Li P, Xia Y, Wang K, Jin L (2021) Revisiting graph neural networks for link prediction. arXiv preprint
http://arxiv.org/abs/arXiv:2010.16103
citation_journal_title=European Phys J B; citation_title=Predicting missing links via local information; citation_author=T Zhou, L Lu, YC Zhang; citation_volume=71; citation_issue=4; citation_publication_date=2009; citation_pages=623-630; citation_doi=10.1140/epjb/e2009-00335-8; citation_id=CR40
citation_journal_title=Phys A Stat Mech Appl; citation_title=Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithms; citation_author=T Zhou, YL Lee, G Wang; citation_volume=564; citation_publication_date=2021; citation_doi=10.1016/j.physa.2020.125532; citation_id=CR41