Network Size Reduction Preserving Optimal Modularity and Clique Partition
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Network Size Reduction Preserving Optimal Modularity and Clique Partition
Original language description
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%.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10102 - Applied mathematics
Result continuities
Project
—
Continuities
S - Specificky vyzkum na vysokych skolach
Others
Publication year
2022
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
Lecture Notes in Computer Science
ISBN
9783031105210
ISSN
0302-9743
e-ISSN
1611-3349
Number of pages
15
Pages from-to
19-33
Publisher name
Springer, Cham
Place of publication
Cham
Event location
Malaga
Event date
Jan 1, 2022
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000916469700002