Graph partition

<h2 id="problem-complexity">Problem complexity</h2>
Typically, graph partition problems fall under the category of <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a> problems. Solutions to these problems are generally derived using heuristics and approximation algorithms.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> However, uniform graph partitioning or a balanced graph partition problem can be shown to be <a href="/facts/NP-complete/NFPv56DU">NP-complete</a> to approximate within any finite factor.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> Even for special graph classes such as trees and grids, no reasonable approximation algorithms exist,<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> unless <a href="/facts/P%253DNP/xoC7Ruda">P=NP</a>. Grids are a particularly interesting case since they model the graphs resulting from <a href="/facts/Finite_element_method/eUcfP1vn">Finite Element Model (FEM)</a> simulations. When not only the number of edges between the components is approximated, but also the sizes of the components, it can be shown that no reasonable fully polynomial algorithms exist for these graphs.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>

<h2 id="problem">Problem</h2>
Consider a graph G = (V, E), where V denotes the set of n vertices and E the set of edges. For a (k,v) balanced partition problem, the objective is to partition G into k components of at most size v · (n/k), while minimizing the capacity of the edges between separate components.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> Also, given G and an integer k > 1, partition V into k parts (subsets) V1, V2, ..., Vk such that the parts are disjoint and have equal size, and the number of edges with endpoints in different parts is minimized. Such partition problems have been discussed in literature as bicriteria-approximation or resource augmentation approaches. A common extension is to <a href="/facts/Hypergraph/qIR2o2I3">hypergraphs</a>, where an edge can connect more than two vertices. A hyperedge is not cut if all vertices are in one partition, and cut exactly once otherwise, no matter how many vertices are on each side. This usage is common in <a href="/facts/Electronic_design_automation/o4la3fmX">electronic design automation</a>.

<h3>Analysis</h3>
For a specific (k, 1 + ε) balanced partition problem, we seek to find a minimum cost partition of G into k components with each component containing a maximum of (1 + ε)·(n/k) nodes. We compare the cost of this approximation algorithm to the cost of a (k,1) cut, wherein each of the k components must have the same size of (n/k) nodes each, thus being a more restricted problem. Thus,

max
          
            i
          
        
        
          |
        
        
          V
          
            i
          
        
        
          |
        
        ≤
        (
        1
        +
        ε
        )
        
          ⌈
          
            
              
                
                  |
                
                V
                
                  |
                
              
              k
            
          
          ⌉
        
        .
      
    
    {\displaystyle \max _{i}|V_{i}|\leq (1+\varepsilon )\left\lceil {\frac {|V|}{k}}\right\rceil .}

We already know that (2,1) cut is the minimum bisection problem and it is NP-complete.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> Next, we assess a 3-partition problem wherein n = 3k, which is also bounded in polynomial time.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> Now, if we assume that we have a finite approximation algorithm for (k, 1)-balanced partition, then, either the 3-partition instance can be solved using the balanced (k,1) partition in G or it cannot be solved. If the 3-partition instance can be solved, then (k, 1)-balanced partitioning problem in G can be solved without cutting any edge. Otherwise, if the 3-partition instance cannot be solved, the optimum (k, 1)-balanced partitioning in G will cut at least one edge. An approximation algorithm with a finite approximation factor has to differentiate between these two cases. Hence, it can solve the 3-partition problem which is a contradiction under the assumption that P = NP. Thus, it is evident that (k,1)-balanced partitioning problem has no polynomial-time approximation algorithm with a finite approximation factor unless P = NP.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>
The <a href="/facts/Planar_separator_theorem/IfwGC9y3">planar separator theorem</a> states that any n-vertex <a href="/facts/Planar_graph/plREagr9">planar graph</a> can be partitioned into roughly equal parts by the removal of O(√n) vertices. This is not a partition in the sense described above, because the partition set consists of vertices rather than edges. However, the same result also implies that every planar graph of bounded degree has a balanced cut with O(√n) edges.

