American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Global weak solution to the quantum Navier-Stokes-Landau-Lifshitz equations with density-dependent viscosity
  • DCDS-B Home
  • This Issue
  • Next Article
    Ground state solutions of fractional Schrödinger equations with potentials and weak monotonicity condition on the nonlinear term
November  2019, 24(11): 6091-6139. doi: 10.3934/dcdsb.2019132

A Max-Cut approximation using a graph based MBO scheme

Blaine Keetch and  Yves van Gennip

School of Mathematical Sciences, The University of Nottingham, University Park, Nottingham, United Kingdom, NG7 2RD

Received  November 2017 Revised  June 2018 Published  November 2019 Early access  July 2019

Fund Project: We would like to thank the EPSRC for supporting this work through the DTP grant EP/M50810X/1.

The Max-Cut problem is a well known combinatorial optimization problem. In this paper we describe a fast approximation method. Given a graph $ G $, we want to find a cut whose size is maximal among all possible cuts. A cut is a partition of the vertex set of $ G $ into two disjoint subsets. For an unweighted graph, the size of the cut is the number of edges that have one vertex on either side of the partition; we also consider a weighted version of the problem where each edge contributes a nonnegative weight to the cut.

We introduce the signless Ginzburg–Landau functional and prove that this functional $ \Gamma $-converges to a Max-Cut objective functional. We approximately minimize this functional using a graph based signless Merriman–Bence–Osher (MBO) scheme, which uses a signless Laplacian. We derive a Lyapunov functional for the iterations of our signless MBO scheme. We show experimentally that on some classes of graphs the resulting algorithm produces more accurate maximum cut approximations than the current state-of-the-art approximation algorithm. One of our methods of minimizing the functional results in an algorithm with a time complexity of $ \mathcal{O}(|E|) $, where $ |E| $ is the total number of edges on $ G $.

Keywords: Graph algorithms, partial differential equations on graphs, Ginzburg-Landau functionals, NP hard problems.
Mathematics Subject Classification: Primary: 05C85, 35R02, 35Q56; Secondary: 49K15, 68R10.
Citation: Blaine Keetch, Yves van Gennip. A Max-Cut approximation using a graph based MBO scheme. Discrete and Continuous Dynamical Systems - B, 2019, 24 (11) : 6091-6139. doi: 10.3934/dcdsb.2019132
References:
[1]

University of Ioannina, Department of Computer Science and Engineering Teaching Resources, http://www.cs.uoi.gr/tsap/teaching/InformationNetworks/data-code.html., Accessed: 2017-03-13.

[2]

MIT Strategic Engineering Research Group: Matlab Tools for Network Analysis (2006-2011), http://strategic.mit.edu/docs/matlab_networks/random_modular_graph.m., Accessed: 2017-07-20.

[3]

SNAP Datasets: Stanford Large Network Dataset Collection, http://snap.stanford.edu/data, Accessed: 2017-07-01.

[4]

R. Albert, H. Jeong and A.-L. Barabási, Internet: Diameter of the world-wide web, Nature, (1999), 130–131.

[5]

S. M. Allen and J. W. Cahn, A microscopic theory for antiphase boundary motion and its application to antiphase domain coarsening, Acta Metallurgica, 27 (1979), 1085-1095.  doi: 10.1016/0001-6160(79)90196-2.

[6]

L. Ambrosio, N. Gigli and G. Savaré, Gradient Flows: In Metric Spaces and in the Space of Probability Measures, Springer Science & Business Media, 2008.

[7]

A.-L. Barabási, Scale-free networks: A decade and beyond, Science, (2002), 412–413.

[8]

A.-L. Barabási and E. Bonabeau, Scale-free, Scientific American, (2003), 50–59.

[9]

F. Barahona, M. Grötschel, M. Jünger and G. Reinhelt, An application of combinatorial optimization to statistical physics and circuit layout design, Scientific American, (2003), 50–59.

[10]

G. Barles and C. Georgelin, A simple proof of convergence for an approximation scheme for computing motions by mean curvature, SIAM Journal on Numerical Analysis, 32 (1995), 484-500.  doi: 10.1137/0732020.

[11]

A. L. Bertozzi and A. Flenner, Diffuse interface models on graphs for classification of high dimensional data, Multiscale Modeling & Simulation, 10 (2012), 1090-1118.  doi: 10.1137/11083109X.

[12]

B. Bollobás, Modern Graph Theory, Graduate Texts in Mathematics, 184. Springer-Verlag, New York, 1998. doi: 10.1007/978-1-4612-0619-4.

[13] A. Braides, Gamma-convergence for Beginners, Clarendon Press, 2002.  doi: 10.1093/acprof:oso/9780198507840.001.0001.
[14]

L. Bronsard and R. V. Kohn, Motion by mean curvature as the singular limit of Ginzburg–Landau dynamics, Journal of Differential Equations, 90 (1991), 211-237.  doi: 10.1016/0022-0396(91)90147-2.

[15]

S. Bylka, A. Idzik and Z. Tuza, Maximum cuts: Improvements and local algorithmic analogues of the Edwards–Erdös inequality, Discrete Mathematics, 194 (1999), 39-58.  doi: 10.1016/S0012-365X(98)00115-0.

[16]

L. Calatroni, Y. van Gennip, C.-B. Schönlieb, H. M. Rowland and A. Flenner, Graph clustering, variational image segmentation methods and Hough transform scale detection for object measurement in images, Journal of Mathematical Imaging and Vision, 57 (2017), 269-291.  doi: 10.1007/s10851-016-0678-0.

[17]

D. Calvetti, L. Reichel and D. C. Sorensen, An implicitly restarted Lanczos method for large symmetric eigenvalue problems, Electronic Transactions on Numerical Analysis, 2 (1994), 1-21. 

[18]

F. R. K. Chung, Spectral Graph Theory, American Mathematical Society, 1997.

[19]

R. Courant and D. Hilbert, Methods of Mathematical Physics, CUP Archive, 1965.

[20]

G. Dal Maso, An Introduction to $\Gamma$-convergence, in Progress in Nonlinear Differential Equations and Their Applications, Birkhäuser, 1993. doi: 10.1007/978-1-4612-0327-8.

[21]

M. Desai and V. Rao, A characterization of the smallest eigenvalue of a graph, Journal of Graph Theory, 18 (1994), 181-194.  doi: 10.1002/jgt.3190180210.

[22]

S. Esedo${\rm{\tilde g}}$lu and F. Otto, Threshold dynamics for networks with arbitrary surface tensions, Communications on Pure and Applied Mathematics, 68 (2015), 808-864.  doi: 10.1002/cpa.21527.

[23]

J. G. F. Francis, The QR transformation a unitary analogue to the LR transformation—Part 1, The Computer Journal, 4 (1961), 265-271.  doi: 10.1093/comjnl/4.3.265.

[24]

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, San Francisco, LA: Freeman, 1979.

[25]

M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), 42 (1995), 1115-1145.  doi: 10.1145/227683.227684.

[26]

G. H. Golub and C. F. van Loan, Matrix Computations, Fourth edition. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, 2013.

[27]

M. Grötschel and W. R. Pulleyblank, Weakly bipartite graphs and the Max-Cut problem, Operations Research Letters, 1 (1981), 23-27.  doi: 10.1016/0167-6377(81)90020-1.

[28]

J.-M. Guo, A new upper bound for the Laplacian spectral radius of graphs, Linear Algebra and Its Applications, 400 (2005), 61-66.  doi: 10.1016/j.laa.2004.10.022.

[29]

V. Guruswami, Maximum cut on line and total graphs, Discrete Applied Mathematics, 92 (1999), 217-221.  doi: 10.1016/S0166-218X(99)00056-6.

[30]

