Construction of Near-Optimal Vertex Clique Covering for Real-World Networks
David Chalupa; Institute of Applied Informatics, Faculty of Informatics and Information Technologies, Slovak University of Technology, 842 16 Bratislava
Computing and Informatics, Tome 34 (2016) no. 4, / Harvested from Computing and Informatics
We propose a method based on combining a constructive and a bounding heuristic to solve the vertex clique covering problem (CCP), where the aim is to partition the vertices of a graph into the smallest number of classes, which induce cliques. Searching for the solution to CCP is highly motivated by analysis of social and other real-world networks, applications in graph mining, as well as by the fact that CCP is one of the classical NP-hard problems. Combining the construction and the bounding heuristic helped us not only to find high-quality clique coverings but also to determine that in the domain of real-world networks, many of the obtained solutions are optimal, while the rest of them are near-optimal. In addition, the method has a polynomial time complexity and shows much promise for its practical use. Experimental results are presented for a fairly representative benchmark of real-world data. Our test graphs include extracts of web-based social networks, including some very large ones, several well-known graphs from network science, as well as coappearance networks of literary works' characters from the DIMACS graph coloring benchmark. We also present results for synthetic pseudorandom graphs structured according to the Erdös-Renyi model and Leighton's model.
Publié le : 2016-03-02
Classification:  other areas of Computing and Informatics,  Clique covering, independent set, community detection, stochastic algorithms, heuristics,  90C59; 05B40; 05C69
@article{cai1276,
     author = {David Chalupa; Institute of Applied Informatics, Faculty of Informatics and Information Technologies, Slovak University of Technology, 842 16 Bratislava},
     title = {Construction of Near-Optimal Vertex Clique Covering for Real-World Networks},
     journal = {Computing and Informatics},
     volume = {34},
     number = {4},
     year = {2016},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai1276}
}
David Chalupa; Institute of Applied Informatics, Faculty of Informatics and Information Technologies, Slovak University of Technology, 842 16 Bratislava. Construction of Near-Optimal Vertex Clique Covering for Real-World Networks. Computing and Informatics, Tome 34 (2016) no. 4, . http://gdmltest.u-ga.fr/item/cai1276/