The Parameterized Complexity of Maximum Betweenness Centrality

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F24%3A00372064" target="_blank" >RIV/68407700:21240/24:00372064 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-981-97-2340-9_19" target="_blank" >https://doi.org/10.1007/978-981-97-2340-9_19</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-981-97-2340-9_19" target="_blank" >10.1007/978-981-97-2340-9_19</a>

Jazyk výsledku

angličtina

Název v původním jazyce

The Parameterized Complexity of Maximum Betweenness Centrality

Popis výsledku v původním jazyce

Arguably, one of the most central tasks in the area of social network analysis is to identify important members and communities of a given network. The importance of an agent is traditionally measured using some well-defined notion of centrality. In this work, we focus on betweenness centrality, which is based on the number of shortest paths that an agent intersects. This measure can be naturally generalized from a single agent to a group of agents. Specifically, we study the computation complexity of the k-Maximum Betweenness Centrality problem, which consists in finding a group of size $k$ whose betweenness centrality exceeds a given threshold. Since this problem is NP-complete in general, we use the framework of parameterized complexity to reveal at least some tractable fragments. From this perspective, we show that the problem is W[1]-hard and in XP when parameterized by the group size $k$. As the threshold value is not a useful parameter in this context, we focus on the structural restrictions of the underlying social network. In this direction, we show that the problem admits FPT algorithms with respect to the vertex cover number, the distance to clique, or the twin-cover number and the group size combined.

Název v anglickém jazyce

The Parameterized Complexity of Maximum Betweenness Centrality

Popis výsledku anglicky

Arguably, one of the most central tasks in the area of social network analysis is to identify important members and communities of a given network. The importance of an agent is traditionally measured using some well-defined notion of centrality. In this work, we focus on betweenness centrality, which is based on the number of shortest paths that an agent intersects. This measure can be naturally generalized from a single agent to a group of agents. Specifically, we study the computation complexity of the k-Maximum Betweenness Centrality problem, which consists in finding a group of size $k$ whose betweenness centrality exceeds a given threshold. Since this problem is NP-complete in general, we use the framework of parameterized complexity to reveal at least some tractable fragments. From this perspective, we show that the problem is W[1]-hard and in XP when parameterized by the group size $k$. As the threshold value is not a useful parameter in this context, we focus on the structural restrictions of the underlying social network. In this direction, we show that the problem admits FPT algorithms with respect to the vertex cover number, the distance to clique, or the twin-cover number and the group size combined.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA22-19557S" target="_blank" >GA22-19557S: Nové výzvy ve výpočetní socální volbě</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 18th Annual Conference on Theory and Applications of Models of Computation, TAMC 2024

ISBN

978-981-97-2339-3

ISSN

0302-9743

e-ISSN

1611-3349

Počet stran výsledku

13

Strana od-do

221-233

Název nakladatele

Springer Nature Singapore Pte Ltd.

Místo vydání

—

Místo konání akce

Hong Kong

Datum konání akce

13. 5. 2024

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

001288414000019