Network Size Reduction Preserving Optimal Modularity and Clique
Partition

D 2022

Network Size Reduction Preserving Optimal Modularity and Clique Partition

BELY, Aliaksandr a Stanislav SOBOLEVSKY

Základní údaje

Originální název

Network Size Reduction Preserving Optimal Modularity and Clique Partition

Autoři

BELY, Aliaksandr (112 Bělorusko, garant, domácí) a Stanislav SOBOLEVSKY (112 Bělorusko, domácí)

Vydání

Cham, Lecture Notes in Computer Science, od s. 19-33, 15 s. 2022

Nakladatel

Springer, Cham

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10102 Applied mathematics

Stát vydavatele

Švýcarsko

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Odkazy

URL

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14310/22:00128549

Organizační jednotka

Přírodovědecká fakulta

ISBN

978-3-031-10521-0

ISSN

DOI

http://dx.doi.org/10.1007/978-3-031-10522-7_2

UT WoS

000916469700002

Klíčová slova anglicky

Network size reduction Clustering Community detection Modularity Clique partitioning problem Exact solution

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 1. 3. 2023 11:52, Mgr. Marie Šípková, DiS.

Anotace

V originále

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ávaznosti

MUNI/J/0008/2021, interní kód MU

Název: Digital City

Investor: Masarykova univerzita, Digital City, MASH JUNIOR - MUNI Award In Science and Humanities JUNIOR

Citovat

BELY, Aliaksandr a Stanislav SOBOLEVSKY. Network Size Reduction Preserving Optimal Modularity and Clique Partition. In Gervasi, O., Murgante, B., Hendrix, E.M.T., Taniar, D., Apduhan, B.O. Lecture Notes in Computer Science. Cham: Springer, Cham, 2022, s. 19-33. ISBN 978-3-031-10521-0. Dostupné z: https://dx.doi.org/10.1007/978-3-031-10522-7_2.

@inproceedings{2252583,
   author = {Bely, Aliaksandr and Sobolevsky, Stanislav},
   address = {Cham},
   booktitle = {Lecture Notes in Computer Science},
   doi = {http://dx.doi.org/10.1007/978-3-031-10522-7_2},
   editor = {Gervasi, O., Murgante, B., Hendrix, E.M.T., Taniar, D., Apduhan, B.O.},
   keywords = {Network size reduction Clustering Community detection Modularity Clique partitioning problem Exact solution},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Cham},
   isbn = {978-3-031-10521-0},
   pages = {19-33},
   publisher = {Springer, Cham},
   title = {Network Size Reduction Preserving Optimal Modularity and Clique Partition},
   url = {https://doi.org/10.1007/978-3-031-10522-7_2},
   year = {2022}
}

TY  - JOUR
ID  - 2252583
AU  - Bely, Aliaksandr - Sobolevsky, Stanislav
PY  - 2022
TI  - Network Size Reduction Preserving Optimal Modularity and Clique Partition
PB  - Springer, Cham
CY  - Cham
SN  - 9783031105210
KW  - Network size reduction Clustering Community detection Modularity Clique partitioning problem Exact solution
UR  - https://doi.org/10.1007/978-3-031-10522-7_2
N2  - 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%.
ER  -

BELY, Aliaksandr a Stanislav SOBOLEVSKY. Network Size Reduction Preserving Optimal Modularity and Clique Partition. In Gervasi, O., Murgante, B., Hendrix, E.M.T., Taniar, D., Apduhan, B.O. \textit{Lecture Notes in Computer Science}. Cham: Springer, Cham, 2022, s.~19-33. ISBN~978-3-031-10521-0. Dostupné z: https://dx.doi.org/10.1007/978-3-031-10522-7\_{}2.

Podrobný výpis o publikaci