Network Size Reduction Preserving Optimal Modularity and Clique Partition

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14310%2F22%3A00128549" target="_blank" >RIV/00216224:14310/22:00128549 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-031-10522-7_2" target="_blank" >https://doi.org/10.1007/978-3-031-10522-7_2</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-031-10522-7_2" target="_blank" >10.1007/978-3-031-10522-7_2</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Network Size Reduction Preserving Optimal Modularity and Clique Partition

Popis výsledku v původním jazyce

Graph clustering and community detection are significant and actively developing topics in network science. Uncovering community structure can provide essential information about the underlying system. In this work, we consider two closely related graph clustering problems. One is the clique partitioning problem, and the other is the maximization of partition quality function called modularity. We are interested in the exact solution. However, both problems are NP-hard. Thus the computational complexity of any existing algorithm makes it impossible to solve the problems exactly for the networks larger than several hundreds of nodes. That is why even a small reduction of network size can significantly improve the speed of finding the solution to these problems. We propose a new method for reducing the network size that preserves the optimal partition in terms of modularity score or the clique partitioning objective function. Furthermore, we prove that the optimal partition of the reduced network has the same quality as the optimal partition of the initial network. We also address the cases where a previously proposed method could provide incorrect results. Finally, we evaluate our method by finding the optimal partitions for two sets of networks. Our results show that the proposed method reduces the network size by 40% on average, decreasing the computation time by about 54%.

Název v anglickém jazyce

Network Size Reduction Preserving Optimal Modularity and Clique Partition

Popis výsledku anglicky

Graph clustering and community detection are significant and actively developing topics in network science. Uncovering community structure can provide essential information about the underlying system. In this work, we consider two closely related graph clustering problems. One is the clique partitioning problem, and the other is the maximization of partition quality function called modularity. We are interested in the exact solution. However, both problems are NP-hard. Thus the computational complexity of any existing algorithm makes it impossible to solve the problems exactly for the networks larger than several hundreds of nodes. That is why even a small reduction of network size can significantly improve the speed of finding the solution to these problems. We propose a new method for reducing the network size that preserves the optimal partition in terms of modularity score or the clique partitioning objective function. Furthermore, we prove that the optimal partition of the reduced network has the same quality as the optimal partition of the initial network. We also address the cases where a previously proposed method could provide incorrect results. Finally, we evaluate our method by finding the optimal partitions for two sets of networks. Our results show that the proposed method reduces the network size by 40% on average, decreasing the computation time by about 54%.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10102 - Applied mathematics

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2022

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

Lecture Notes in Computer Science

ISBN

9783031105210

ISSN

0302-9743

e-ISSN

1611-3349

Počet stran výsledku

15

Strana od-do

19-33

Název nakladatele

Springer, Cham

Místo vydání

Cham

Místo konání akce

Malaga

Datum konání akce

1. 1. 2022

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

WRD - Celosvětová akce

Kód UT WoS článku

000916469700002