Interpretable Link Prediction Based On Visual Analytics

Link Prediction is a challenging area in network research.Over the past two decades,various methods have been used to address the problem of link prediction in different branches of computer science,and similarity-based analysis methods have received much attention due to their lower time complexity,higher prediction accuracy,and interpretability.These methods use the characteristics of nodes and their connections to compute the similarity between node pairs and compare them.However,existing similarity indices often fail to effectively capture high-order structural information around nodes,and lack constraints on other attributes when analyzing low-order structural information,affecting their prediction accuracy.In this thesis,starting from the perspective of physical concepts and combining theories such as Resource Allocation(RA)and Local Community Paradigm(LCP),a link prediction index with high interpretability and prediction accuracy is proposed.High-order structural information of nodes is captured based on the index,and the index is extended to a larger neighborhood.Experimental results show that the proposed index performs much better than existing indices.Additionally,a link prediction visualization and analysis system is proposed to provide an intuitive and interactive interface for exploring and analyzing link prediction results.Users can choose different indices and datasets and visualize the link prediction process and results through multiple views.The main contributions of this thesis are as follows.(1)Starting from physical concepts and combining RA and LCP theory,an Effective Resource Transfer Ratio(ERTR)index with strong interpretability is proposed to analyze the transfer of effective and ineffective resources in link prediction resource allocation.Experimental results show that the ERTR index outperforms other baseline indices.(2)To capture high-order structural information and improve prediction accuracy,while maintaining the strong interpretability of the index,the ERTR index is extended to a larger local neighborhood and a Local Effective Resource Transfer Ratio(LERTR)index is proposed.The contribution of second-order common neighbors is controlled by introducing parameters.Experimental results show that the LERTR index outperforms other baseline indices more significantly.(3)A link prediction visualization and analysis system,LPExplorer,is designed to provide an intuitive and interactive interface for exploring and analyzing link prediction results.Multiple visual encodings are designed to assist in expressing different visualization tasks.(4)The functionality of the system is evaluated through multiple case studies on real datasets.The validity and reliability of the system are demonstrated through multi-view explanations and analyses of the link prediction process and results.