2019/12/30 by Mateusz Tarkowski, Tarkowski, Mateusz, Tomasz Michalak +3
Computer Science · Decision Sciences · Mathematics · Physics and Astronomy · #Algorithm #Artificial intelligence #Centrality #Closeness #Complex Network Analysis Techniques #Computer science #Data mining #Extension (predicate logic) #FOS: Computer and information sciences #FOS: Physical sciences #Game Theory and Applications #Game theory #Key (lock) #Link (geometry) #Mathematics #Measure (data warehouse) #Opinion Dynamics and Social Influence #Physics and Society (physics.soc-ph) #RADIUS #Selection (genetic algorithm) #Social and Information Networks (cs.SI) #Theoretical computer science #cs.SI #physics.soc-ph
paper · pdf · doi:10.48550/arxiv.1912.12846
published in arXiv (Cornell University) (Cornell University)
arxiv created 2019/12/30 · openalex publication_date 2019/12/30 · arxiv updated 2020/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08
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.