On a semi-superwized graph clustering problem

A. V. Ilev ; V. P. Il'ev

Prikladnaâ diskretnaâ matematika, no. 4 (2018), pp. 66-75.

Résumé

In the clustering problems one has to partition a given set of objects into some subsets (called clusters) taking into consideration only similarity of the objects. In this paper we study a version of the graph correlation clustering that can be considered as a formalization of the semi-supervised clustering. We prove that the problem under consideration is NP-hard and propose a polynomial-time 3-approximation algorithm for a version of the problem.

Détail

Keywords: graph, cluster, semi-supervised clustering.

Bibliographie

[1] Zhuravlev Yu. I., Ryazanov V. V., Sen'ko O. V., Recognition. Mathematical methods. Program system. Practical applications, FAZIS Publ., M., 2005 (in Russian)

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

[3] Schaeffer S. E., “Graph clustering”, Comput. Sci. Rev., 1:1 (2005), 27–64 | DOI

[4] Bair E., “Semi-supervised clustering methods”, Wiley Interdisciplinary Reviews: Computational Statistics, 5:5 (2013), 349–361 | DOI

[5] Chapelle O., Schölkopf B., Zein A., Semi-supervised Learning, MIT Press, Cambridge, Massachusets, 2006

[6] Ilev A. V., Remeslennikov V. N., “Study of the compatibility of systems of equations over graphs and finding their general solutions”, Vestnik Omskogo Universiteta, 2017, no. 4(86), 26–32 (in Russian)

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

[8] Zahn C. T., “Approximating symmetric relations by equivalence relations”, J. Soc. Indust. Appl. Math., 12:4 (1964), 840–847 | DOI | MR | Zbl

[9] Tomescu I., “La reduction minimale d'un graphe à une reunion de cliques”, Discrete Math., 10:1–2 (1974), 173–179 | DOI | MR | Zbl

[10] Fridman G. Sh., “Investigation of a classifying problem on graphs”, Metody Modelirovaniya i Obrabotka Informatsii, Nauka Publ., Novosibirsk, 1976, 147–177 (in Russian)

[11] Il'ev V. P., Fridman G. Sh., “On the problem of approximation by graphs with a fixed number of components”, Sov. Math. Dokl., 25 (1982), 666–670 | MR | Zbl

[12] Bansal N., Blum A., Chawla S., “Correlation clustering”, Mach. Learn., 56:1–3 (2004), 89–113 | DOI | MR | Zbl

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

[14] Il'ev V. P., Navrotskaya A. A., “Computational complexity of the problem of approximation by graphs with connected components of bounded size”, Prikladnaya Diskretnaya Matematika, 2011, no. 3(13), 80–84 (in Russian)

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

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

[17] 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

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

[19] 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

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

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

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