<h2 id="graph-partition-methods">Graph partition methods</h2>
Since graph partitioning is a hard problem, practical solutions are based on heuristics. There are two broad categories of methods, local and global. Well-known local methods are the <a href="/facts/Kernighan%25E2%2580%2593Lin_algorithm/oJ5F0dN5">Kernighan–Lin algorithm</a>, and <a href="/facts/Fiduccia-Mattheyses_algorithm/WNvCsJ5k">Fiduccia-Mattheyses algorithms</a>, which were the first effective 2-way cuts by local search strategies. Their major drawback is the arbitrary initial partitioning of the vertex set, which can affect the final solution quality. Global approaches rely on properties of the entire graph and do not rely on an arbitrary initial partition. The most common example is spectral partitioning, where a partition is derived from approximate eigenvectors of the adjacency matrix, or <a href="/facts/Spectral_clustering/GorfFMRT">spectral clustering</a> that groups graph vertices using the <a href="/facts/Eigendecomposition/a2nfF7hJ">eigendecomposition</a> of the <a href="/facts/Graph_Laplacian/Iwea2mm9">graph Laplacian</a> matrix.

<h2 id="multi-level-methods">Multi-level methods</h2>
Main article: <a href="/facts/Multi-level_technique/D6A3gjj3">Multi-level technique</a>
A multi-level graph partitioning algorithm works by applying one or more stages. Each stage reduces the size of
the graph by collapsing vertices and edges, partitions the smaller graph, then maps back and refines this partition of the original graph.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a> A wide variety of partitioning and refinement methods can be applied within the overall multi-level scheme. In many cases, this approach can give both fast execution times and very high quality results. 
One widely used example of such an approach is <a href="/facts/METIS/ItD8ehbI">METIS</a>,<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a> a graph partitioner, and hMETIS, the corresponding partitioner for hypergraphs.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>
An alternative approach originated from <a class="footnote-ref" id="fnref:14" href="#fn:14">14</a>
and implemented, e.g., in <a href="/facts/Scikit-learn/HqxDHRMJ">scikit-learn</a> is <a href="/facts/Spectral_clustering/GorfFMRT">spectral clustering</a> with the partitioning determined from <a href="/facts/Eigenvectors/8TjEoT8u">eigenvectors</a> of the <a href="/facts/Graph_Laplacian/Iwea2mm9">graph Laplacian</a> matrix for the original graph computed by <a href="/facts/LOBPCG/I131RpW0">LOBPCG</a> solver with <a href="/facts/Multigrid/6FTEwkja">multigrid</a> <a href="/facts/Preconditioning/MUvFta7g">preconditioning</a>.

<h2 id="spectral-partitioning-and-spectral-bisection">Spectral partitioning and spectral bisection</h2>
Given a graph 
 
 
 
 G
 =
 (
 V
 ,
 E
 )
 
 
 {\displaystyle G=(V,E)}
 
 with <a href="/facts/Adjacency_matrix/jYXNhYGs">adjacency matrix</a> 
 
 
 
 A
 
 
 {\displaystyle A}
 
, where an entry 
 
 
 
 
 A
 
 i
 j
 
 
 
 
 {\displaystyle A_{ij}}
 
 implies an edge between node 
 
 
 
 i
 
 
 {\displaystyle i}
 
 and 
 
 
 
 j
 
 
 {\displaystyle j}
 
, and <a href="/facts/Degree_matrix/tAFr9xEa">degree matrix</a> 
 
 
 
 D
 
 
 {\displaystyle D}
 
, which is a diagonal matrix, where each diagonal entry of a row 
 
 
 
 i
 
 
 {\displaystyle i}
 
, 
 
 
 
 
 d
 
 i
 i
 
 
 
 
 {\displaystyle d_{ii}}
 
, represents the node degree of node 
 
 
 
 i
 
 
 {\displaystyle i}
 
. The <a href="/facts/Laplacian_matrix/Iwea2mm9">Laplacian matrix</a> 
 
 
 
 L
 
 
 {\displaystyle L}
 
 is defined as 
 
 
 
 L
 =
 D
 −
 A
 
 
 {\displaystyle L=D-A}
 
. Now, a ratio-cut partition for graph 
 
 
 
 G
 =
 (
 V
 ,
 E
 )
 
 
 {\displaystyle G=(V,E)}
 
 is defined as a partition of 
 
 
 
 V
 
 
 {\displaystyle V}
 
 into disjoint 
 
 
 
 U
 
 
 {\displaystyle U}
 
, and 
 
 
 
 W
 
 
 {\displaystyle W}
 
, minimizing the ratio

