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
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Modularity of the ABCD Random Graph Model with Community Structure Kapitel lesen Erstes Kapitel lesen

2023 | OriginalPaper | Buchkapitel

A More Powerful Heuristic for Balancing an Unbalanced Graph

verfasst von : Sukhamay Kundu, Amit A. Nanavati

Erschienen in: Complex Networks and Their Applications XI

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We present a more powerful heuristic algorithm for the NP-complete problem of finding a minimum size subset of edges in an unbalanced signed graph G whose ‘+’/‘−’ labels can be flipped to balance G. Our algorithm finds a minimal flipping edge-set, starting with a given spanning tree T of G, by considering both the edges not in T and those in T because flipping a tree-edge can sometimes balance multiple fundamental unbalanced cycles at the same time. This can give a much smaller minimal flipping edge-set than the current algorithm where only the edges not in T are considered for flipping.

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 Learning Attribute Distributions Through Random Walks
Nächstes Kapitel DC-RST: A Parallel Algorithm for Random Spanning Trees in Network Analytics
Literatur
1.
Aref, S., Neal, Z.: Detecting coalitions by optimally partitioning signed networks of political collaboration. Sci. Rep. 10(1), 1–10 (2020)CrossRef
2.
Cartwright, D., Harary, F.: Structural balance: a generalization of Heider’s theory. Psychol. Rev. 63(5), 277 (1956)
3.
Ma’ayan, A., Lipshtat, A., Iyengar, R., Sontag, E.D.: Proximity of intracellular regulatory networks to monotone systems. IET Syst. Biol. 2(3), 103–112 (2008)CrossRef
4.
Harary, F.: On the notion of balance of a signed graph. Michigan Math. J. 2(2), 143–146 (1953)
5.
Harary, F.: On the measurement of structural balance. Behavioral Sci. 4(4), 316–323 (1959)CrossRef
6.
Akiyama, J., Avis, D., Chvátal, V., Era, H.: Balancing signed graphs. Discrete Appl. Math. 3(4), 227–233 (1981)CrossRefMATH
7.
Figueiredo, R., Frota, Y.: The maximum balanced subgraph of a signed graph: applications and solution approaches. Euro. J. Oper. Res. 236(2), 473–487 (2014)CrossRefMATH
8.
Hüffner, F., Betzler, N., Niedermeier, R.: Optimal edge deletions for signed graph balancing. In: International Workshop on Experimental and Efficient Algorithms, pp. 297–310. Springer (2007)
9.
Ordozgoiti, B., Matakos, A., Gionis, A.: Finding large balanced subgraphs in signed networks. In: Proceedings of the Web Conference 2020, pp. 1378–1388 (2020)
10.
Sharma, K., Gillani, I.A., Medya, S., Ranu, S., Bagchi, A.: Balance maximization in signed networks via edge deletions. In: Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pp. 752–760 (2021)
11.
Alabandi, G., Tešić, J., Rusnak, L., Burtscher, M.: Discovering and balancing fundamental cycles in large signed graphs. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1–17 (2021)
Metadaten
Titel
A More Powerful Heuristic for Balancing an Unbalanced Graph
verfasst von
Sukhamay Kundu
Amit A. Nanavati
Copyright-Jahr
2023
Buch
Complex Networks and Their Applications XI

Print ISBN: 978-3-031-21130-0

Electronic ISBN: 978-3-031-21131-7

Copyright-Jahr: 2023

DOI
https://doi.org/10.1007/978-3-031-21131-7_3

Premium Partner

    Bildnachweise