Defensive Alliances in Signed Networks
Authors: Emmanuel Arrighi, Zhidan Feng, Henning Fernau, Kevin Mann, Xingqin Qi, Petra Wolf
JAIR 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Hence, we propose the novel notion of a defensive alliance in the context of signed networks. We then investigate several natural algorithmic questions related to this notion. These, and also combinatorial findings, connect our notion to that of correlation clustering, which is a well-established idea of finding groups of agents within a signed network. Also, we introduce a new structural parameter for signed graphs, the signed neighborhood diversity snd, and exhibit a snd-parameterized algorithm that finds one of the smallest defensive alliances in a signed graph. |
| Researcher Affiliation | Academia | Emmanuel Arrighi EMAIL Ens L, UCBL, CNRS, Inria, LIP UMR 5668, 69007, Lyon, France Zhidan Feng EMAIL Shandong University, School of Mathematics and Statistics 264209 Weihai, China Universit at Trier, Fachbereich 4 Abteilung Informatikwissenschaften 54286 Trier, Germany Henning Fernau EMAIL Kevin Mann EMAIL Universit at Trier, Fachbereich 4 Abteilung Informatikwissenschaften 54286 Trier, Germany Xingqin Qi EMAIL Shandong University, School of Mathematics and Statistics 264209 Weihai, China Petra Wolf EMAIL Universit e de Bordeaux, CNRS, Bordeaux INP, La BRI UMR 5800, 33400, Talence, France |
| Pseudocode | No | The paper describes algorithms (e.g., a polynomial-time algorithm for Defensive Alliance Building, and a dynamic programming algorithm for combined parameters) and their logic, but it does not present them in formal pseudocode blocks or clearly labeled algorithm sections with structured steps. |
| Open Source Code | No | Since the publication of the first report version of this paper, a group of students (Sebastian et al., 2024) implemented and tested some of the polynomial-time algorithms presented in this paper, most notably, the one on building alliances. |
| Open Datasets | No | The paper mentions examples like "Correlates of War data" and ethnographic descriptions from "Read (1954)" to illustrate the relevance of their theoretical concepts. However, it does not conduct empirical studies or use these as datasets for experimental evaluation, and therefore does not provide specific access information for such purposes. |
| Dataset Splits | No | The paper does not present any empirical experiments or data analysis, and therefore does not provide information regarding dataset splits. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithmic complexity and combinatorial analysis. It does not describe any experiments that would require specific hardware, hence no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and does not describe any specific software implementations or experimental setups. Therefore, it does not list software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithmic complexity and combinatorial analysis. It does not describe any experiments or specific model training, and thus does not provide details on experimental setup or hyperparameters. |