Partitioning networks into cliques: a randomized heuristic approach

Chalupa, David

Abstract

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.

Citation

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: https://hull-repository.worktribe.com/output/438341
• Publisher URL: http://acmbulletin.fiit.stuba.sk/vol6num3/chalupa2014.pdf
• 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.