• 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

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

Received  November 2017 Revised  June 2018 Published  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 $.

Citation: Blaine Keetch, Yves Van Gennip. A Max-Cut approximation using a graph based MBO scheme. Discrete & 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.Google Scholar

[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.Google Scholar

[3]

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

[4]

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

[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. Google Scholar

[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. Google Scholar

[7]

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

[8]

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

[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.Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[13] A. Braides, Gamma-convergence for Beginners, Clarendon Press, 2002. doi: 10.1093/acprof:oso/9780198507840.001.0001. Google Scholar
[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. Google Scholar

[15]

S. BylkaA. 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. Google Scholar

[16]

L. CalatroniY. van GennipC.-B. SchönliebH. 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. Google Scholar

[17]

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

[18]

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

[19]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[24]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[32]

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

[33]

H. HuT. LaurentM. 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. Google Scholar

[34]

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

[35]

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

[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. Google Scholar

[37]

S. KhotG. KindlerE. 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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[40]

E. MerkurjevT. 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. Google Scholar

[41]

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

[42]

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

[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. Google Scholar

[44]

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

[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. Google Scholar

[46]

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

[47]

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

[48]

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

[49]

J.-L. ShuY. 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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[52]

L. TrevisanG. B. SorkinM. Sudan and D. P. Williamson, Gadgets, approximation, and linear programming, SIAM Journal on Computing, 29 (2000), 2074-2097. doi: 10.1137/S0097539797328847. Google Scholar

[53]

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

[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. Google Scholar

[55]

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

[56]

Y. van GennipN. GuillenB. 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. Google Scholar

[57]

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

[58]

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

[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. Google Scholar

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.Google Scholar

[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.Google Scholar

[3]

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

[4]

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

[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. Google Scholar

[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. Google Scholar

[7]

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

[8]

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

[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.Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[13] A. Braides, Gamma-convergence for Beginners, Clarendon Press, 2002. doi: 10.1093/acprof:oso/9780198507840.001.0001. Google Scholar
[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. Google Scholar

[15]

S. BylkaA. 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. Google Scholar

[16]

L. CalatroniY. van GennipC.-B. SchönliebH. 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. Google Scholar

[17]

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

[18]

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

[19]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[24]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[32]

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

[33]

H. HuT. LaurentM. 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. Google Scholar

[34]

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

[35]

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

[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. Google Scholar

[37]

S. KhotG. KindlerE. 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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[40]

E. MerkurjevT. 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. Google Scholar

[41]

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

[42]

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

[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. Google Scholar

[44]

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

[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. Google Scholar

[46]

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

[47]

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

[48]

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

[49]

J.-L. ShuY. 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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[52]

L. TrevisanG. B. SorkinM. Sudan and D. P. Williamson, Gadgets, approximation, and linear programming, SIAM Journal on Computing, 29 (2000), 2074-2097. doi: 10.1137/S0097539797328847. Google Scholar

[53]

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

[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. Google Scholar

[55]

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

[56]

Y. van GennipN. GuillenB. 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. Google Scholar

[57]

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

[58]

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

[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. Google Scholar

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 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 3.  Visualisation of maximum cut approximations (best viewed in colour)
Figure 4.  Bar chart of Max-Cut approximations on 100 realisations of $ G(1000, 0.01) $
Figure 5.  Bar chart of Max-Cut approximations on 100 realisations of $ G(2500, 0.4) $
Figure 6.  Bar chart of Max-Cut approximations on 100 realisations of $ G(5000, 0.001) $
Figure 7.  Average degree distribution of 100 realisations of a random graph and the degree distribution of a scale free graph
Figure 8.  A Max-Cut approximation on a random 4-modular graph (best viewed in colour)
Figure 9.  Bar chart of Max-Cut approximations on 100 realisations of $ R(2500, 2, 0.009, 0.8) $
Figure 10.  Bar chart of Max-Cut approximations on 100 realisations of $ R(4000, 20, 0.01, 0.7) $
Figure 11.  Bar chart of Max-Cut approximations on 100 realisations of $ R(10000, 10, 0.01, 0.8) $
Figure 12.  Cut size as function of $ K $ for three graphs (best viewed in colour)
Figure 13.  Comparison of cut size approximation vs $ K $ on Amazon0302 graph
Figure 14.  Cut size as function of $ \tau $ for three graphs (best viewed in colour)
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 16.  Bar chart of Max-Cut approximations on 100 realisations of $ R(4000, 20, 0.01, 0.7) $
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
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
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
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
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
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
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
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----
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
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
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
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
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
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
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
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 & Continuous Dynamical Systems - A, 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 & Applied Analysis, 2008, 7 (6) : 1345-1359. doi: 10.3934/cpaa.2008.7.1345

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

Kolade M. Owolabi, Edson Pindza. Numerical simulation of multidimensional nonlinear fractional Ginzburg-Landau equations. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 835-851. doi: 10.3934/dcdss.2020048

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

Leonid Berlyand, Volodymyr Rybalko, Nung Kwan Yip. Renormalized Ginzburg-Landau energy and location of near boundary vortices. Networks & Heterogeneous Media, 2012, 7 (1) : 179-196. doi: 10.3934/nhm.2012.7.179

[19]

Leonid Berlyand, Petru Mironescu. Two-parameter homogenization for a Ginzburg-Landau problem in a perforated domain. Networks & Heterogeneous Media, 2008, 3 (3) : 461-487. doi: 10.3934/nhm.2008.3.461

[20]

Leonid Berlyand, Volodymyr Rybalko. Homogenized description of multiple Ginzburg-Landau vortices pinned by small holes. Networks & Heterogeneous Media, 2013, 8 (1) : 115-130. doi: 10.3934/nhm.2013.8.115

2018 Impact Factor: 1.008

Metrics

  • PDF downloads (12)
  • HTML views (172)
  • Cited by (0)

Other articles
by authors

[Back to Top]