Skip to main content

Research Repository

Advanced Search

Partitioning networks into cliques: a randomized heuristic approach

Chalupa, David


David Chalupa


In the context of community detection in social networks, the term community can be grounded in the strict way that simply everybody should know each other within the community. We consider the corresponding community detection problem. We search for a partitioning of a network into the minimum number of non-overlapping cliques, such that the cliques cover all vertices. This problem is called the clique covering problem (CCP) and is one of the classical NP-hard problems. For CCP, we propose a randomized heuristic approach. To construct a high quality solution to CCP, we present an iterated greedy (IG) algorithm. IG can also be combined with a heuristic used to determine how far the algorithm is from the optimum in the worst case. Randomized local search (RLS) for maximum independent set was proposed to find such a bound. The experimental results of IG and the bounds obtained by RLS indicate that IG is a very suitable technique for solving CCP in real-world graphs. In addition, we summarize our basic rigorous results, which were developed for analysis of IG and understanding of its behavior on several relevant graph classes.


Chalupa, D. (2014). Partitioning networks into cliques: a randomized heuristic approach. Information Sciences and Technologies Bulletin of the ACM Slovakia, 6(3), 1-8

Journal Article Type Article
Acceptance Date Jun 25, 2014
Publication Date 2014
Deposit Date May 18, 2016
Publicly Available Date May 18, 2016
Journal Information sciences and technologies bulletin of the ACM Slovakia
Electronic ISSN 1338-6654
Peer Reviewed Peer Reviewed
Volume 6
Issue 3
Pages 1-8
Keywords Clique covering problem, Heuristic algorithms, Complex networks, Iterated greedy, Community detection
Public URL
Publisher URL
Additional Information This is a copy of an article published in Information sciences and technologies bulletin of the ACM Slovakia, 2014, v.6 issue 3.


Article.pdf (313 Kb)

Copyright Statement
© Copyright 2014. All rights reserved. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works requires prior specific permission and/or a fee. Permissions may be requested from STU Press, Vazovova 5, 811 07 Bratislava, Slovakia.

You might also like

Downloadable Citations