F. Hadlock, Finding a maximum cut of a planar graph in polynomial time, SIAM Journal on Computing, 4 (1975), 221-225.  doi: 10.1137/0204019.

[31]

Y. Haribara, S. Utsunomiya and Y. Yamamoto, A coherent Ising machine for MAX-CUT problems: Performance evaluation against semidefinite programming and simulated annealing, in Principles and Methods of Quantum Information Technologies Springer, 911 (2016), 251–262. doi: 10.1007/978-4-431-55756-2_12.

[32]

M. Hein, J.-Y. Audibert and U. von Luxburg, Graph Laplacians and their convergence on random neighborhood graphs, Journal of Machine Learning Research, 8 (2007), 1325-1368. 

[33]

H. Hu, T. Laurent, M. A. Porter and A. L. Bertozzi, A method based on total variation for network modularity optimization using the MBO scheme, SIAM Journal on Applied Mathematics, 73 (2013), 2224-2246.  doi: 10.1137/130917387.

[34]

C.-Y. Kao and Y. van Gennip,, Private communication.

[35]

R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations, Springer, (1972), 85–103.

[36]

S. Khot, On the power of unique 2-prover 1-round games, in Proceedings of the thirty-fourth Annual ACM Symposium on Theory of Computing, ACM, (2002), 767–775. doi: 10.1145/509907.510017.

[37]

S. Khot, G. Kindler, E. Mossel and R. O'Donnell, Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?, SIAM Journal on Computing, 37 (2007), 319-357.  doi: 10.1137/S0097539705447372.

[38]

J. B. Lasserre, A MAX-CUT formulation of 0/1 programs, Operations Research Letters, 44 (2016), 158-164.  doi: 10.1016/j.orl.2015.12.014.

[39]

R. B. Lehoucq and D. C. Sorensen, Deflation techniques for an implicitly restarted Arnoldi iteration, SIAM Journal on Matrix Analysis and Applications, 17 (1996), 789-821.  doi: 10.1137/S0895479895281484.

[40]

E. Merkurjev, T. Kostic and A. L. Bertozzi, An MBO scheme on graphs for classification and image processing, SIAM Journal on Imaging Sciences, 6 (2013), 1903-1930.  doi: 10.1137/120886935.

[41]

B. Merriman, J. Bence and S. Osher, Diffusion Generated Motion by Mean Curvature, UCLA Department of Mathematics CAM report CAM 06–32, 1992.

[42]

B. Merriman, J. Bence and S. Osher, Diffusion generated motion by mean curvature, AMS Selected Letters, Crystal Grower's Workshop, (1993), 73–83.

[43]

H. D. Mittelmann, The state-of-the-art in conic optimization software, in Handbook on Semidefinite, Conic and Polynomial Optimization Springer, 166 (2012), 671–686. doi: 10.1007/978-1-4614-0769-0_23.

[44]

L. Modica and S. Mortola, Un esempio di $\Gamma^-$-convergenza, Boll. Un. Mat. Ital. B (5), 14 (1977), 285-299. 

[45]

L. Modica, The gradient theory of phase transitions and the minimal interface criterion, Archive for Rational Mechanics and Analysis, 98 (1987), 123-142.  doi: 10.1007/BF00251230.

[46]

B. Mohar, The Laplacian spectrum of graphs, in Graph Theory, Combinatorics, and Applications, Volume 2, Wiley, (1991), 871–898.

[47]

R. J. Radke, A Matlab Implementation of the Implicitly Restarted Arnoldi Method for Solving Large-scale Eigenvalue Problems, Masters thesis, Rice University, 1996.

[48]

W. Rudin, Principles of Mathematical Analysis, McGraw-hill New York, 1964.

[49]

J.-L. Shu, Y. Hong and K. Wen-Ren, A sharp upper bound on the largest eigenvalue of the Laplacian matrix of a graph, Linear Algebra and Its Applications, 347 (2002), 123-129.  doi: 10.1016/S0024-3795(01)00548-1.

[50]

D. C. Sorensen, Implicitly restarted Arnoldi/Lanczos methods for large scale eigenvalue calculations, in Parallel Numerical Algorithms, Springer, 4 (1997), 119–165. doi: 10.1007/978-94-011-5412-3_5.

[51]

J. A. Soto, Improved analysis of a Max-Cut algorithm based on spectral partitioning, SIAM Journal on Discrete Mathematics, 29 (2015), 259-268.  doi: 10.1137/14099098X.

[52]

L. Trevisan, G. B. Sorkin, M. Sudan and D. P. Williamson, Gadgets, approximation, and linear programming, SIAM Journal on Computing, 29 (2000), 2074-2097.  doi: 10.1137/S0097539797328847.

[53]

L. Trevisan, Max-cut and the smallest eigenvalue, SIAM Journal on Computing, 41 (2012), 1769-1786.  doi: 10.1137/090773714.

[54]

R. H. Tütüncü, K.-C. Toh and M. Todd, Solving semidefinite-quadratic-linear programs using SDPT3, Mathematical Programming, 95 (2003), 189-217.  doi: 10.1007/s10107-002-0347-5.

[55]

Y. van Gennip and A. L. Bertozzi, $\Gamma$-convergence of graph Ginzburg-Landau functionals, Advances in Differential Equations, 17 (2012), 1115-1180. 

[56]

Y. van Gennip, N. Guillen, B. Osting and A. L. Bertozzi, Mean curvature, threshold dynamics, and phase field theory on finite graphs, Milan Journal of Mathematics, 82 (2014), 3-65.  doi: 10.1007/s00032-014-0216-8.

[57]

Y. van Gennip, An MBO scheme for minimizing the graph Ohta–Kawasaki functional, Journal Of Nonlinear Science, 2018.

[58]

U. von Luxburg, A tutorial on spectral clustering, Statistics and computing, 17 (2007), 395-416.  doi: 10.1007/s11222-007-9033-z.

[59]

X.-D. Zhang, The signless Laplacian spectral radius of graphs with given degree sequences, Discrete Applied Mathematics, 157 (2009), 2928-2937.  doi: 10.1016/j.dam.2009.02.022.

show all references

References:
[1]

University of Ioannina, Department of Computer Science and Engineering Teaching Resources, http://www.cs.uoi.gr/tsap/teaching/InformationNetworks/data-code.html., Accessed: 2017-03-13.

[2]

MIT Strategic Engineering Research Group: Matlab Tools for Network Analysis (2006-2011), http://strategic.mit.edu/docs/matlab_networks/random_modular_graph.m., Accessed: 2017-07-20.

[3]

SNAP Datasets: Stanford Large Network Dataset Collection, http://snap.stanford.edu/data, Accessed: 2017-07-01.

[4]

R. Albert, H. Jeong and A.-L. Barabási, Internet: Diameter of the world-wide web, Nature, (1999), 130–131.

[5]

S. M. Allen and J. W. Cahn, A microscopic theory for antiphase boundary motion and its application to antiphase domain coarsening, Acta Metallurgica, 27 (1979), 1085-1095.  doi: 10.1016/0001-6160(79)90196-2.

[6]

L. Ambrosio, N. Gigli and G. Savaré, Gradient Flows: In Metric Spaces and in the Space of Probability Measures, Springer Science & Business Media, 2008.

[7]

A.-L. Barabási, Scale-free networks: A decade and beyond, Science, (2002), 412–413.

[8]

A.-L. Barabási and E. Bonabeau, Scale-free, Scientific American, (2003), 50–59.

[9]

F. Barahona, M. Grötschel, M. Jünger and G. Reinhelt, An application of combinatorial optimization to statistical physics and circuit layout design, Scientific American, (2003), 50–59.

[10]

G. Barles and C. Georgelin, A simple proof of convergence for an approximation scheme for computing motions by mean curvature, SIAM Journal on Numerical Analysis, 32 (1995), 484-500.  doi: 10.1137/0732020.