|
              
              E
              (
              G
              )
              ∩
              (
              U
              ×
              W
              )
              
                |
              
            
            
              
                |
              
              U
              
                |
              
              ⋅
              
                |
              
              W
              
                |
              
            
          
        
      
    
    {\displaystyle {\frac {|E(G)\cap (U\times W)|}{|U|\cdot |W|}}}

of the number of edges that actually cross this cut to the number of pairs of vertices that could support such edges. Spectral graph partitioning can be motivated<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a> by analogy with partitioning of a vibrating string or a mass-spring system and similarly extended to the case of negative weights of the graph.<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a>

<h3>Fiedler eigenvalue and eigenvector</h3>
In such a scenario, the <a href="/facts/Algebraic_connectivity/z7kP4K3s">second smallest eigenvalue</a> (
 
 
 
 
 λ
 
 2
 
 
 
 
 {\displaystyle \lambda _{2}}
 
) of 
 
 
 
 L
 
 
 {\displaystyle L}
 
, yields a lower bound on the optimal cost (
 
 
 
 c
 
 
 {\displaystyle c}
 
) of ratio-cut partition with 
 
 
 
 c
 ≥
 
 
 
 λ
 
 2
 
 
 n
 
 
 
 
 {\displaystyle c\geq {\frac {\lambda _{2}}{n}}}
 
. The eigenvector (
 
 
 
 
 V
 
 2
 
 
 
 
 {\displaystyle V_{2}}
 
) corresponding to 
 
 
 
 
 λ
 
 2
 
 
 
 
 {\displaystyle \lambda _{2}}
 
, called the <a href="/facts/Algebraic_connectivity/z7kP4K3s">Fiedler vector</a>, bisects the graph into only two communities based on the sign of the corresponding vector entry. Division into a larger number of communities can be achieved by repeated bisection or by using multiple eigenvectors corresponding to the smallest eigenvalues.<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a> The examples in Figures 1,2 illustrate the spectral bisection approach.

<h3>Modularity and ratio-cut</h3>
Minimum cut partitioning however fails when the number of communities to be partitioned, or the partition sizes are unknown. For instance, optimizing the cut size for free group sizes puts all vertices in the same community. Additionally, cut size may be the wrong thing to minimize since a good division is not just one with small number of edges between communities. This motivated the use of <a href="/facts/Modularity_(networks)/Q3hmfMwa">Modularity</a> (Q)<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a> as a metric to optimize a balanced graph partition. The example in Figure 3 illustrates 2 instances of the same graph such that in (a) modularity (Q) is the partitioning metric and in (b), ratio-cut is the partitioning metric.

<h2 id="applications">Applications</h2>
<h3>Conductance</h3>
Another objective function used for graph partitioning is <a href="/facts/Conductance_(graph)/y29dPtPz">Conductance</a> which is the ratio between the number of cut edges and the volume of the smallest part. Conductance is related to electrical flows and random walks. The <a href="/facts/Cheeger_bound/sxLwSCyK">Cheeger bound</a> guarantees that spectral bisection provides partitions with nearly optimal conductance. The quality of this approximation depends on the second smallest eigenvalue of the Laplacian λ2.

<h3>Immunization</h3>
Graph partition can be useful for identifying the minimal set of nodes or links that should be immunized in order to stop epidemics.<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a>

<h2 id="other-graph-partition-methods">Other graph partition methods</h2>
Spin models have been used for clustering of multivariate data wherein similarities are translated into coupling strengths.<a class="footnote-ref" id="fnref:20" href="#fn:20">20</a> The properties of ground state spin configuration can be directly interpreted as communities. Thus, a graph is partitioned to minimize the Hamiltonian of the partitioned graph. The <a href="/facts/Hamiltonian_mechanics/2ReerlNA">Hamiltonian</a> (H) is derived by assigning the following partition rewards and penalties.

<ul><li>Reward internal edges between nodes of same group (same spin)</li>
<li>Penalize missing edges in same group</li>
<li>Penalize existing edges between different groups</li>
<li>Reward non-links between different groups.</li></ul>
Additionally, Kernel-PCA-based Spectral clustering takes a form of least squares Support Vector Machine framework, and hence it becomes possible to project the data entries to a kernel induced feature space that has maximal variance, thus implying a high separation between the projected communities.<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a>
Some methods express graph partitioning as a multi-criteria optimization problem which can be solved using local methods expressed in a game theoretic framework where each node makes a decision on the partition it chooses.<a class="footnote-ref" id="fnref:22" href="#fn:22">22</a>
For very large-scale distributed graphs classical partition methods might not apply (e.g., spectral partitioning, Metis<a class="footnote-ref" id="fnref:23" href="#fn:23">23</a>) since they require full access to graph data in order to perform global operations. For such large-scale scenarios distributed graph partitioning is used to perform partitioning through asynchronous local operations only.

