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:
Distributed Range-Based Meta-Data Management for an In-Memory Storage Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

On Evaluating Graph Partitioning Algorithms for Distributed Agent Based Models on Networks

verfasst von : Alessia Antelmi, Gennaro Cordasco, Carmine Spagnuolo, Luca Vicidomini

Erschienen in: Euro-Par 2015: Parallel Processing Workshops

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Graph Partitioning is a key challenge problem with application in many scientific and technological fields. The problem is very well studied with a rich literature and is known to be NP-hard. Several heuristic solutions, which follow diverse approaches, have been proposed, they are based on different initial assumptions that make them difficult to compare. An analytical comparison was performed based on an Implementation Challenge [3], however being a multi-objective problem (two opposing goals are for instance load balancing and edge-cut size), the results are difficult to compare and it is hard to foresee what can be the impact of one solution, instead of another, in a real scenario. In this paper we analyze the problem in a real context: the development of a distributed agent-based simulation model on a network field (which for instance can model social interactions).
We present an extensive evaluation of the most efficient and effective solutions for the balanced k-way partitioning problem. We evaluate several strategies both analytically and on real distributed simulation settings (D-Mason). Results show that, a good partitioning strategy strongly influences the performances of the distributed simulation environment. Moreover, we show that there is a strong correlation between the edge-cut size and the real performances. Analyzing the results in details we were also able to discover the parameters that need to be optimized for best performances on networks in ABMs.

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 Superoptimizing Memory Subsystems for Multiple Objectives
Nächstes Kapitel Distributed Agent-Based Simulation and GIS: An Experiment with the Dynamics of Social Norms
Fußnoten
1
The correlation between T(N, A, 2) and E(N, A, 2) cannot be computed, since for \(k=2\) all the partitioning strategy require exactly 1 communication channel and so E(N, A, 2) has standard deviation equal to 0.
 
Literatur
1.
2.
Alpert, C.J., Kahng, A.B.: Recent directions in netlist partitioning: a survey. Integr. VLSI J. 19, 1–81 (1995)MATHCrossRef
3.
Bader, D.A., Meyerhenke, H., Sanders, P., Wagner, D. (eds.): Graph Partitioning and Graph Clustering - 10th DIMACS Implementation Challenge Workshop, Georgia Institute of Technology, Atlanta, GA, USA, February 13–14, 2012. Proceedings, Contemporary Mathematics, vol. 588, American Mathematical Society (2013). http://​dx.​doi.​org/​10.​1090/​conm/​588
4.
Balan, G.C., Cioffi-Revilla, C., Luke, S., Panait, L., Paus, S.: MASON: a java multi-agent simulation library. In: Proceedings of the Agent 2003 Conference (2003)
5.
Cordasco, G., De Chiara, R., Mancuso, A., Mazzeo, D., Scarano, V., Spagnuolo, C.: A Framework for distributing Agent-based simulations. In: 9th International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Platforms (2011)
6.
Cordasco, G., De Chiara, R., Mancuso, A., Mazzeo, D., Scarano, V., Spagnuolo, C.: Bringing together efficiency and effectiveness in distributed simulations: the experience with D-MASON. SIMULATION Trans. Soc. Model. Simul. Int. 89(10), 1236–1253 (2013)CrossRef
7.
Cordasco, G., Mancuso, A., Milone, F., Spagnuolo, C.: Communication strategies in distributed agent-based simulations: the experience with D-Mason. In: an Mey, D., Alexander, M., Bientinesi, P., Cannataro, M., Clauss, C., Costan, A., Kecskemeti, G., Morin, C., Ricci, L., Sahuquillo, J., Schulz, M., Scarano, V., Scott, S.L., Weidendorfer, J. (eds.) Euro-Par 2013. LNCS, vol. 8374, pp. 533–543. Springer, Heidelberg (2014) CrossRef
8.
Cordasco, G., Milone, F., Spagnuolo, C., Vicidomini, L.: Exploiting D-Mason on parallel platforms: a novel communication strategy. In: Proceedings of the 2nd Workshop on Parallel and Distributed Agent-Based Simulations (PADABS), Euro-Par 2014 (2014)
9.
Cosenza, B., Cordasco, G., De Chiara, R., Scarano, V.: Distributed load balancing for parallel agent-based simulations. In: Proceedings of the 19th International Euromicro Conference on Parallel, Distributed, and Network-Based Processing, (PDP 2011), pp. 62–69 (2011)
10.
Easley, D., Kleinberg, J.: Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, New York (2010) CrossRef
11.
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co, New York (1990)
12.
Gupta, A.: Graph partitioning based sparse matrix orderings for interior-point algorithms. IBM Thomas J, Watson Research Division (1996)
13.
Karypis, G., Aggarwal, R., Kumar, V., Shekhar, S.: Multilevel hypergraph partitioning: applications in VLSI domain. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 7(1), 69–79 (1999)CrossRef
14.
Karypis, G., Kumar, V.: Multilevel k-way partitioning scheme for irregular graphs. J. Parallel Distrib. Comput. 48(1), 96–129 (1998)CrossRefMathSciNet
15.
Kernighan, B., Lin, S.: An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49(2), 291–307 (1970)MATHCrossRef
16.
Luke, S., Cioffi-revilla, C., Panait, L., Sullivan, K.: MASON: a new multi-agent simulation toolkit. In: Proceedings of the 2004 SwarmFest Workshop (2004)
17.
18.
Newman, M.E.J.: Modularity and community structure in networks. Proc. Nat. Acad. Sci. (PNAS) 103(23), 8577–8582 (2006)CrossRef
19.
Rahimian, F., Payberah, A.H., Girdzijauskas, S., Jelasity, M., Haridi, S.: JA-BE-JA: a distributed algorithm for balanced graph partitioning. In: 7th International Conference on Self-Adaptive and SelfOrganizing Systems. IEEE (2013)
20.
Sanders, P., Schulz, C.: Think locally, act globally: highly balanced graph partitioning. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 164–175. Springer, Heidelberg (2013) CrossRef
21.
Spielmat, D., Teng, S.H.: Spectral partitioning works: planar graphs and finite element meshes. In: Proceedings 37th Annual Symposium on Foundations of Computer Science, pp. 96–105, October 1996
22.
Sutter, H.: The free lunch is over: a fundamental turn toward concurrency in software. Dr. Dobb’s J. 30(3), 202–210 (2005)
23.
Tekin, E., Sabuncuoglu, I.: Simulation optimization: a comprehensive review on theory and applications. IIE Trans. 36(11), 1067–1081 (2004)CrossRef
24.
25.
26.
27.
28.
Metadaten
Titel
On Evaluating Graph Partitioning Algorithms for Distributed Agent Based Models on Networks
verfasst von
Alessia Antelmi
Gennaro Cordasco
Carmine Spagnuolo
Luca Vicidomini
Copyright-Jahr
2015
Buch
Euro-Par 2015: Parallel Processing Workshops

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

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

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-27308-2_30

Neuer Inhalt

    Bildnachweise