[11]

A. L. Bertozzi and A. Flenner, Diffuse interface models on graphs for classification of high dimensional data, Multiscale Modeling & Simulation, 10 (2012), 1090-1118.  doi: 10.1137/11083109X.

[12]

B. Bollobás, Modern Graph Theory, Graduate Texts in Mathematics, 184. Springer-Verlag, New York, 1998. doi: 10.1007/978-1-4612-0619-4.

[13] A. Braides, Gamma-convergence for Beginners, Clarendon Press, 2002.  doi: 10.1093/acprof:oso/9780198507840.001.0001.
[14]

L. Bronsard and R. V. Kohn, Motion by mean curvature as the singular limit of Ginzburg–Landau dynamics, Journal of Differential Equations, 90 (1991), 211-237.  doi: 10.1016/0022-0396(91)90147-2.

[15]

S. Bylka, A. Idzik and Z. Tuza, Maximum cuts: Improvements and local algorithmic analogues of the Edwards–Erdös inequality, Discrete Mathematics, 194 (1999), 39-58.  doi: 10.1016/S0012-365X(98)00115-0.

[16]

L. Calatroni, Y. van Gennip, C.-B. Schönlieb, H. M. Rowland and A. Flenner, Graph clustering, variational image segmentation methods and Hough transform scale detection for object measurement in images, Journal of Mathematical Imaging and Vision, 57 (2017), 269-291.  doi: 10.1007/s10851-016-0678-0.

[17]

D. Calvetti, L. Reichel and D. C. Sorensen, An implicitly restarted Lanczos method for large symmetric eigenvalue problems, Electronic Transactions on Numerical Analysis, 2 (1994), 1-21. 

[18]

F. R. K. Chung, Spectral Graph Theory, American Mathematical Society, 1997.

[19]

R. Courant and D. Hilbert, Methods of Mathematical Physics, CUP Archive, 1965.

[20]

G. Dal Maso, An Introduction to $\Gamma$-convergence, in Progress in Nonlinear Differential Equations and Their Applications, Birkhäuser, 1993. doi: 10.1007/978-1-4612-0327-8.

[21]

M. Desai and V. Rao, A characterization of the smallest eigenvalue of a graph, Journal of Graph Theory, 18 (1994), 181-194.  doi: 10.1002/jgt.3190180210.

[22]

S. Esedo${\rm{\tilde g}}$lu and F. Otto, Threshold dynamics for networks with arbitrary surface tensions, Communications on Pure and Applied Mathematics, 68 (2015), 808-864.  doi: 10.1002/cpa.21527.

[23]

J. G. F. Francis, The QR transformation a unitary analogue to the LR transformation—Part 1, The Computer Journal, 4 (1961), 265-271.  doi: 10.1093/comjnl/4.3.265.

[24]

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, San Francisco, LA: Freeman, 1979.

[25]

M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), 42 (1995), 1115-1145.  doi: 10.1145/227683.227684.

[26]

G. H. Golub and C. F. van Loan, Matrix Computations, Fourth edition. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, 2013.

[27]

M. Grötschel and W. R. Pulleyblank, Weakly bipartite graphs and the Max-Cut problem, Operations Research Letters, 1 (1981), 23-27.  doi: 10.1016/0167-6377(81)90020-1.

[28]

J.-M. Guo, A new upper bound for the Laplacian spectral radius of graphs, Linear Algebra and Its Applications, 400 (2005), 61-66.  doi: 10.1016/j.laa.2004.10.022.

[29]

V. Guruswami, Maximum cut on line and total graphs, Discrete Applied Mathematics, 92 (1999), 217-221.  doi: 10.1016/S0166-218X(99)00056-6.

[30]

F. Hadlock, Finding a maximum cut of a planar graph in polynomial time, SIAM Journal on Computing, 4 (1975), 221-225.  doi: 10.1137/0204019.

[31]

Y. Haribara, S. Utsunomiya and Y. Yamamoto, A coherent Ising machine for MAX-CUT problems: Performance evaluation against semidefinite programming and simulated annealing, in Principles and Methods of Quantum Information Technologies Springer, 911 (2016), 251–262. doi: 10.1007/978-4-431-55756-2_12.

[32]

M. Hein, J.-Y. Audibert and U. von Luxburg, Graph Laplacians and their convergence on random neighborhood graphs, Journal of Machine Learning Research, 8 (2007), 1325-1368. 

[33]

H. Hu, T. Laurent, M. A. Porter and A. L. Bertozzi, A method based on total variation for network modularity optimization using the MBO scheme, SIAM Journal on Applied Mathematics, 73 (2013), 2224-2246.  doi: 10.1137/130917387.

[34]

C.-Y. Kao and Y. van Gennip,, Private communication.

[35]

R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations, Springer, (1972), 85–103.

[36]

S. Khot, On the power of unique 2-prover 1-round games, in Proceedings of the thirty-fourth Annual ACM Symposium on Theory of Computing, ACM, (2002), 767–775. doi: 10.1145/509907.510017.

[37]

S. Khot, G. Kindler, E. Mossel and R. O'Donnell, Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?, SIAM Journal on Computing, 37 (2007), 319-357.  doi: 10.1137/S0097539705447372.

[38]

J. B. Lasserre, A MAX-CUT formulation of 0/1 programs, Operations Research Letters, 44 (2016), 158-164.  doi: 10.1016/j.orl.2015.12.014.

[39]

R. B. Lehoucq and D. C. Sorensen, Deflation techniques for an implicitly restarted Arnoldi iteration, SIAM Journal on Matrix Analysis and Applications, 17 (1996), 789-821.  doi: 10.1137/S0895479895281484.

[40]

E. Merkurjev, T. Kostic and A. L. Bertozzi, An MBO scheme on graphs for classification and image processing, SIAM Journal on Imaging Sciences, 6 (2013), 1903-1930.  doi: 10.1137/120886935.

[41]

B. Merriman, J. Bence and S. Osher, Diffusion Generated Motion by Mean Curvature, UCLA Department of Mathematics CAM report CAM 06–32, 1992.

[42]

B. Merriman, J. Bence and S. Osher, Diffusion generated motion by mean curvature, AMS Selected Letters, Crystal Grower's Workshop, (1993), 73–83.

[43]

H. D. Mittelmann, The state-of-the-art in conic optimization software, in Handbook on Semidefinite, Conic and Polynomial Optimization Springer, 166 (2012), 671–686. doi: 10.1007/978-1-4614-0769-0_23.

[44]

L. Modica and S. Mortola, Un esempio di $\Gamma^-$-convergenza, Boll. Un. Mat. Ital. B (5), 14 (1977), 285-299. 

[45]

L. Modica, The gradient theory of phase transitions and the minimal interface criterion, Archive for Rational Mechanics and Analysis, 98 (1987), 123-142.  doi: 10.1007/BF00251230.

[46]

B. Mohar, The Laplacian spectrum of graphs, in Graph Theory, Combinatorics, and Applications, Volume 2, Wiley, (1991), 871–898.

[47]

R. J. Radke, A Matlab Implementation of the Implicitly Restarted Arnoldi Method for Solving Large-scale Eigenvalue Problems, Masters thesis, Rice University, 1996.

[48]

W. Rudin, Principles of Mathematical Analysis, McGraw-hill New York, 1964.

[49]

J.-L. Shu, Y. Hong and K. Wen-Ren, A sharp upper bound on the largest eigenvalue of the Laplacian matrix of a graph, Linear Algebra and Its Applications, 347 (2002), 123-129.  doi: 10.1016/S0024-3795(01)00548-1.

[50]

D. C. Sorensen, Implicitly restarted Arnoldi/Lanczos methods for large scale eigenvalue calculations, in Parallel Numerical Algorithms, Springer, 4 (1997), 119–165. doi: 10.1007/978-94-011-5412-3_5.

