The Game-Theoretic Interaction Index on Social Networks with Applications to Link Prediction and Community Detection

Piotr Lech Szczepanski, Aleksy Stanislaw Barcz, Tomasz Pawel Michalak, Talal RahwanIJCAI 2015

Abstract

This paper introduces a novel node-similarity measure for social networks rooted in coalitional game theory. By modeling a network as an "influence game," the authors demonstrate that the traditionally hard-to-compute interaction index can be calculated in polynomial time, outperforming standard local similarity measures in link prediction and community detection tasks.

Introduction

In network analysis, determining how "similar" two nodes are is a foundational task used to predict future friendships (link prediction) or group users into clusters (community detection). Existing similarity measures generally fall into two camps: global measures, which are accurate but computationally expensive, and local measures, which are fast but often too simplistic to capture complex relationships. This research seeks a "middle ground": a measure that captures the nuanced synergy between nodes while remaining computationally efficient enough for real-world applications.

Methodology

The authors bridge the gap between game theory and graph theory using three key steps:

1. The Influence Game

They define a coalitional game where nodes are "players." The payoff of a group (coalition) of nodes is the size of its "sphere of influence"—the set of all nodes within $k$ steps of the group.

2. The Interaction Index

They use the game-theoretic interaction index (a generalization of the Shapley value) to measure the synergy between two nodes. Synergy represents the additional influence gained when two nodes cooperate, averaged over all possible coalitions. In this model, high negative synergy indicates that two nodes' spheres of influence overlap significantly, meaning they are "functionally" similar within the network.

3. Polynomial-Time Algorithm

While calculating interaction indices is typically NP-hard, the authors provide a combinatorial proof showing that for their specific "influence game," the index can be computed in $O(|V|^2)$ time. For the Semivalue Interaction Index (SvII), the complexity drops to $O(|V|)$ per pair, matching the speed of the fastest local measures in the literature.

Experimental Evaluation

The researchers evaluated their measure on seven diverse, real-life networks, including the Zachary karate club, bottlenose dolphin associations, US political book networks, and large-scale communication patterns (Emails).

Key Results and Analysis

The proposed SvII measure outperformed seven other standard measures (including Jaccard Index and Adamic-Adar) on the majority of the tested networks. This is partly due to a mathematical shift in how influence is distributed: while popular indices like Resource Allocation (RA) assume a node distributes resources equally, the game-theoretic approach accounts for the fact that a node does not "send back" influence to the original sender.

Community Detection and Multi-resolution

Using hierarchical clustering, the SvII measure consistently yielded community structures with higher modularity compared to other local measures. By adjusting the parameter $k$ (the steps of influence), the measure acts as a "zoom lens," allowing for community detection at different scales.

Hierarchical clustering dendrograms for different influence steps (k=2 and k=3), illustrating the multi-resolution capability of the interaction index.

The visual results of community detection demonstrate the method's ability to partition complex networks into meaningful groups at different scales, from fine-grained clusters to broader divisions.

Comparison of community detection results on a network graph, showing how the interaction index can identify both fine-grained and coarse-grained structures.

Limitations and Future Work

The results are sensitive to the choice of $k$; if $k$ is too small, interactions are missed, while a $k$ that is too large introduces noise. Future work could explore other game-theoretic models, such as those based on betweenness centrality or connectivity games, and extend the empirical testing to weighted real-world datasets.

Summary updated

BibTeX
@inproceedings{szczepanski2015game,
  author = {Piotr Lech Szczepanski and Aleksy Stanislaw Barcz and Tomasz Pawel Michalak and Talal Rahwan},
  title = {{The Game-Theoretic Interaction Index on Social Networks with Applications to Link Prediction and Community Detection}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure