The Parameterized Complexity of Maximum Betweenness Centrality
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
The Parameterized Complexity of Maximum Betweenness Centrality
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA22-19557S" target="_blank" >GA22-19557S: New Frontiers in Computational Social Choice</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2024
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
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
Number of pages
13
Pages from-to
221-233
Publisher name
Springer Nature Singapore Pte Ltd.
Place of publication
—
Event location
Hong Kong
Event date
May 13, 2024
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
001288414000019