2019/12/30 by Mateusz Tarkowski, Tarkowski, Mateusz, Tomasz Michalak +3
Decision Sciences · Physics and Astronomy · #Complex Network Analysis Techniques #FOS: Computer and information sciences #FOS: Physical sciences #Game Theory and Applications #Opinion Dynamics and Social Influence #Physics and Society (physics.soc-ph) #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.1912.12846
openalex publication_date 2019/12/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Predicting edges in networks is a key problem in social network analysis and involves reasoning about the relationships between nodes based on the structural properties of a network. In particular, link prediction can be used to analyse how a network will develop or - given incomplete information about relationships - to discover "missing" links. Our approach to this problem is rooted in cooperative game theory, where we propose a new, quasi-local approach (i.e., one which considers nodes within some radius k) that combines generalised group closeness centrality and semivalue interaction indices. We develop fast algorithms for computing our measure and evaluate it on a number of real-world networks, where it outperforms a selection of other state-of-the-art methods from the literature. Importantly, choosing the optimal radius k for quasi-local methods is difficult, and there is no assurance that the choice is optimal. Additionally, when compared to other quasi-local methods, ours achieves very good results even when given a suboptimal radius k as a parameter.