[51]

J. A. Soto, Improved analysis of a Max-Cut algorithm based on spectral partitioning, SIAM Journal on Discrete Mathematics, 29 (2015), 259-268.  doi: 10.1137/14099098X.

[52]

L. Trevisan, G. B. Sorkin, M. Sudan and D. P. Williamson, Gadgets, approximation, and linear programming, SIAM Journal on Computing, 29 (2000), 2074-2097.  doi: 10.1137/S0097539797328847.

[53]

L. Trevisan, Max-cut and the smallest eigenvalue, SIAM Journal on Computing, 41 (2012), 1769-1786.  doi: 10.1137/090773714.

[54]

R. H. Tütüncü, K.-C. Toh and M. Todd, Solving semidefinite-quadratic-linear programs using SDPT3, Mathematical Programming, 95 (2003), 189-217.  doi: 10.1007/s10107-002-0347-5.

[55]

Y. van Gennip and A. L. Bertozzi, $\Gamma$-convergence of graph Ginzburg-Landau functionals, Advances in Differential Equations, 17 (2012), 1115-1180. 

[56]

Y. van Gennip, N. Guillen, B. Osting and A. L. Bertozzi, Mean curvature, threshold dynamics, and phase field theory on finite graphs, Milan Journal of Mathematics, 82 (2014), 3-65.  doi: 10.1007/s00032-014-0216-8.

[57]

Y. van Gennip, An MBO scheme for minimizing the graph Ohta–Kawasaki functional, Journal Of Nonlinear Science, 2018.

[58]

U. von Luxburg, A tutorial on spectral clustering, Statistics and computing, 17 (2007), 395-416.  doi: 10.1007/s11222-007-9033-z.

[59]

X.-D. Zhang, The signless Laplacian spectral radius of graphs with given degree sequences, Discrete Applied Mathematics, 157 (2009), 2928-2937.  doi: 10.1016/j.dam.2009.02.022.

Figure 1.  The value $ f_{\varepsilon}^+(\mu^j) $ as a function of the iteration number $ j $ in the (MBO+) scheme on AS8Graph, using the spectral method and $ \Delta_1^+ $, with $ K = 100 $, and $ \tau = 20 $. The left hand plot shows the initial condition and all iterations of the (MBO+) scheme on AS8Graph, where as the right hand plot displays the 3rd to the final iterations of the (MBO+) scheme on AS8Graph
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  The value $ f_{\varepsilon}^+(\mu^j) $ as a function of the iteration number $ j $ in the (MBO+) scheme on the GNutella09 graph, using the spectral method and $ \Delta_1^+ $, with $ K = 100 $, and $ \tau = 20 $. The left hand plot shows the initial condition and all iterations of the (MBO+) scheme on GNutella09, where as the right hand plot displays all iterations of the (MBO+) scheme on GNutella09, without the initial condition
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  Visualisation of maximum cut approximations (best viewed in colour)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  Bar chart of Max-Cut approximations on 100 realisations of $ G(1000, 0.01) $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  Bar chart of Max-Cut approximations on 100 realisations of $ G(2500, 0.4) $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6.  Bar chart of Max-Cut approximations on 100 realisations of $ G(5000, 0.001) $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 7.  Average degree distribution of 100 realisations of a random graph and the degree distribution of a scale free graph
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 8.  A Max-Cut approximation on a random 4-modular graph (best viewed in colour)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 9.  Bar chart of Max-Cut approximations on 100 realisations of $ R(2500, 2, 0.009, 0.8) $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 10.  Bar chart of Max-Cut approximations on 100 realisations of $ R(4000, 20, 0.01, 0.7) $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 11.  Bar chart of Max-Cut approximations on 100 realisations of $ R(10000, 10, 0.01, 0.8) $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 12.  Cut size as function of $ K $ for three graphs (best viewed in colour)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 13.  Comparison of cut size approximation vs $ K $ on Amazon0302 graph
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 14.  Cut size as function of $ \tau $ for three graphs (best viewed in colour)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 15.  Bar chart of Max-Cut approximations on 100 realisations of $ G(1000, 0.01) $ using the implicit Euler method and the explicit Euler method
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 16.  Bar chart of Max-Cut approximations on 100 realisations of $ R(4000, 20, 0.01, 0.7) $
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  Average (MBO+) and (GW) run-times for each realisation of $ G(n, p) $, time in seconds
Graph $ \Delta_1^+ $ (S) $ \Delta_1^+ $ (E) $ \Delta_s^+ $ (S) $ \Delta_s^+ $ (E) $ \Delta_0^+ $ (S) $ \Delta_0^+ $ (E) GW
$ G(1000, 0.01) $ 0.20 1.58 0.34 1.52 0.56 1.06 5.25
$ G(2500, 0.4) $ 8.04 172.91 13.33 181.40 6.40 172.73 55.36
$ G(5000, 0.001) $ 4.38 16.96 6.37 14.95 24.99 6.97 257.09
Table Options

Download as excel

Graph $ \Delta_1^+ $ (S) $ \Delta_1^+ $ (E) $ \Delta_s^+ $ (S) $ \Delta_s^+ $ (E) $ \Delta_0^+ $ (S) $ \Delta_0^+ $ (E) GW
$ G(1000, 0.01) $ 0.20 1.58 0.34 1.52 0.56 1.06 5.25
$ G(2500, 0.4) $ 8.04 172.91 13.33 181.40 6.40 172.73 55.36
$ G(5000, 0.001) $ 4.38 16.96 6.37 14.95 24.99 6.97 257.09
Table 6.  (GW) cut approximations on graphs with a scale free structure, time in seconds
Graph GW Best GW Avg GW Least GW Time
AS1 22864 22346.26 20546 2324.98
AS2 13328 13039.10 12048 594.29
AS3 15240 14961.56 14050 826.65
AS4 15328 15015.34 14072 832.28
AS5 14190 13810.82 12922 721.51
AS6 18191 17851.24 16483 1368.35
AS7 22901 22421.80 21244 2321.34
AS8 23170 22593.10 21110 2613.62
GNutella09 20658 20242.02 18815 1095.04
Wiki-Vote 73363 71510 62886 1074.98
Table Options

Download as excel

Graph GW Best GW Avg GW Least GW Time
AS1 22864 22346.26 20546 2324.98
AS2 13328 13039.10 12048 594.29
AS3 15240 14961.56 14050 826.65
AS4 15328 15015.34 14072 832.28
AS5 14190 13810.82 12922 721.51
AS6 18191 17851.24 16483 1368.35
AS7 22901 22421.80 21244 2321.34
AS8 23170 22593.10 21110 2613.62
GNutella09 20658 20242.02 18815 1095.04
Wiki-Vote 73363 71510 62886 1074.98
Table 2.  Properties of $ G(n, p) $ graph realisations vs scale free graphs
Graph $ |V| $ $ |E| $ $ d_{-} $ $ d_{+} $
$ G(1000, 0.01) $(1) 1000 4919 1 21
$ G(1000, 0.01) $(2) 1000 4939 2 21
$ G(2500, 0.4) $(1) 2500 1248937 910 1079
$ G(2500, 0.4) $(2) 2500 1251182 904 1081
$ G(5000, 0.001) $(1) 4962 12646 1 16
$ G(5000, 0.001) $(2) 4969 12642 1 16
Graph $|V|$ $|E|$ $d_{-}$ $d_{+}$
AS1126942655912566
AS276901541311713
AS386891770911911
AS489041765311921
GNutella098114260131102
Wiki-Vote711510076211065
Table Options

Download as excel

