Partitions of networks that are robust to vertex permutation dynamics

Gary Froyland; Eric Kwok

Special Matrices (2015)

  • Volume: 3, Issue: 1, page 22-42, electronic only
  • ISSN: 2300-7451

Abstract

top
Minimum disconnecting cuts of connected graphs provide fundamental information about the connectivity structure of the graph. Spectral methods are well-known as stable and efficient means of finding good solutions to the balanced minimum cut problem. In this paper we generalise the standard balanced bisection problem for static graphs to a new “dynamic balanced bisection problem”, in which the bisecting cut should be minimal when the vertex-labelled graph is subjected to a general sequence of vertex permutations. We extend the standard spectral method for partitioning static graphs, based on eigenvectors of the Laplacian matrix of the graph, by constructing a new dynamic Laplacian matrix, with eigenvectors that generate good solutions to the dynamic minimum cut problem. We formulate and prove a dynamic Cheeger inequality for graphs, and demonstrate the effectiveness of the dynamic Laplacian matrix for both structured and unstructured graphs.

How to cite

top

Gary Froyland, and Eric Kwok. "Partitions of networks that are robust to vertex permutation dynamics." Special Matrices 3.1 (2015): 22-42, electronic only. <http://eudml.org/doc/270000>.

@article{GaryFroyland2015,
abstract = {Minimum disconnecting cuts of connected graphs provide fundamental information about the connectivity structure of the graph. Spectral methods are well-known as stable and efficient means of finding good solutions to the balanced minimum cut problem. In this paper we generalise the standard balanced bisection problem for static graphs to a new “dynamic balanced bisection problem”, in which the bisecting cut should be minimal when the vertex-labelled graph is subjected to a general sequence of vertex permutations. We extend the standard spectral method for partitioning static graphs, based on eigenvectors of the Laplacian matrix of the graph, by constructing a new dynamic Laplacian matrix, with eigenvectors that generate good solutions to the dynamic minimum cut problem. We formulate and prove a dynamic Cheeger inequality for graphs, and demonstrate the effectiveness of the dynamic Laplacian matrix for both structured and unstructured graphs.},
author = {Gary Froyland, Eric Kwok},
journal = {Special Matrices},
keywords = {graph bisection; spectral method; Laplacian matrix; permutation dynamics},
language = {eng},
number = {1},
pages = {22-42, electronic only},
title = {Partitions of networks that are robust to vertex permutation dynamics},
url = {http://eudml.org/doc/270000},
volume = {3},
year = {2015},
}

TY - JOUR
AU - Gary Froyland
AU - Eric Kwok
TI - Partitions of networks that are robust to vertex permutation dynamics
JO - Special Matrices
PY - 2015
VL - 3
IS - 1
SP - 22
EP - 42, electronic only
AB - Minimum disconnecting cuts of connected graphs provide fundamental information about the connectivity structure of the graph. Spectral methods are well-known as stable and efficient means of finding good solutions to the balanced minimum cut problem. In this paper we generalise the standard balanced bisection problem for static graphs to a new “dynamic balanced bisection problem”, in which the bisecting cut should be minimal when the vertex-labelled graph is subjected to a general sequence of vertex permutations. We extend the standard spectral method for partitioning static graphs, based on eigenvectors of the Laplacian matrix of the graph, by constructing a new dynamic Laplacian matrix, with eigenvectors that generate good solutions to the dynamic minimum cut problem. We formulate and prove a dynamic Cheeger inequality for graphs, and demonstrate the effectiveness of the dynamic Laplacian matrix for both structured and unstructured graphs.
LA - eng
KW - graph bisection; spectral method; Laplacian matrix; permutation dynamics
UR - http://eudml.org/doc/270000
ER -

References

top
  1. [1] N. Alon. Eigenvalues and expanders. Combinatorica, 6:83–96, 1986. [Crossref] Zbl0661.05053
  2. [2] C. J. Alpert, A. B. Kahng, and S.-Z. Yao. Spectral partitioning with multiple eigenvectors. Discrete Applied Mathematics, 90(1):3–26, 1999. [Crossref] Zbl0918.68076
  3. [3] W. N. Anderson Jr and T. D. Morley. Eigenvalues of the Laplacian of a graph. Linear and Multilinear Algebra, 18(2):141–145, 1985. Zbl0594.05046
  4. [4] A. S. Bandeibra, A. Singer, and D. A. Spielman. A Cheeger inequality for graph connection Laplacian. SIAM Journal onMatrix Analysis and Applications, 34(4):1611–1630, 2013. [Crossref][WoS] Zbl1287.05081
  5. [5] A. Buluç, H. Meyerhenke, I. Safro, P. Sanders, and C. Schulz. Recent advances in graph partitioning. 2013. 
  6. [6] P. K. Chan, M. D. Schlag, and J. Y. Zien. Spectral k-way ratio-cut partitioning and clustering. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 13(9):1088–1096, 1994. 
  7. [7] F. Chung. Spectral Graph Theory, volume 92. American Mathematical Society, CBMS Regional Conference Series in Mathematics edition, 1996. 
  8. [8] R. R. Coifman and M. J. Hirn. Diffusionmaps for changing data. Applied and Computational Harmonic Analysis, 36(1):79–107, 2014. [Crossref] Zbl1302.62122
  9. [9] G. Demirel, F. Vazquez, G.A. Böhme, and T. Gross. Moment-closure approximations for discrete adaptive networks. Physica D, 267, 68–80, 2014. [WoS] Zbl1285.93013
  10. [10] D. Delling, A. V. Goldberg, T. Pajor, and R. F. Werneck. Customizable route planning. In Experimental Algorithms, volume 6630, pages 376–387. Springer, 2011. 
  11. [11] W. E. Donath and A. J. Hoffman. Lower bounds for the partitioning of graphs. IBM Journal of Research and Development, 17(5):420–425, 1973. [Crossref] Zbl0259.05112
  12. [12] D. Ediger, J. Riedy, D. A. Bader, and H. Meyerhenke. Tracking structure of streaming social networks. In Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), 2011 IEEE International Symposium on, pages 1691–1699. IEEE, 2011. 
  13. [13] M. Fiedler. Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23(2):298–305, 1973. [WoS] Zbl0265.05119
  14. [14] M. Fiedler. A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czechoslovak Mathematical Journal, 25:619–633, 1975. Zbl0437.15004
  15. [15] P.-O. Fjällström. Algorithms for graph partitioning: A survey. Linköping electronic articles in Computer and Information Science, 3(10), 1998. 
  16. [16] J. H. Fowler and N. A. Christakis. Dynamic spread of happiness in a large social network: Longitudinal analysis over 20 years in the framingham heart study. British Medical Journal, 337:1–9, 2008. [WoS] 
  17. [17] G. Froyland and M. Dellnitz. Detecting and locating near-optimal almost-invariant sets and cycles. SIAM Journal on Scientific Computing, 24(6):1839–1863, 2003. [Crossref] Zbl1042.37063
  18. [18] G. Froyland, N. Santitissadeekorn, and A. Monahan. Transport in time-dependent dynamical systems: Finite-time coherent sets. Chaos: An Interdisciplinary Journal of Nonlinear Science, 20(4):043116, 2010. Zbl1311.37008
  19. [19] M. R. Garey and D. S. Johnson. Computers and Intractability:A Guide to Theory of NP-completeness. W.H Freeman and Co, 1970. 
  20. [20] L. Grady and E. Schwartz. Isopermetric graph partitioning for image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(3):469–475, 2006. 
  21. [21] K. M. Hall. An r-dimensional quadratic placement algorithm. Management Science, 17(3):219–229, 1970. [Crossref] Zbl0203.52503
  22. [22] P. Holme and J. Saramäki. Temporal networks. Physics reports, 519(3): 97–125, 2012. 
  23. [23] R.A. Horn and C.A. Johnson. Matrix Analysis. Cambridge, 1990. 
  24. [24] B. Hendrickson and T. G. Kolda. Graph partitioning models for parallel computing. Parallel Computing, 26:1519–1534, 2000. [Crossref] Zbl0948.68130
  25. [25] V. Kwatra, A. Schödl, I. Essa, G. Turk, and A. Bobick. Graphcut textures: Image and video synthesis using graph cuts. In ACM Transactions on Graphics (ToG), volume 22, pages 277–286, 2003. [Crossref] 
  26. [26] K. Li, M. Small, and X. Fu. Generation of clusters in complex dynamical networks via pinning control. Journal of Physics A: Mathematical and Theoretical, 41(50):505101, 2008. [WoS] Zbl1152.93002
  27. [27] P.J. Mucha, T. Richardson, K. Macon, M.A. Porter, and J.P. Onnela. Community structure in time-dependent, multiscale, and multiplex networks. Science, 328(5980):876–878, 2010. Zbl1226.91056
  28. [28] B. Mohar. Isoperimetric number of graphs. Journal of Combinatorial Theory, 47:274–291, 1989. Zbl0719.05042
  29. [29] M. Reed and B. Simon. Methods of Modern Mathematical Physics: Analysis of Operators, volume 4. Academic Press, 1978. Zbl0401.47001
  30. [30] J. Scott. Social Network Analysis: A Handbook. SAGE, 2000. 
  31. [31] J. Shi and J.Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis andMachine Intelligence, 22(8):888–905, 2000. 
  32. [32] M. Small and C. K. Tse. Small world and scale free model of transmission of SARS. International Journal of Bifurcation and Chaos, 15(05):1745–1755, 2005. [Crossref] 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.