Partitioning networks into cliques: a randomized heuristic approach
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|
|Deposit Date||May 18, 2016|
|Publicly Available Date||May 18, 2016|
|Journal||Information sciences and technologies bulletin of the ACM Slovakia|
|Peer Reviewed||Peer Reviewed|
|Keywords||Clique covering problem, Heuristic algorithms, Complex networks, Iterated greedy, Community detection|
|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.|
© 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
Analysis of an iterated greedy heuristic for vertex clique covering
Computational methods for finding long simple cycles in complex networks
Construction of near-optimal vertex clique covering for real-world networks