Graph $ |V| $ $ |E| $ $ d_{-} $ $ d_{+} $
$ G(1000, 0.01) $(1) 1000 4919 1 21
$ G(1000, 0.01) $(2) 1000 4939 2 21
$ G(2500, 0.4) $(1) 2500 1248937 910 1079
$ G(2500, 0.4) $(2) 2500 1251182 904 1081
$ G(5000, 0.001) $(1) 4962 12646 1 16
$ G(5000, 0.001) $(2) 4969 12642 1 16
Graph $|V|$ $|E|$ $d_{-}$ $d_{+}$
AS1126942655912566
AS276901541311713
AS386891770911911
AS489041765311921
GNutella098114260131102
Wiki-Vote711510076211065
Table 3.  (MBO+) cut approximations using $ \Delta_1^+ $ on graphs with a scale free structure, time in seconds
Graph $ \Delta_1^+ $ (S) Best $ \Delta_1^+ $ (S) Avg $ \Delta_1^+ $ (S) Least $ \Delta_1^+ $ (S) Time
AS1 22744 22542.20 22183 $ {\bf{15.85}} $
AS2 13249 13153.72 13054 $ {\bf{3.55}} $
AS3 15118 15027.22 14907 4.73
AS4 15194 15143.44 15042 $ {\bf{5.67}} $
AS5 14080 13988.90 13928 $ {\bf{4.82}} $
AS6 18053 17964.74 17876 10.06
AS7 22741 22535.00 22150 17.82
AS8 22990 22720.36 22334 17.22
GNutella09 20280 20143.74 19983 8.16
WikiVote 72981 72856.40 72744 2.46
Graph $\Delta_1^+$ (E) Best $\Delta_1^+$ (E) Avg $\Delta_1^+$ (E) Least $\Delta_1^+$ (E) Time
AS122798 22670.762226823.62
AS213281 13199.72 131208.76
AS315175 15095.46 150079.95
AS415270 15202.70 1511710.88
AS514120 14020.62 139449.50
AS618134 18034.10 1793316.50
AS722826 22696.42 2252525.78
AS823070 22951.54 2255025.38
GNutella0920437 20361.92 2029517.14
WikiVote73159 73126.34 730869.06
Table Options

Download as excel

Graph $ \Delta_1^+ $ (S) Best $ \Delta_1^+ $ (S) Avg $ \Delta_1^+ $ (S) Least $ \Delta_1^+ $ (S) Time
AS1 22744 22542.20 22183 $ {\bf{15.85}} $
AS2 13249 13153.72 13054 $ {\bf{3.55}} $
AS3 15118 15027.22 14907 4.73
AS4 15194 15143.44 15042 $ {\bf{5.67}} $
AS5 14080 13988.90 13928 $ {\bf{4.82}} $
AS6 18053 17964.74 17876 10.06
AS7 22741 22535.00 22150 17.82
AS8 22990 22720.36 22334 17.22
GNutella09 20280 20143.74 19983 8.16
WikiVote 72981 72856.40 72744 2.46
Graph $\Delta_1^+$ (E) Best $\Delta_1^+$ (E) Avg $\Delta_1^+$ (E) Least $\Delta_1^+$ (E) Time
AS122798 22670.762226823.62
AS213281 13199.72 131208.76
AS315175 15095.46 150079.95
AS415270 15202.70 1511710.88
AS514120 14020.62 139449.50
AS618134 18034.10 1793316.50
AS722826 22696.42 2252525.78
AS823070 22951.54 2255025.38
GNutella0920437 20361.92 2029517.14
WikiVote73159 73126.34 730869.06
Table 4.  (MBO+) cut approximations using $ \Delta_s^+ $ on graphs with a scale free structure, time in seconds
Graph $ \Delta_s^+ $ (S) Best $ \Delta_s^+ $ (S) Avg $ \Delta_s^+ $ (S) Least $ \Delta_s^+ $ (S) Time
AS1 22809 22620.8 $ {\bf{22325}} $ 17.83
AS2 13271 13178.86 13103 4.12
AS3 15166 15082.1 14992 $ {\bf{4.66}} $
AS4 15237 15166.24 15077 5.78
AS5 14075 14011.96 13911 5.47
AS6 18088 17968.04 17859 $ {\bf{9.14}} $
AS7 22822 22629.66 22218 $ {\bf{15.73}} $
AS8 23061 22884.8 22547 $ {\bf{15.46}} $
GNutella09 20282 20186.32 20101 $ {\bf{6.82}} $
WikiVote 73169 73003.44 72917 $ {\bf{2.25}} $
Graph $\Delta_s^+$ (E) Best $\Delta_s^+$ (E) Avg $\Delta_s^+$ (E) Least $\Delta_s^+$ (E) Time
AS12278922629.622226127.63
AS21325613176.64130949.09
AS31513915059.541496710.24
AS41523415159.761507911.57
AS51409614011.91393010.47
AS61808817994.661787616.12
AS72282322639.582223724.5
AS823036228652244025.08
GNutella092039720332.282017018.75
WikiVote7299372772.26725499.00
Table Options

Download as excel

Graph $ \Delta_s^+ $ (S) Best $ \Delta_s^+ $ (S) Avg $ \Delta_s^+ $ (S) Least $ \Delta_s^+ $ (S) Time
AS1 22809 22620.8 $ {\bf{22325}} $ 17.83
AS2 13271 13178.86 13103 4.12
AS3 15166 15082.1 14992 $ {\bf{4.66}} $
AS4 15237 15166.24 15077 5.78
AS5 14075 14011.96 13911 5.47
AS6 18088 17968.04 17859 $ {\bf{9.14}} $
AS7 22822 22629.66 22218 $ {\bf{15.73}} $
AS8 23061 22884.8 22547 $ {\bf{15.46}} $
GNutella09 20282 20186.32 20101 $ {\bf{6.82}} $
WikiVote 73169 73003.44 72917 $ {\bf{2.25}} $
Graph $\Delta_s^+$ (E) Best $\Delta_s^+$ (E) Avg $\Delta_s^+$ (E) Least $\Delta_s^+$ (E) Time
AS12278922629.622226127.63
AS21325613176.64130949.09
AS31513915059.541496710.24
AS41523415159.761507911.57
AS51409614011.91393010.47
AS61808817994.661787616.12
AS72282322639.582223724.5
AS823036228652244025.08
GNutella092039720332.282017018.75
WikiVote7299372772.26725499.00
Table 5.  (MBO+) cut approximations using $ \Delta_0^+ $ on graphs with a scale free structure, time in seconds
Graph $ \Delta_0^+ $ (S) Best $ \Delta_0^+ $ (S) Avg $ \Delta_0^+ $ (S) Least $ \Delta_0^+ $ (S) Time
AS1 22578 22303.10 21844 297.79
AS2 13081 12935.80 12763 62.41
AS3 14995 14869.52 14702 90.32
AS4 15097 14994.92 14885 88.53
AS5 13952 13795.24 13561 70.81
AS6 17836 17672.50 17527 149.60
AS7 22571 22328.18 21932 294.26
AS8 22824 22585.88 22075 287.79
GNutella09 19079 18419.36 17951 72.03
WikiVote 65504 60599.74 56917 46.11
Table Options

Download as excel

