Approximate algorithms for graph clustering problem

V. P. Il'ev ; S. D. Il'eva ; A. V. Morshinin

Prikladnaâ diskretnaâ matematika, no. 3 (2019), pp. 64-77

Résumé

In the paper, the graph clustering problem is studied. For the version of the problem when the number of clusters does not exceed $3$, we develop three approximate algorithms. The first algorithm uses as a procedure the known Coleman–Saunderson–Wirth algorithm which approximately solves the similar problem when the number of clusters does not exceed $2$, and repeatedly applies a local search. On the contrary, our second algorithm is based on an original idea and does not use a local search at all. The main difference between these algorithms is the following. The first algorithm looks over all vertices of a given graph, for each vertex forms the cluster involving this vertex and all its neighbors and on the rest of the vertices forms one or two clusters using the Coleman–Saunderson–Wirth algorithm. The second algorithm looks over all ordered pairs of vertices of a given graph and for every pair forms two clusters at once, each of which contains only one vertex of this pair with some of its neighbors, placing the rest of the vertices to the third cluster (the third cluster may be empty). Finally, the third algorithm applies the local search only once to the feasible solution returned by the second one. A priori performance guarantees of all approximate algorithms are obtained, the best is equal to $(6-12/n)$ for the second and the third algorithms, where $n$ is the number of vertices of a given graph. Also, experimental comparing of the developed algorithms was carried out. Experimental testing show that running time of our second and third algorithms is essentially less than running time of the first algorithm. At the same time the third algorithm demonstrated the best results in sense of accuracy of the solutions. Thus, the third algorithm has the best characterstics both from point of view of theoretical analysis and experimental study.

Détail

Keywords: graph, clustering, approximation algorithm, performance guarantee.

Bibliographie

[1] Kulis B., Basu S., Dhillon I., Mooney R., “Semi-supervised graph clustering: a kernel approach”, Machine Learning, 74:1 (2009), 1–22 | DOI

[2] Schaeffer S. E., “Graph clustering”, Computer Science Review, 1:1 (2005), 27–64 | DOI

[3] Shamir R., Sharan R., Tsur D., “Cluster graph modification problems”, Discr. Appl. Math., 144:1-2 (2004), 173–182 | DOI | MR | Zbl

[4] Bansal N., Blum A., Chawla S., “Correlation clustering”, Machine Learning, 56 (2004), 89–113 | DOI | MR | Zbl

[5] Ben-Dor A., Shamir R., Yakhimi Z., “Clustering gene expression patterns”, J. Comput. Biol., 6:3-4 (1999), 281–297 | DOI

[6] Křivánek M., Morávek J., “NP-hard problems in hierarchical-tree clustering”, Acta Informatica, 23 (1986), 311–323 | DOI | MR

[7] Giotis I., Guruswami V., “Correlation clustering with a fixed number of clusters”, Theory of Computing, 2:1 (2006), 249–266 | DOI | MR | Zbl

[8] Ageev A. A., Il'ev V. P., Kononov A. V., Talevnin A. S., “Computational complexity of the graph approximation problem”, J. Appl. Indust. Math., 1:1 (2007), 1–8 | DOI | MR

[9] Coleman T., Saunderson J., and Wirth A., “A local-search 2-approximation for 2-correlation-clustering”, LNCS, 5193, 2008, 308–319 | Zbl

[10] Il'ev V. P., Il'eva S. D., Navrotskaya A. A., “Approximation algorithms for graph approximation problems”, J. Appl. Indust. Math., 5:4 (2011), 569–581 | DOI | MR | MR | Zbl

[11] Charikar M., Guruswami V., Wirth A., “Clustering with qualitative information”, J. Comput. Syst. Sci., 71:3 (2005), 360–383 | DOI | MR | Zbl

[12] Ailon N., Charikar M., Newman A., “Aggregating inconsistent information: Ranking and clustering”, J. ACM, 55:5 (2008), 1–27 | DOI | MR

[13] Chawla S., Makarychev K., Schramm T., Yaroslavtsev G., “Near optimal LP algorithm for correlation clustering on complete and complete $k$-partite graphs”, STOC'15 Symp. on Theory of Computing, ACM, N.Y., 2015, 219–228 | MR | Zbl

[14] Il'ev V., Il'eva S., Kononov A., “Short survey on graph correlation clustering with minimization criteria”, LNCS, 9869, 2016, 25–36 | MR | Zbl

[15] Erdös P., Spencer J., Probabilistic Methods in Combinatorics, Académiai Kiadó, Budapest, 1974

[16] Alon N., Spencer J., The Probabilistic Method, Wiley and Sons, N.Y., 1992 | MR | Zbl