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
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
A Fair-Cost Analysis of the Random Neighbor Sampling Method Kapitel lesen Erstes Kapitel lesen

2022 | OriginalPaper | Buchkapitel

Mixed Integer Programming and LP Rounding for Opinion Maximization on Directed Acyclic Graphs

verfasst von : Po-An Chen, Ya-Wen Cheng, Yao-Wei Tseng

Erschienen in: Complex Networks & Their Applications X

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Gionis et al. have already proposed a greedy algorithm and some heuristics for the opinion maximization problem. Unlike their approach, we adopt mathematical programming to solve the opinion maximization problem on specific classes of networks. We find that on directed acyclic graphs, opinion influence between nodes will not cycle, but would spread outwards from influencers. Based on such an insight, we model the problem as a mixed integer programming (MIP) problem and relax the MIP to a linear program (LP). With MIP, we obtain optimal solutions for the opinion maximization problem and derive approximation solutions with LP randomized rounding algorithms. We conduct experiments for one LP randomized rounding algorithm and give an analysis of the approximation ratio for the other LP randomized rounding algorithm.

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 Need for a Realistic Measure of Attack Severity in Centrality Based Node Attack Strategies
Fußnoten
1
Also, although our main results are motivated from and established for directed acyclic graphs, what if a given graph is not acyclic but is very close to an acyclic graph? Our conjecture is that the approach can be extended for such a graph since we have not yet observed anything that would immediately prevent us from obtaining an approximation solution, but the feasibility in a probabilistic sense and approximation ratio guarantees may change a lot.
 
2
The uniqueness follows from the convexity of cost functions.
 
Literatur
1.
Ahmadinejad, A., Mahini, H.: How effectively can we form opinions? In: Proceedings of International World Wide Web Conference (2014)
2.
3.
Chen, P.-A., Chen, Y.-L., Chi-Jen, L.: Bounds on the price of anarchy for a more general class of directed graphs in opinion formation games. Oper. Res. Lett. 44(6), 808–811 (2016)MathSciNetCrossRefMATH
4.
5.
Friedkin, N.E., Johnsen, E.C.: Social influence and opinions. J. Math. Sociol. 15(3–4), 193–206 (1990)CrossRefMATH
6.
Gionis, A., Terzi, E., Tsaparas, P.: Opinion maximization in social networks. In: Proceedings of the 2013 SIAM International Conference on Data Mining, pp. 387–395. SIAM (2013)
7.
LLC Gurobi Optimization. Gurobi optimizer reference manual (2021)
8.
Leskovec, J., Sosič, R.: SNAP: a general-purpose network analysis and graph-mining library. ACM Trans. Intell. Syst. Technol. (TIST) 8(1), 1 (2016)
9.
Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, Dordrecht (2004)CrossRefMATH
10.
Shang, Y.: Group pinning consensus under fixed and randomly switching topologies with acyclic partition. Netw. Heterog. Media 9(3), 553–573 (2014)MathSciNetCrossRefMATH
11.
Metadaten
Titel
Mixed Integer Programming and LP Rounding for Opinion Maximization on Directed Acyclic Graphs
verfasst von
Po-An Chen
Ya-Wen Cheng
Yao-Wei Tseng
Copyright-Jahr
2022
Buch
Complex Networks & Their Applications X

Print ISBN: 978-3-030-93408-8

Electronic ISBN: 978-3-030-93409-5

Copyright-Jahr: 2022

DOI
https://doi.org/10.1007/978-3-030-93409-5_71

Premium Partner

    Bildnachweise