Graph $ \Delta_0^+ $ (S) Best $ \Delta_0^+ $ (S) Avg $ \Delta_0^+ $ (S) Least $ \Delta_0^+ $ (S) Time
AS1 22578 22303.10 21844 297.79
AS2 13081 12935.80 12763 62.41
AS3 14995 14869.52 14702 90.32
AS4 15097 14994.92 14885 88.53
AS5 13952 13795.24 13561 70.81
AS6 17836 17672.50 17527 149.60
AS7 22571 22328.18 21932 294.26
AS8 22824 22585.88 22075 287.79
GNutella09 19079 18419.36 17951 72.03
WikiVote 65504 60599.74 56917 46.11
Table 7.  Average (MBO+) and (GW) run-times for each realisation of $ R(n, c, p, r) $, time in seconds
Graph $ \Delta_1^+ $ (S) $ \Delta_1^+ $ (E) $ \Delta_s^+ $ (S) $ \Delta_s^+ $ (E) $ \Delta_0^+ $ (S) $ \Delta_0^+ $ (E) GW
$ R(2500, 2, 0.009, 0.8) $ 0.80 10.43 0.79 10.26 4.36 6.13 56.30
$ R(4000, 20, 0.01, 0.7) $ 4.05 30.46 4.49 29.52 16.26 18.19 248.25
$ R(10000, 10, 0.01, 0.8) $ 49.98 266.10 52.85 266.40 210.94 194.52 3893.87
Table Options

Download as excel

Graph $ \Delta_1^+ $ (S) $ \Delta_1^+ $ (E) $ \Delta_s^+ $ (S) $ \Delta_s^+ $ (E) $ \Delta_0^+ $ (S) $ \Delta_0^+ $ (E) GW
$ R(2500, 2, 0.009, 0.8) $ 0.80 10.43 0.79 10.26 4.36 6.13 56.30
$ R(4000, 20, 0.01, 0.7) $ 4.05 30.46 4.49 29.52 16.26 18.19 248.25
$ R(10000, 10, 0.01, 0.8) $ 49.98 266.10 52.85 266.40 210.94 194.52 3893.87
Table 10.  (MBO+) cut approximations using $ \Delta_0^+ $ on randomly weighted graphs, time in seconds
Graph $ \Delta_0^+ $ (S) Best $ \Delta_0^+ $ (S) Avg $ \Delta_0^+ $ (S) Least $ \Delta_0^+ $ (S) Time
W1 3413.96 3345.32 3276.63 0.61
W2 34784.30 34304.33 33627.16 0.51
W3 1602346.52 1600022.33 1595791.12 $ {\bf{6.97}} $
W4 320251.52 319940.38 319663.40 $ {\bf{6.25}} $
W5 4793.44 4761.72 4715.51 18.66
W6 71219.49 70427.83 69643.31 18.93
W7 239991.72 237647.45 235617.15 19.17
W8 134097.55 131088.97 126123.70 272.56
W9 27528.99 26554.77 25501.34 69.63
W10 90271.70 88031.84 83130.60 264.89
Graph $\Delta_0^+$ (E) Best $\Delta_0^+$ (E) Avg $\Delta_0^+$ (E) Least $\Delta_0^+$ (E) Time
W13524.243456.553406.931.03
W235664.1835040.7134383.571.03
W31605419.971602251.821597064.59203.27
W4320321.63319809.73319237.08192.51
W55017.664983.904954.637.76
W674195.8773688.9773231.677.33
W7251330.73249754.88248091.067.51
W8----
W9----
W10----
Table Options

Download as excel

Graph $ \Delta_0^+ $ (S) Best $ \Delta_0^+ $ (S) Avg $ \Delta_0^+ $ (S) Least $ \Delta_0^+ $ (S) Time
W1 3413.96 3345.32 3276.63 0.61
W2 34784.30 34304.33 33627.16 0.51
W3 1602346.52 1600022.33 1595791.12 $ {\bf{6.97}} $
W4 320251.52 319940.38 319663.40 $ {\bf{6.25}} $
W5 4793.44 4761.72 4715.51 18.66
W6 71219.49 70427.83 69643.31 18.93
W7 239991.72 237647.45 235617.15 19.17
W8 134097.55 131088.97 126123.70 272.56
W9 27528.99 26554.77 25501.34 69.63
W10 90271.70 88031.84 83130.60 264.89
Graph $\Delta_0^+$ (E) Best $\Delta_0^+$ (E) Avg $\Delta_0^+$ (E) Least $\Delta_0^+$ (E) Time
W13524.243456.553406.931.03
W235664.1835040.7134383.571.03
W31605419.971602251.821597064.59203.27
W4320321.63319809.73319237.08192.51
W55017.664983.904954.637.76
W674195.8773688.9773231.677.33
W7251330.73249754.88248091.067.51
W8----
W9----
W10----
Table 11.  (GW) cut approximations on randomly weighted graphs, time in seconds
Graph GW Best GW Avg GW Least GW Time
W1 3585.17 3535.63 3494.26 5.74
W2 36101.30 35698.47 35151.60 6.07
W3 1620705.80 1618813.52 1616502.33 43.58
W4 323573.40 323275.84 322795.83 44.09
W5 5038.00 5000.74 4953.71 265.27
W6 74372.75 73852.36 73293.27 241.33
W7 251802.56 250316.08 248098.85 263.44
W8 138159.14 135899.20 129576.95 2629.60
W9 28705.35 28169.25 26422.54 689.16
W10 93547.26 91571.68 87487.99 2646.94
Table Options

Download as excel

Graph GW Best GW Avg GW Least GW Time
W1 3585.17 3535.63 3494.26 5.74
W2 36101.30 35698.47 35151.60 6.07
W3 1620705.80 1618813.52 1616502.33 43.58
W4 323573.40 323275.84 322795.83 44.09
W5 5038.00 5000.74 4953.71 265.27
W6 74372.75 73852.36 73293.27 241.33
W7 251802.56 250316.08 248098.85 263.44
W8 138159.14 135899.20 129576.95 2629.60
W9 28705.35 28169.25 26422.54 689.16
W10 93547.26 91571.68 87487.99 2646.94
Table 8.  (MBO+) cut approximations using $ \Delta_1^+ $ on randomly weighted graphs, time in seconds
Graph $ \Delta_1^+ $ (S) Best $ \Delta_1^+ $ (S) Avg $ \Delta_1^+ $ (S) Least $ \Delta_1^+ $ (S) Time
W1 3612.00 3569.08 3537.10 0.47
W2 36487.51 36082.58 35687.87 $ {\bf{0.30}} $
W3 1622125.53 $ {\bf{1620885.77}} $ $ {\bf{1619371.25}} $ 8.09
W4 323926.34 323639.05 $ {\bf{323321.92}} $ 8.59
W5 5054.26 5033.54 5010.38 $ {\bf{4.00}} $
W6 74560.24 74218.26 73776.17 $ {\bf{3.90}} $
W7 252448.52 251045.03 249459.89 4.18
W8 137202.14 135952.94 133480.08 16.17
W9 28351.01 28194.96 28009.15 $ {\bf{3.99}} $
W10 92376.49 91570.35 90172.90 17.02
Graph $\Delta_1^+$ (E) Best $\Delta_1^+$ (E) Avg $\Delta_1^+$ (E) Least $\Delta_1^+$ (E) Time
W1 3622.58 3580.533548.821.41
W2 36530.25 36191.16 35928.561.67
W31603390.761600505.431596558.94185.03
W4320347.01319612.93318849.26195.66
W5 5104.45 5081.95 5063.6415.31
W6 75499.50 75175.73 74833.8015.70
W7 255793.23 254569.97 253091.9115.71
W8137569.32 136896.1 136094.6023.83
W928545.45 28369.43 28141.769.24
W1093021.06 92489.04 91626.9925.37
Table Options

Download as excel

