Efficient Computation of Semivalues for Game-Theoretic Network Centrality
Authors: Mateusz K. Tarkowski, Piotr L. Szczepański, Tomasz P. Michalak, Paul Harrenstein, Michael Wooldridge
JAIR 2018 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this article, we show that these results can be extended to a much larger class of centrality measures that are based on a family of solution concepts known as semivalues. The family of semivalues includes, among others, the Shapley value and the Banzhaf index. To this end, we present a generic framework for defining game-theoretic network centralities and prove that all centrality measures that can be expressed in this framework are computable in polynomial time. Using our framework, we present a number of new and polynomial-time computable game-theoretic centrality measures. |
| Researcher Affiliation | Collaboration | Mateusz K. Tarkowski EMAIL Department of Computer Science, University of Oxford OX1 3QD, United Kingdom Piotr L. Szczepa nski EMAIL Nykredit / BEC Poland 00-113 Warsaw, Poland |
| Pseudocode | Yes | Algorithm 1: (SEMI) The semivalue-based centrality Algorithm 2: General Banzhaf Centrality Algorithm 3: The parametrised degree centrality Algorithm 4: Dijkstra algorithm for computing distance and counting shortest paths Algorithm 5: The parametrised betweenness centrality Algorithm 6: The parametrised closeness centrality |
| Open Source Code | No | The paper does not explicitly state that source code for the described methodology is being released, nor does it provide a direct link to a code repository. A website "www.game-theoretic-centrality.com" is mentioned in a footnote for a broader overview of applications, but not for code. |
| Open Datasets | No | The paper uses illustrative examples of networks (e.g., "Figure 1: A sample unweighted network of 5 nodes", "Figure 2: A graph representing a delivery network"), but does not refer to any specific publicly available or open datasets with concrete access information (links, DOIs, citations). |
| Dataset Splits | No | The paper is theoretical and does not perform experiments on specific datasets requiring training, validation, or test splits. Therefore, no dataset split information is provided. |
| Hardware Specification | No | The paper focuses on theoretical computational analysis and algorithms. It does not describe any experimental setup involving specific hardware components like GPUs, CPUs, or other computational resources. |
| Software Dependencies | No | The paper discusses algorithms (e.g., BFS, Dijkstra) but does not specify any software libraries, frameworks, or solvers with version numbers that would be necessary for reproduction. |
| Experiment Setup | No | The paper is theoretical, presenting frameworks and algorithms for computational analysis. It does not describe empirical experiments with specific hyperparameters, training configurations, or system-level settings. |