<h2 id="software-tools">Software tools</h2>
<a href="/facts/Scikit-learn/HqxDHRMJ">scikit-learn</a> implements <a href="/facts/Spectral_clustering/GorfFMRT">spectral clustering</a> with the partitioning determined from <a href="/facts/Eigenvectors/8TjEoT8u">eigenvectors</a> of the <a href="/facts/Graph_Laplacian/Iwea2mm9">graph Laplacian</a> matrix for the original graph computed by <a href="/facts/ARPACK/KpvjAu67">ARPACK</a>, or by <a href="/facts/LOBPCG/I131RpW0">LOBPCG</a> solver with <a href="/facts/Multigrid/6FTEwkja">multigrid</a> <a href="/facts/Preconditioning/MUvFta7g">preconditioning</a>.<a class="footnote-ref" id="fnref:24" href="#fn:24">24</a>
<a href="/facts/METIS/ItD8ehbI">METIS</a><a class="footnote-ref" id="fnref:25" href="#fn:25">25</a> is a graph partitioning family by Karypis and Kumar. Among this family, kMetis aims at greater partitioning speed, hMetis,<a class="footnote-ref" id="fnref:26" href="#fn:26">26</a> applies to hypergraphs and aims at partition quality, and ParMetis<a class="footnote-ref" id="fnref:27" href="#fn:27">27</a> is a parallel implementation of the Metis graph partitioning algorithm.
KaHyPar<a class="footnote-ref" id="fnref:28" href="#fn:28">28</a><a class="footnote-ref" id="fnref:29" href="#fn:29">29</a><a class="footnote-ref" id="fnref:30" href="#fn:30">30</a> is a multilevel hypergraph partitioning framework providing direct k-way and recursive bisection based partitioning algorithms. It instantiates the multilevel approach in its most extreme version, removing only a single vertex in every level of the hierarchy. By using this very fine grained n-level approach combined with strong local search heuristics, it computes solutions of very high quality.
Scotch<a class="footnote-ref" id="fnref:31" href="#fn:31">31</a> is graph partitioning framework by Pellegrini. It uses recursive multilevel bisection and includes sequential as well as parallel partitioning techniques.
Jostle<a class="footnote-ref" id="fnref:32" href="#fn:32">32</a> is a sequential and parallel graph partitioning solver developed by Chris Walshaw. 
The commercialized version of this partitioner is known as NetWorks.
Party<a class="footnote-ref" id="fnref:33" href="#fn:33">33</a> implements the Bubble/shape-optimized framework and the Helpful Sets algorithm.
The software packages DibaP<a class="footnote-ref" id="fnref:34" href="#fn:34">34</a> and its MPI-parallel variant PDibaP<a class="footnote-ref" id="fnref:35" href="#fn:35">35</a> by Meyerhenke implement the Bubble framework using diffusion; DibaP also uses AMG-based techniques for coarsening and solving linear systems arising in the diffusive approach.
Sanders and Schulz released a graph partitioning package KaHIP<a class="footnote-ref" id="fnref:36" href="#fn:36">36</a> (Karlsruhe High Quality Partitioning) that implements for example flow-based methods, more-localized local searches and several parallel and sequential meta-heuristics.
The tools Parkway<a class="footnote-ref" id="fnref:37" href="#fn:37">37</a> by Trifunovic and
Knottenbelt as well as Zoltan<a class="footnote-ref" id="fnref:38" href="#fn:38">38</a> by Devine et al. focus on hypergraph
partitioning.

<h2 id="further-reading">Further reading</h2>
<ul><li>Bichot, Charles-Edmond; Siarry, Patrick (2011). Graph Partitioning: Optimisation and Applications. ISTE – Wiley. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1-84821-233-6.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Andreev, Konstantin; Räcke, Harald (2004). "Balanced graph partitioning". Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures. Barcelona, Spain. pp. 120–124. CiteSeerX 10.1.1.417.8592. doi:10.1145/1007912.1007931. ISBN 978-1-58113-840-5.{{cite book}}: CS1 maint: location missing publisher (link) <a href="978-1-58113-840-5" target="_blank">978-1-58113-840-5</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Buluc, Aydin; Meyerhenke, Henning; Safro, Ilya; Sanders, Peter; Schulz, Christian (2013). "Recent Advances in Graph Partitioning". arXiv:1311.3144 [cs.DS]. <a href="/wiki/Peter_Sanders_(computer_scientist)" target="_blank">/wiki/Peter_Sanders_(computer_scientist)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Feldmann, Andreas Emil; Foschini, Luca (2012). "Balanced Partitions of Trees and Applications". Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science: 100–111. <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Andreev, Konstantin; Räcke, Harald (2004). "Balanced graph partitioning". Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures. Barcelona, Spain. pp. 120–124. CiteSeerX 10.1.1.417.8592. doi:10.1145/1007912.1007931. ISBN 978-1-58113-840-5.{{cite book}}: CS1 maint: location missing publisher (link) <a href="978-1-58113-840-5" target="_blank">978-1-58113-840-5</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Feldmann, Andreas Emil (2012). "Fast Balanced Partitioning is Hard, Even on Grids and Trees". Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science. arXiv:1111.6745. Bibcode:2011arXiv1111.6745F. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Feldmann, Andreas Emil (2012). "Fast Balanced Partitioning is Hard, Even on Grids and Trees". Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science. arXiv:1111.6745. Bibcode:2011arXiv1111.6745F. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Andreev, Konstantin; Räcke, Harald (2004). "Balanced graph partitioning". Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures. Barcelona, Spain. pp. 120–124. CiteSeerX 10.1.1.417.8592. doi:10.1145/1007912.1007931. ISBN 978-1-58113-840-5.{{cite book}}: CS1 maint: location missing publisher (link) <a href="978-1-58113-840-5" target="_blank">978-1-58113-840-5</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Garey, Michael R.; Johnson, David S. (1979). Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman & Co. ISBN 978-0-7167-1044-8. <a href="978-0-7167-1044-8" target="_blank">978-0-7167-1044-8</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Andreev, Konstantin; Räcke, Harald (2004). "Balanced graph partitioning". Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures. Barcelona, Spain. pp. 120–124. CiteSeerX 10.1.1.417.8592. doi:10.1145/1007912.1007931. ISBN 978-1-58113-840-5.{{cite book}}: CS1 maint: location missing publisher (link) <a href="978-1-58113-840-5" target="_blank">978-1-58113-840-5</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Andreev, Konstantin; Räcke, Harald (2004). "Balanced graph partitioning". Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures. Barcelona, Spain. pp. 120–124. CiteSeerX 10.1.1.417.8592. doi:10.1145/1007912.1007931. ISBN 978-1-58113-840-5.{{cite book}}: CS1 maint: location missing publisher (link) <a href="978-1-58113-840-5" target="_blank">978-1-58113-840-5</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Hendrickson, B.; Leland, R. (1995). A multilevel algorithm for partitioning graphs. Proceedings of the 1995 ACM/IEEE conference on Supercomputing. ACM. p. 28. <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Karypis, G.; Kumar, V. (1999). "A fast and high quality multilevel scheme for partitioning irregular graphs". SIAM Journal on Scientific Computing. 20 (1): 359. CiteSeerX 10.1.1.39.3415. doi:10.1137/S1064827595287997. S2CID 3628209. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Karypis, G.; Aggarwal, R.; Kumar, V.; Shekhar, S. (1997). Multilevel hypergraph partitioning: application in VLSI domain. Proceedings of the 34th annual Design Automation Conference. pp. 526–529. <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Knyazev, Andrew V. (2006). Multiscale Spectral Graph Partitioning and Image Segmentation. Workshop on Algorithms for Modern Massive Data Sets Stanford University and Yahoo! Research. <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">J. Demmel, [1], CS267: Notes for Lecture 23, April 9, 1999, Graph Partitioning, Part 2 <a href="https://people.eecs.berkeley.edu/~demmel/cs267/lecture20/lecture20.html" target="_blank">https://people.eecs.berkeley.edu/~demmel/cs267/lecture20/lecture20.html</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Knyazev, Andrew (2018). On spectral partitioning of signed graphs. Eighth SIAM Workshop on Combinatorial Scientific Computing, CSC 2018, Bergen, Norway, June 6–8. arXiv:1701.01394. doi:10.1137/1.9781611975215.2. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Naumov, M.; Moon, T. (2016). "Parallel Spectral Graph Partitioning". NVIDIA Technical Report. nvr-2016-001. <a href="https://research.nvidia.com/publication/parallel-spectral-graph-partitioning" target="_blank">https://research.nvidia.com/publication/parallel-spectral-graph-partitioning</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Newman, M. E. J. (2006). "Modularity and community structure in networks". PNAS. 103 (23): 8577–8696. arXiv:physics/0602124. Bibcode:2006PNAS..103.8577N. doi:10.1073/pnas.0601602103. PMC 1482622. PMID 16723398. <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1482622" target="_blank">https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1482622</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Y. Chen, G. Paul, S. Havlin, F. Liljeros, H.E. Stanley (2009). "Finding a Better Immunization Strategy". Phys. Rev. Lett. 101 (5): 058701. doi:10.1103/PhysRevLett.101.058701. PMID 18764435.{{cite journal}}: CS1 maint: multiple names: authors list (link) <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Reichardt, Jörg; Bornholdt, Stefan (July 2006). "Statistical mechanics of community detection". Phys. Rev. E. 74 (1): 016110. arXiv:cond-mat/0603718. Bibcode:2006PhRvE..74a6110R. doi:10.1103/PhysRevE.74.016110. PMID 16907154. S2CID 792965. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Alzate, Carlos; Suykens, Johan A. K. (2010). "Multiway Spectral Clustering with Out-of-Sample Extensions through Weighted Kernel PCA". IEEE Transactions on Pattern Analysis and Machine Intelligence. 32 (2): 335–347. doi:10.1109/TPAMI.2008.292. ISSN 0162-8828. PMID 20075462. S2CID 200488. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">Kurve, A.; Griffin, C.; Kesidis G. (2011) "A graph partitioning game for distributed simulation of networks", Proceedings of the 2011 International Workshop on Modeling, Analysis, and Control of Complex Networks: 9–16 <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">Karypis, G.; Kumar, V. (1999). "A fast and high quality multilevel scheme for partitioning irregular graphs". SIAM Journal on Scientific Computing. 20 (1): 359. CiteSeerX 10.1.1.39.3415. doi:10.1137/S1064827595287997. S2CID 3628209. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
<li id="fn:24">Knyazev, Andrew V. (2006). Multiscale Spectral Graph Partitioning and Image Segmentation. Workshop on Algorithms for Modern Massive Data Sets Stanford University and Yahoo! Research. <a href="#fnref:24" class="footnote-back-ref">↩</a></li>
<li id="fn:25">Karypis, G.; Kumar, V. (1999). "A fast and high quality multilevel scheme for partitioning irregular graphs". SIAM Journal on Scientific Computing. 20 (1): 359. CiteSeerX 10.1.1.39.3415. doi:10.1137/S1064827595287997. S2CID 3628209. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></li>
<li id="fn:26">Karypis, G.; Aggarwal, R.; Kumar, V.; Shekhar, S. (1997). Multilevel hypergraph partitioning: application in VLSI domain. Proceedings of the 34th annual Design Automation Conference. pp. 526–529. <a href="#fnref:26" class="footnote-back-ref">↩</a></li>
<li id="fn:27">Karypis, G.; Kumar, V. (1999). "A fast and high quality multilevel scheme for partitioning irregular graphs". SIAM Journal on Scientific Computing. 20 (1): 359. CiteSeerX 10.1.1.39.3415. doi:10.1137/S1064827595287997. S2CID 3628209. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:27" class="footnote-back-ref">↩</a></li>
<li id="fn:28">Schlag, S.; Henne, V.; Heuer, T.; Meyerhenke, H.; Sanders, P.; Schulz, C. (2015-12-30). "K-way Hypergraph Partitioning via n-Level Recursive Bisection". 2016 Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics. pp. 53–67. arXiv:1511.03137. doi:10.1137/1.9781611974317.5. ISBN 978-1-61197-431-7. S2CID 1674598. <a href="978-1-61197-431-7" target="_blank">978-1-61197-431-7</a> <a href="#fnref:28" class="footnote-back-ref">↩</a></li>
<li id="fn:29">Akhremtsev, Y.; Heuer, T.; Sanders, P.; Schlag, S. (2017-01-01). "Engineering a direct k-way Hypergraph Partitioning Algorithm". 2017 Proceedings of the Nineteenth Workshop on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics. pp. 28–42. doi:10.1137/1.9781611974768.3. ISBN 978-1-61197-476-8. <a href="978-1-61197-476-8" target="_blank">978-1-61197-476-8</a> <a href="#fnref:29" class="footnote-back-ref">↩</a></li>
<li id="fn:30">Heuer, Tobias; Schlag, Sebastian (2017). "Improving Coarsening Schemes for Hypergraph Partitioning by Exploiting Community Structure". In Iliopoulos, Costas S.; Pissis, Solon P.; Puglisi, Simon J.; Raman, Rajeev (eds.). 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs). Vol. 75. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. pp. 21:1–21:19. doi:10.4230/LIPIcs.SEA.2017.21. ISBN 978-3-95977-036-1. <a href="978-3-95977-036-1" target="_blank">978-3-95977-036-1</a> <a href="#fnref:30" class="footnote-back-ref">↩</a></li>
<li id="fn:31">Chevalier, C.; Pellegrini, F. (2008). "PT-Scotch: A Tool for Efficient Parallel Graph Ordering". Parallel Computing. 34 (6): 318–331. arXiv:0907.1375. doi:10.1016/j.parco.2007.12.001. S2CID 10433524. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:31" class="footnote-back-ref">↩</a></li>
<li id="fn:32">Walshaw, C.; Cross, M. (2000). "Mesh Partitioning: A Multilevel Balancing and Refinement Algorithm". SIAM Journal on Scientific Computing. 22 (1): 63–80. Bibcode:2000SJSC...22...63W. CiteSeerX 10.1.1.19.1836. doi:10.1137/s1064827598337373. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:32" class="footnote-back-ref">↩</a></li>
<li id="fn:33">Diekmann, R.; Preis, R.; Schlimbach, F.; Walshaw, C. (2000). "Shape-optimized Mesh Partitioning and Load Balancing for Parallel Adaptive FEM". Parallel Computing. 26 (12): 1555–1581. CiteSeerX 10.1.1.46.5687. doi:10.1016/s0167-8191(00)00043-0. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:33" class="footnote-back-ref">↩</a></li>
<li id="fn:34">Meyerhenke, H.; Monien, B.; Sauerwald, T. (2008). "A New Diffusion-Based Multilevel Algorithm for Computing Graph Partitions". Journal of Parallel Computing and Distributed Computing. 69 (9): 750–761. CiteSeerX 10.1.1.702.7275. doi:10.1016/j.jpdc.2009.04.005. S2CID 9755877. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:34" class="footnote-back-ref">↩</a></li>
<li id="fn:35">Meyerhenke, H. (2013). Shape Optimizing Load Balancing for MPI-Parallel Adaptive Numerical Simulations. 10th DIMACS Implementation Challenge on Graph Partitioning and Graph Clustering. pp. 67–82. <a href="#fnref:35" class="footnote-back-ref">↩</a></li>
<li id="fn:36">Sanders, P.; Schulz, C. (2011). Engineering Multilevel Graph Partitioning Algorithms. Proceedings of the 19th European Symposium on Algorithms (ESA). Vol. 6942. pp. 469–480. <a href="/wiki/Peter_Sanders_(computer_scientist)" target="_blank">/wiki/Peter_Sanders_(computer_scientist)</a> <a href="#fnref:36" class="footnote-back-ref">↩</a></li>
<li id="fn:37">Trifunovic, A.; Knottenbelt, W. J. (2008). "Parallel Multilevel Algorithms for Hypergraph Partitioning". Journal of Parallel and Distributed Computing. 68 (5): 563–581. CiteSeerX 10.1.1.641.7796. doi:10.1016/j.jpdc.2007.11.002. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:37" class="footnote-back-ref">↩</a></li>
<li id="fn:38">Devine, K.; Boman, E.; Heaphy, R.; Bisseling, R.; Catalyurek, Ü. (2006). Parallel Hypergraph Partitioning for Scientific Computing. Proceedings of the 20th International Conference on Parallel and Distributed Processing. p. 124. <a href="#fnref:38" class="footnote-back-ref">↩</a></li>
</ol>

Graph partition open-in-new

Graph partition