Graph $ \Delta_1^+ $ (S) Best $ \Delta_1^+ $ (S) Avg $ \Delta_1^+ $ (S) Least $ \Delta_1^+ $ (S) Time
W1 3612.00 3569.08 3537.10 0.47
W2 36487.51 36082.58 35687.87 $ {\bf{0.30}} $
W3 1622125.53 $ {\bf{1620885.77}} $ $ {\bf{1619371.25}} $ 8.09
W4 323926.34 323639.05 $ {\bf{323321.92}} $ 8.59
W5 5054.26 5033.54 5010.38 $ {\bf{4.00}} $
W6 74560.24 74218.26 73776.17 $ {\bf{3.90}} $
W7 252448.52 251045.03 249459.89 4.18
W8 137202.14 135952.94 133480.08 16.17
W9 28351.01 28194.96 28009.15 $ {\bf{3.99}} $
W10 92376.49 91570.35 90172.90 17.02
Graph $\Delta_1^+$ (E) Best $\Delta_1^+$ (E) Avg $\Delta_1^+$ (E) Least $\Delta_1^+$ (E) Time
W1 3622.58 3580.533548.821.41
W2 36530.25 36191.16 35928.561.67
W31603390.761600505.431596558.94185.03
W4320347.01319612.93318849.26195.66
W5 5104.45 5081.95 5063.6415.31
W6 75499.50 75175.73 74833.8015.70
W7 255793.23 254569.97 253091.9115.71
W8137569.32 136896.1 136094.6023.83
W928545.45 28369.43 28141.769.24
W1093021.06 92489.04 91626.9925.37
Table 12.  Properties of our large datasets we are testing on
Graph $ |V| $ $ |E| $ $ d_{-} $ $ d_{+} $
Amazon0302 262111 899792 1 420
Amazon0601 403394 2443408 1 2752
GNutella31 62586 147892 1 95
PA RoadNet 1088092 1541898 1 9
Email-Enron 36692 183831 1 1383
BerkStan-Web 685230 6649470 1 84290
Stanford 281904 1992636 1 38625
WWW1999 325729 1090108 1 10721
Table Options

Download as excel

Graph $ |V| $ $ |E| $ $ d_{-} $ $ d_{+} $
Amazon0302 262111 899792 1 420
Amazon0601 403394 2443408 1 2752
GNutella31 62586 147892 1 95
PA RoadNet 1088092 1541898 1 9
Email-Enron 36692 183831 1 1383
BerkStan-Web 685230 6649470 1 84290
Stanford 281904 1992636 1 38625
WWW1999 325729 1090108 1 10721
Table 13.  Results of (MBO+) using $ \Delta_1^+ $ and the Euler method on large datasets, time in hours
Graph $ \Delta_1^+ $ (E) Best $ \Delta_1^+ $ (E) Avg $ \Delta_1^+ $ (E) Min $ \Delta_1^+ $ (E) Time
Amazon0302 618942 618512.18 618030 0.49
Amazon0601 1580070 1576960.80 1571089 1.90
GNutella31 116552 116213.74 115916 0.06
PA RoadNet 1380131 1379797.90 1379416 0.64
Email-Enron 112665 111680.24 110279 0.02
BerkStan-Web 5335813 5319662.06 5281630 0.83
Stanford 1585802 1580445.14 1570469 0.47
WWW1999 813000 809329.52 806130 0.21
Table Options

Download as excel

Graph $ \Delta_1^+ $ (E) Best $ \Delta_1^+ $ (E) Avg $ \Delta_1^+ $ (E) Min $ \Delta_1^+ $ (E) Time
Amazon0302 618942 618512.18 618030 0.49
Amazon0601 1580070 1576960.80 1571089 1.90
GNutella31 116552 116213.74 115916 0.06
PA RoadNet 1380131 1379797.90 1379416 0.64
Email-Enron 112665 111680.24 110279 0.02
BerkStan-Web 5335813 5319662.06 5281630 0.83
Stanford 1585802 1580445.14 1570469 0.47
WWW1999 813000 809329.52 806130 0.21
Table 9.  (MBO+) cut approximations using $ \Delta_s^+ $ on randomly weighted graphs, time in seconds
Graph $ \Delta_s^+ $ (S) Best $ \Delta_s^+ $ (S) Avg $ \Delta_s^+ $ (S) Least $ \Delta_s^+ $ (S) Time
W1 3601.29 3569.23 3545.85 $ {\bf{0.33}} $
W2 36192.09 36059.80 35867.83 0.49
W3 $ {\bf{1622372.91}} $ 1620484 1618809.76 8.40
W4 $ {\bf{323933.40}} $ $ {\bf{323642.4}} $ 323114.45 7.65
W5 5068.19 5041.94 5015.16 4.50
W6 74844.37 74505.45 73963.79 4.67
W7 253043.96 251668.30 250600.35 $ {\bf{4.12}} $
W8 137195.52 136360.17 134856.06 $ {\bf{15.38}} $
W9 28389.38 28227.09 28067.66 4.12
W10 92439.42 91952.98 90488.33 $ {\bf{15.33}} $
Graph $\Delta_s^+$ (E) Best $\Delta_s^+$ (E) Avg $\Delta_s^+$ (E) Least $\Delta_s^+$ (E) Time
W13614.373577.563542.191.40
W236321.8036150.0535910.901.53
W31604257.121600145.681597577.4187.88
W4320691.88319596.27318900.13199.01
W55096.555072.365041.8915.9
W675456.8775089.7374745.1718.09
W7255316.85253821.64252527.1315.48
W8137282.02136475.24134333.124.51
W928445.9428258.6428101.229.18
W1092731.6292093.0590448.6124.36
Table Options

Download as excel

Graph $ \Delta_s^+ $ (S) Best $ \Delta_s^+ $ (S) Avg $ \Delta_s^+ $ (S) Least $ \Delta_s^+ $ (S) Time
W1 3601.29 3569.23 3545.85 $ {\bf{0.33}} $
W2 36192.09 36059.80 35867.83 0.49
W3 $ {\bf{1622372.91}} $ 1620484 1618809.76 8.40
W4 $ {\bf{323933.40}} $ $ {\bf{323642.4}} $ 323114.45 7.65
W5 5068.19 5041.94 5015.16 4.50
W6 74844.37 74505.45 73963.79 4.67
W7 253043.96 251668.30 250600.35 $ {\bf{4.12}} $
W8 137195.52 136360.17 134856.06 $ {\bf{15.38}} $
W9 28389.38 28227.09 28067.66 4.12
W10 92439.42 91952.98 90488.33 $ {\bf{15.33}} $
Graph $\Delta_s^+$ (E) Best $\Delta_s^+$ (E) Avg $\Delta_s^+$ (E) Least $\Delta_s^+$ (E) Time
W13614.373577.563542.191.40
W236321.8036150.0535910.901.53
W31604257.121600145.681597577.4187.88
W4320691.88319596.27318900.13199.01
W55096.555072.365041.8915.9
W675456.8775089.7374745.1718.09
W7255316.85253821.64252527.1315.48
W8137282.02136475.24134333.124.51
W928445.9428258.6428101.229.18
W1092731.6292093.0590448.6124.36
Table 14.  Cut sizes obtained by (MBO+) using the implicit Euler scheme on scale free graphs, time in seconds
Graph $ \Delta_1^+ $ Best $ \Delta_s^+ $ Best $ \Delta_0^+ $ Best
AS4 15276 15279 9259
AS8 23083 23033 13725
W9 28553.66 28485.28 17146.69
Graph $\Delta_1^+$ Avg $\Delta_s^+$ Avg $\Delta_0^+$ Avg
AS4 15196.5215175.529124.68
AS8 22934.3022844.1613585.56
W9 28360.4628294.4016847.92
Graph $\Delta_1^+$ Least $\Delta_s^+$ Least $\Delta_0^+$ Least
AS4 15124150568964
AS8 225212245413477
W9 28103.2828075.6216521.43
Graph $\Delta_1^+$ Time $\Delta_s^+$ Time $\Delta_0^+$ Time
AS447.8350.94 7.47
AS8105.22114.74 11.48
W938.6142.57 5.26
Table Options

Download as excel

