A Diffusion Process for Graph Partitioning: Its Solutions and Their Improvement | SpringerLink
Skip to main content
Springer Nature Link
Log in

A Diffusion Process for Graph Partitioning: Its Solutions and Their Improvement

  • Conference paper
  • First Online:
Parallel Processing and Applied Mathematics (PPAM 2015)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 9573))

  • 1293 Accesses

Abstract

We present a diffusion process on graphs for k-way partitioning. In this approach, various species propagate on the graph that cancel each other out, and every partition is represented by one species of the converged solution. The vertices and edges of the graph are reservoirs and resistances, respectively, and source terms are placed on the vertices. A distribution of these source terms on the graph is suggested and the resulting k-way partitioning of the diffusion process for basic graphs discussed. We present reference examples in which complex graphs are recursively bi-partitioned with a diffusion step and a subsequent Kernighan-Lin improvement step. For comparison the graphs are also partitioned with multilevel methods and a subsequent Kernighan-Lin improvement. For certain graphs the diffusion approach produces the best partitions.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. http://www.corc.ieor.columbia.edu/meetings/ipcox/talks/kevin/export-ipco-talk/gparchive.html

  2. https://cfwebprod.sandia.gov/cfdocs/CompResearch/templates/insert/software.cfm

  3. Boillat, J.E.: Load balancing and Poisson equation in a graph. Concur. Pract. Exper. 2(4), 289–313 (1990)

    Article  Google Scholar 

  4. Diekmann, R., Preis, R., Schlimbach, F., Walshaw, C.: Shape-optimized mesh partitioning and load balancing for parallel adaptive FEM. Parallel Comput. 26, 1555–1581 (2000)

    Article  Google Scholar 

  5. Fiduccia, C.M., Mattheyses, R.M.: A linear-time heuristic for improving network partitions. In: 19th Design Automation Conference, pp. 175–181. IEEE (1982)

    Google Scholar 

  6. Hendrickson, B., Leland, R.: An improved spectral graph partitioning algorithm for mapping parallel computations. SIAM J. Sci. Comput. 16(2), 452–469 (1995). SANDIA REPORT SAND92-1460 \(\cdot \) UC-405 September 1992

    Article  MathSciNet  Google Scholar 

  7. Hendrickson, B., Leland, R.: A multilevel algorithm for partitioning graphs. In: Proceedings of Supercomputing 1995, vol. 1, pp. 626–657. ACM/IEEE (1995)

    Google Scholar 

  8. Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20(1), 359–392 (1998)

    Article  MathSciNet  Google Scholar 

  9. Karypis, G., Kumar, V.: A parallel algorithm for multilevel graph partitioning and sparse matrix ordering. J. Parallel Distrib. Comput. 48, 71–95 (1998)

    Article  Google Scholar 

  10. Kernighan, B.W., Lin, S.: An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49(2), 291–307 (1970)

    Article  Google Scholar 

  11. Kirkpatrick, S., Gelatt Jr., C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983)

    Article  MathSciNet  Google Scholar 

  12. Krishnamurthy, B.: An improved min-cut algorithm for partitioning VLSI networks. IEEE Trans. Comput. c–33(5), 438–446 (1984)

    Article  Google Scholar 

  13. Lafon, S., Lee, A.B.: Diffusion maps and coarse-graining: a unified framework for dimensionality reduction, graph partitioning, and data set parametrization. IEEE Trans. Pattern Anal. 28(9), 1393–1403 (2006)

    Article  Google Scholar 

  14. Meyerhenke, H., Monien, B., Sauerwald, T.: A new diffusion-based multilevel algorithm for computing graph partitions of very high quality. In: Parallel and Distributed Processing, IPDPS, pp. 1–13. IEEE, Miami (2008)

    Google Scholar 

  15. Meyerhenke, H., Monien, B., Schamberger, S.: Graph partitioning and disturbed diffusion. Parallel Comput. 35, 544–569 (2009)

    Article  Google Scholar 

  16. Pellegrini, F.: A parallelisable multi-level banded diffusion scheme for computing balanced partitions with smooth boundaries. In: Kermarrec, A.-M., Bougé, L., Priol, T. (eds.) Euro-Par 2007. LNCS, vol. 4641, pp. 195–204. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  17. Sanchis, L.A.: Multiple-way network partitioning. IEEE Trans. Comput. 38(1), 62–81 (1989)

    Article  Google Scholar 

  18. Sanders, P., Schulz, C.: Engineering multilevel graph partitioning algorithms. In: Demetrescu, C., Halldórsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 469–480. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  19. Soper, A.J., Walshaw, C., Cross, M.: A combined evolutionary search and multilevel optimisation approach to graph-partitioning. J. Global Optim. 29, 225–241 (2004)

    Article  MathSciNet  Google Scholar 

  20. Xu, C., Lau, F.C.M.: Load Balancing in Parallel Computers: Theory and Practice. Kluwer, Boston (1997)

    MATH  Google Scholar 

Download references

Acknowledgements

The authors would like to thank T.W. Robinson and W. Sawyer for fruitful discussions.

Author information

Authors and Affiliations

  1. CSCS, Swiss National Supercomputing Centre, Via Trevano 131, 6900, Lugano, Switzerland

    Andreas Jocksch

Authors
  1. Andreas Jocksch
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Andreas Jocksch .

Editor information

Editors and Affiliations

  1. Czestochowa University of Technolog, Czestochowa, Poland

    Roman Wyrzykowski

  2. Department of Computer Science, University of Southern California, Marina Del Rey, California, USA

    Ewa Deelman

  3. Electrical Engineering & Comput. Science, University of Tennessee, Knoxville, Tennessee, USA

    Jack Dongarra

  4. Czestochowa University of Technology, Institute of Computer & Information Sci., Czestochowa, Poland

    Konrad Karczewski

  5. Department of Computer Science, AGH University of Science and Technology, Krakow, Poland

    Jacek Kitowski

  6. Systèmes d’informations, Big Data et Rec, AGH University of Science and Technology, Krakow, Poland

    Kazimierz Wiatr

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer International Publishing Switzerland

About this paper

Cite this paper

Jocksch, A. (2016). A Diffusion Process for Graph Partitioning: Its Solutions and Their Improvement. In: Wyrzykowski, R., Deelman, E., Dongarra, J., Karczewski, K., Kitowski, J., Wiatr, K. (eds) Parallel Processing and Applied Mathematics. PPAM 2015. Lecture Notes in Computer Science(), vol 9573. Springer, Cham. https://doi.org/10.1007/978-3-319-32149-3_21

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-32149-3_21

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-32148-6

  • Online ISBN: 978-3-319-32149-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics