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:
A Time-Space Trade-Off for Triangulations of Points in the Plane Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

Cooperative Game Theory Approaches for Network Partitioning

verfasst von : Konstantin E. Avrachenkov, Aleksei Yu. Kondratev, Vladimir V. Mazalov

Erschienen in: Computing and Combinatorics

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

The paper is devoted to game-theoretic methods for community detection in networks. The traditional methods for detecting community structure are based on selecting denser subgraphs inside the network. Here we propose to use the methods of cooperative game theory that highlight not only the link density but also the mechanisms of cluster formation. Specifically, we suggest two approaches from cooperative game theory: the first approach is based on the Myerson value, whereas the second approach is based on hedonic games. Both approaches allow to detect clusters with various resolution. However, the tuning of the resolution parameter in the hedonic games approach is particularly intuitive. Furthermore, the modularity based approach and its generalizations can be viewed as particular cases of the hedonic games.

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 Improved Approximation Algorithm for the Maximum Base Pair Stackings Problem in RNA Secondary Structures Prediction
Nächstes Kapitel Chain of Influencers: Multipartite Intra-community Ranking
Literatur
1.
Avrachenkov, K., Dobrynin, V., Nemirovsky, D., Pham, S.K., Smirnova, E.: Pagerank based clustering of hypertext document collections. In: Proceedings of ACM SIGIR 2008, pp. 873–874 (2008)
2.
Avrachenkov, K., El Chamie, M., Neglia, G.: Graph clustering based on mixing time of random walks. In: Proceedings of IEEE ICC 2014, pp. 4089–4094 (2014)
3.
Blatt, M., Wiseman, S., Domany, E.: Clustering data through an analogy to the Potts model. In: Proceedings of NIPS 1996, pp. 416–422 (1996)
4.
Blondel, V.D., Guillaume, J.L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. J. Stat. Mech. Theory Exp. 10, P10008 (2008)CrossRef
5.
6.
Dongen, S.: Performance criteria for graph clustering and Markov cluster experiments. CWI Technical report (2000)
7.
8.
Fortunato, S., Barthelemy, M.: Resolution limit in community detection. Proc. Nat. Acad. Sci. 104(1), 36–41 (2007)CrossRef
9.
Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proc. Nat. Acad. Sci. USA 99(12), 7821–7826 (2002)MathSciNetCrossRefMATH
10.
11.
Jackson, M.O.: Social and Economic Networks. Princeton University Press, Princeton (2008)MATH
12.
Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, M.W.: Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Math. 6(1), 29–123 (2009)MathSciNetCrossRefMATH
13.
Mazalov, V.: Mathematical Game Theory and Applications. Wiley, Hoboken (2014)MATH
14.
Mazalov, V., Avrachenkov, K., Trukhina, I.: Game-theoretic centrality measures for weighted graphs. Fundamenta Informaticae 145(3), 341–358 (2016)MathSciNetCrossRef
15.
Mazalov, V.V., Trukhina, L.I.: Generating functions and the Myerson vector in communication networks. Disc. Math. Appl. 24(5), 295–303 (2014)MathSciNetMATH
16.
Meila, M., Shi, J.: A random walks view of spectral segmentation. In: Proceedings of AISTATS 2001
17.
18.
Newman, M.E.J.: A measure of betweenness centrality based on random walks. Proc. Nat. Acad. Sci. USA 27, 39–54 (2005)
19.
Newman, M.E.J.: Modularity and community structure in networks. Soc. Netw. 103(23), 8577–8582 (2006)
20.
Pons, P., Latapy, M.: Computing communities in large networks using random walks. J. Graph Algorithms Appl. 10(2), 191–218 (2006)MathSciNetCrossRefMATH
21.
Raghavan, U.N., Albert, R., Kumara, S.: Near linear time algorithm to detect community structures in large-scale networks. Phys. Rev. E 76(3), 036106 (2007)CrossRef
22.
Reichardt, J., Bornholdt, S.: Statistical mechanics of community detection. Phys. Rev. E 74(1), 016110 (2006)MathSciNetCrossRef
23.
24.
Waltman, L., van Eck, N.J., Noyons, E.C.: A unified approach to mapping and clustering of bibliometric networks. J. Inform. 4(4), 629–635 (2010)CrossRef
25.
Zachary, W.W.: An information flow model for conflict and fission in small groups. J. Anthropol. Res. 33(4), 452–473 (1977)CrossRef
Metadaten
Titel
Cooperative Game Theory Approaches for Network Partitioning
verfasst von
Konstantin E. Avrachenkov
Aleksei Yu. Kondratev
Vladimir V. Mazalov
Copyright-Jahr
2017
Buch
Computing and Combinatorics

Print ISBN: 978-3-319-62388-7

Electronic ISBN: 978-3-319-62389-4

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-62389-4_49

Premium Partner

    Bildnachweise