Graph $ \Delta_1^+ $ Best $ \Delta_s^+ $ Best $ \Delta_0^+ $ Best
AS4 15276 15279 9259
AS8 23083 23033 13725
W9 28553.66 28485.28 17146.69
Graph $\Delta_1^+$ Avg $\Delta_s^+$ Avg $\Delta_0^+$ Avg
AS4 15196.5215175.529124.68
AS8 22934.3022844.1613585.56
W9 28360.4628294.4016847.92
Graph $\Delta_1^+$ Least $\Delta_s^+$ Least $\Delta_0^+$ Least
AS4 15124150568964
AS8 225212245413477
W9 28103.2828075.6216521.43
Graph $\Delta_1^+$ Time $\Delta_s^+$ Time $\Delta_0^+$ Time
AS447.8350.94 7.47
AS8105.22114.74 11.48
W938.6142.57 5.26
Table 15.  Average (MBO+) run-times for each realisation of $ G(1000, 0.01) $ and $ R(4000, 20, 0.01, 0.7) $, time in seconds. (I) indicates the implicit Euler method and (E) indicates the explicit Euler method
Graph $ \Delta_1^+ $ (I) $ \Delta_1^+ $ (E) $ \Delta_s^+ $ (I) $ \Delta_s^+ $ (E) $ \Delta_0^+ $ (I) $ \Delta_0^+ $ (E)
$ G(1000, 0.01) $ 3.36 1.82 3.28 1.79 2.20 1.19
$ R(4000, 20, 0.01, 0.7) $ 62.97 44.23 62.16 44.18 41.53 24.01
Table Options

Download as excel

Graph $ \Delta_1^+ $ (I) $ \Delta_1^+ $ (E) $ \Delta_s^+ $ (I) $ \Delta_s^+ $ (E) $ \Delta_0^+ $ (I) $ \Delta_0^+ $ (E)
$ G(1000, 0.01) $ 3.36 1.82 3.28 1.79 2.20 1.19
$ R(4000, 20, 0.01, 0.7) $ 62.97 44.23 62.16 44.18 41.53 24.01
[1]

Hans G. Kaper, Bixiang Wang, Shouhong Wang. Determining nodes for the Ginzburg-Landau equations of superconductivity. Discrete and Continuous Dynamical Systems, 1998, 4 (2) : 205-224. doi: 10.3934/dcds.1998.4.205
[2]

Dmitry Glotov, P. J. McKenna. Numerical mountain pass solutions of Ginzburg-Landau type equations. Communications on Pure and Applied Analysis, 2008, 7 (6) : 1345-1359. doi: 10.3934/cpaa.2008.7.1345
[3]

Kolade M. Owolabi, Edson Pindza. Numerical simulation of multidimensional nonlinear fractional Ginzburg-Landau equations. Discrete and Continuous Dynamical Systems - S, 2020, 13 (3) : 835-851. doi: 10.3934/dcdss.2020048
[4]

Dmitry Turaev, Sergey Zelik. Analytical proof of space-time chaos in Ginzburg-Landau equations. Discrete and Continuous Dynamical Systems, 2010, 28 (4) : 1713-1751. doi: 10.3934/dcds.2010.28.1713
[5]

Noboru Okazawa, Tomomi Yokota. Smoothing effect for generalized complex Ginzburg-Landau equations in unbounded domains. Conference Publications, 2001, 2001 (Special) : 280-288. doi: 10.3934/proc.2001.2001.280
[6]

N. I. Karachalios, H. E. Nistazakis, A. N. Yannacopoulos. Remarks on the asymptotic behavior of solutions of complex discrete Ginzburg-Landau equations. Conference Publications, 2005, 2005 (Special) : 476-486. doi: 10.3934/proc.2005.2005.476
[7]

Yuta Kugo, Motohiro Sobajima, Toshiyuki Suzuki, Tomomi Yokota, Kentarou Yoshii. Solvability of a class of complex Ginzburg-Landau equations in periodic Sobolev spaces. Conference Publications, 2015, 2015 (special) : 754-763. doi: 10.3934/proc.2015.0754
[8]

Bixiang Wang, Shouhong Wang. Gevrey class regularity for the solutions of the Ginzburg-Landau equations of superconductivity. Discrete and Continuous Dynamical Systems, 1998, 4 (3) : 507-522. doi: 10.3934/dcds.1998.4.507
[9]

Gregory A. Chechkin, Vladimir V. Chepyzhov, Leonid S. Pankratov. Homogenization of trajectory attractors of Ginzburg-Landau equations with randomly oscillating terms. Discrete and Continuous Dynamical Systems - B, 2018, 23 (3) : 1133-1154. doi: 10.3934/dcdsb.2018145
[10]

Lu Zhang, Aihong Zou, Tao Yan, Ji Shu. Weak pullback attractors for stochastic Ginzburg-Landau equations in Bochner spaces. Discrete and Continuous Dynamical Systems - B, 2022, 27 (2) : 749-768. doi: 10.3934/dcdsb.2021063
[11]

Mickaël Dos Santos, Oleksandr Misiats. Ginzburg-Landau model with small pinning domains. Networks and Heterogeneous Media, 2011, 6 (4) : 715-753. doi: 10.3934/nhm.2011.6.715
[12]

Fanghua Lin, Ping Zhang. On the hydrodynamic limit of Ginzburg-Landau vortices. Discrete and Continuous Dynamical Systems, 2000, 6 (1) : 121-142. doi: 10.3934/dcds.2000.6.121
[13]

Iuliana Oprea, Gerhard Dangelmayr. A period doubling route to spatiotemporal chaos in a system of Ginzburg-Landau equations for nematic electroconvection. Discrete and Continuous Dynamical Systems - B, 2019, 24 (1) : 273-296. doi: 10.3934/dcdsb.2018095
[14]

N. I. Karachalios, Hector E. Nistazakis, Athanasios N. Yannacopoulos. Asymptotic behavior of solutions of complex discrete evolution equations: The discrete Ginzburg-Landau equation. Discrete and Continuous Dynamical Systems, 2007, 19 (4) : 711-736. doi: 10.3934/dcds.2007.19.711
[15]

Dingshi Li, Xiaohu Wang. Asymptotic behavior of stochastic complex Ginzburg-Landau equations with deterministic non-autonomous forcing on thin domains. Discrete and Continuous Dynamical Systems - B, 2019, 24 (2) : 449-465. doi: 10.3934/dcdsb.2018181
[16]

Dingshi Li, Lin Shi, Xiaohu Wang. Long term behavior of stochastic discrete complex Ginzburg-Landau equations with time delays in weighted spaces. Discrete and Continuous Dynamical Systems - B, 2019, 24 (9) : 5121-5148. doi: 10.3934/dcdsb.2019046
[17]

Hong Lu, Mingji Zhang. Dynamics of non-autonomous fractional Ginzburg-Landau equations driven by colored noise. Discrete and Continuous Dynamical Systems - B, 2020, 25 (9) : 3553-3576. doi: 10.3934/dcdsb.2020072
[18]

Dandan Ma, Ji Shu, Ling Qin. Wong-Zakai approximations and asymptotic behavior of stochastic Ginzburg-Landau equations. Discrete and Continuous Dynamical Systems - B, 2020, 25 (11) : 4335-4359. doi: 10.3934/dcdsb.2020100
[19]

Yun Lan, Ji Shu. Dynamics of non-autonomous fractional stochastic Ginzburg-Landau equations with multiplicative noise. Communications on Pure and Applied Analysis, 2019, 18 (5) : 2409-2431. doi: 10.3934/cpaa.2019109
[20]

Tianlong Shen, Jianhua Huang. Ergodicity of the stochastic coupled fractional Ginzburg-Landau equations driven by α-stable noise. Discrete and Continuous Dynamical Systems - B, 2017, 22 (2) : 605-625. doi: 10.3934/dcdsb.2017029

2020 Impact Factor: 1.327

Tools

Metrics

  • PDF downloads (244)
  • HTML views (315)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy