Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Algorithmic Issues in Energy-Efficient Computation Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Short Survey on Graph Correlation Clustering with Minimization Criteria

verfasst von : Victor Il’ev, Svetlana Il’eva, Alexander Kononov

Erschienen in: Discrete Optimization and Operations Research

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In clustering problems one has to partition a given set of objects into some subsets (called clusters) taking into consideration only similarity of the objects. One of the most visual formalizations of clustering is the graph clustering, that is, grouping the vertices of a graph into clusters taking into consideration the edge structure of the graph whose vertices are objects and edges represent similarities between the objects.
In this short survey, we consider the graph correlation clustering problems where the goal is to minimize the number of edges between clusters and the number of missing edges inside clusters. We present a number of results on graph correlation clustering including results on computational complexity and approximability of different variants of the problems, and performance guarantees of approximation algorithms for graph correlation clustering. Some results on approximability of weighted versions of graph correlation clustering are also presented.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Linear Superiorization for Infeasible Linear Programming
Nächstes Kapitel Wardrop Equilibrium for Networks with the BPR Latency Function
Literatur
1.
Ageev, A.A., II’ev, V.P., Kononov, A.V., Talevnin, A.S.: Computational complexity of the graph approximation problem. Diskretnyi Analiz i Issledovanie Operatsii. Ser. 1 13(1), 3–11 (2006). (in Russian). English transl. in: J. Appl. Ind. Math. 1(1), 1–8 (2007)
2.
Ailon, N., Charikar, M., Newman, A.: Aggregating inconsistent information: ranking and clustering. J. ACM 55(5), 1–27 (2008)MathSciNetCrossRefMATH
3.
Bachrach, Y., Kohli, P., Kolmogorov, V., Zadimoghaddam, M.: Optimal coalition structure generation in cooperative graph games. In: 27th AAAI Conference on Artificial Intelligence, pp. 81–87. AAAI Press (2013)
4.
5.
Bastos, L., Ochi, L.S., Protti, F., Subramanian, A., Martins, I.C., Pinheiro, R.G.S.: Efficient algorithms for cluster editing. J. Comb. Optim. 31, 347–371 (2016)MathSciNetCrossRefMATH
6.
Ben-Dor, A., Shamir, R., Yakhimi, Z.: Clustering gene expression patterns. J. Comput. Biol. 6(3–4), 281–297 (1999)CrossRef
7.
8.
Bonizzoni, P., Vedova, G.D., Dondi, R., Jiang, T.: On the approximation of correlation clustering and consensus clustering. J. Comput. Syst. Sci. 74, 671–696 (2008)MathSciNetCrossRefMATH
9.
Böcker, S., Baumbach, J.: Cluster editing. In: Bonizzoni, P., Brattka, V., Löwe, B. (eds.) CiE 2013. LNCS, vol. 7921, pp. 33–44. Springer, Heidelberg (2013)
10.
Charikar, M., Guruswami, V., Wirth, A.: Clustering with qualitative information. J. Comput. Syst. Sci. 71(3), 360–383 (2005)MathSciNetCrossRefMATH
11.
Chen, Z.-Z., Jiang, T., Lin, G.: Computing phylogenetic roots with bounded degrees and errors. SIAM J. Comput. 32(4), 864–879 (2003)MathSciNetCrossRefMATH
12.
Coleman, T., Saunderson, J., Wirth, A.: A local-search 2-approximation for 2-correlation-clustering. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol. 5193, pp. 308–319. Springer, Heidelberg (2008)CrossRef
13.
Demaine, E., Emanuel, D., Fiat, A., Immorlica, V.: Correlation clustering in general weighted graphs. Theoret. Comput. Sci. 361, 172–187 (2006)MathSciNetCrossRefMATH
14.
Filkov, V., Skiena, S.: Integrating microarray data by Consensus clustering. In: 15th IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp. 418–425 (2003)
15.
Fridman, G.Š.: A graph approximation problem. Upravlyaemye Sistemy 8, 73–75 (1971). (in Russian)
16.
Fridman, G.Š.: On an inequality in the graph approximation problem. Kibernetika 3, 151 (1974). (in Russian). English transl. in: Cybernetics 10, 554 (1974)
17.
Fridman, G.Š.: Analysis of a classification problem on graphs. Metody Modelirovaniya i Obrabotka Informatsii, pp. 147–177. Nauka, Novosibirsk (1976). (in Russian)
18.
19.
Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer Series in Statistics. Springer, New York (2009)CrossRefMATH
20.
Harary, F.: On the notion of balance of a signed graph. Michigan Math. J. 2, 143–146 (1955)MathSciNetMATH
21.
II’ev, V.P., Fridman G.Š,: On the problem of approximation by graphs with fixed number of components. Doklady AN SSSR 264(3), 533–538 (1982). (in Russian). English transl. in: Soviet Math. Dokl. 25(3), 666–670 (1982)
22.
II’ev, V.P., Navrotskaya, A.A., Talevnin, A.S.: Polynomial time approximation scheme for the graph approximation problem. Vestnik Omskogo Universiteta 4, 24–27 (2007). (in Russian)
23.
II’ev, V.P., II’eva, S.D., Navrotskaya, A.A.: Approximation algorithms for graph approximation problems. Diskretnyi Analiz i Issledovanie Operatsii 18(1), 41–60 (2011). (in Russian). English transl. in: J. Appl. Ind. Math. 5(4), 1–15 (2011)
24.
Klein, P.N., Mathieu, C., Zhou, H.: Correlation clustering and two-edge-connected augmentation for planar graphs. In: 32nd Symposium on Theoretical Aspects of Computer Science (STACS 2015. Leibniz International Proceedings in Informatics (LIPIcs), vol. 30, pp. 554–567. Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, Saarbrücken/Wadern (2015)
25.
Komusiewicz, C., Uhlmann, J.: Cluster editing with locally bounded modifications. Discrete Appl. Math. 160(15), 2259–2270 (2012)MathSciNetCrossRefMATH
26.
27.
Kulis, B., Basu, S., Dhillon, I., Mooney, R.: Semi-supervised graph clustering: a kernel approach. Mach. Learn. 74(1), 1–22 (2009)CrossRef
28.
Lyapunov, A.A.: The structure and evolution of the control systems in connection with the theory of classification. Problemy Kibernetiki 27, 7–18 (1973). Nauka, Moscow (in Russian)MathSciNet
29.
Mannaa, B.: Cluster editing problem for points on the real line: a polynomial time algorithm. Inform. Process. Lett. 110, 961–965 (2010)MathSciNetCrossRef
30.
Navrotskaya, A.A., II’ev, V.P., Talevnin, A.S.: Asymptotically exact algorithm for the problem of approximation of nondense graphs. In: III All-Russian Conference “Problemy Optimizatsii i Ekonomicheskiye Prilozheniya”, p. 115. Izd. OmGTU, Omsk (2006). (in Russian)
31.
Rahmann, S., Wittkop, T., Baumbach, J., Martin, M., Truß, A., Böcker, S.: Exact and heuristic algorithms for weighted cluster editing. In: 6th Annual International Conference on Computational Systems Bioinformatics (CSB 2007), vol. 6, pp. 391–401. Imperial College Press, London (2007)
32.
33.
34.
Tomescu, I.: Note sur une caractérisation des graphes done le degreé de deséquilibre est maximal. Mathematiques et Sciences Humaines 42, 37–40 (1973)MathSciNetMATH
35.
36.
Tyshkevich, R.I.: Matroidal decompositions of a graph. Diskretnaya Matematika 1(3), 129–139 (1989). (in Russian)MathSciNetMATH
37.
Voice, T., Polukarov, M., Jennings, N.R.: Coalition structure generation over graphs. J. Artif. Intell. Res. 45, 165–196 (2012)MathSciNetMATH
38.
Wakabayashi, Y.: The complexity of computing defians of relations. Resenhas 3(3), 323–349 (1998)MathSciNetMATH
39.
Xin, X.: An FPT algorithm for the correlation clustering problem. Key Eng. Mater. Adv. Mater. Comput. Sci. 474–476, 924–927 (2011)CrossRef
40.
41.
van Zuylen, A., Williamson, D.P.: Deterministic pivoting algorithms for constrained ranking and clustering problems. Math. Oper. Res. 34(3), 594–620 (2009)MathSciNetCrossRefMATH
Metadaten
Titel
Short Survey on Graph Correlation Clustering with Minimization Criteria
verfasst von
Victor Il’ev
Svetlana Il’eva
Alexander Kononov
Copyright-Jahr
2016
Buch
Discrete Optimization and Operations Research

Print ISBN: 978-3-319-44913-5

Electronic ISBN: 978-3-319-44914-2

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-44914-2_3