# Partitions of networks that are robust to vertex permutation dynamics

Special Matrices (2015)

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

## Access Full Article

top## Abstract

top## How to cite

topGary 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] N. Alon. Eigenvalues and expanders. Combinatorica, 6:83–96, 1986. [Crossref] Zbl0661.05053
- [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] 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] 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] A. Buluç, H. Meyerhenke, I. Safro, P. Sanders, and C. Schulz. Recent advances in graph partitioning. 2013.
- [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] F. Chung. Spectral Graph Theory, volume 92. American Mathematical Society, CBMS Regional Conference Series in Mathematics edition, 1996.
- [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] 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] 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] 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] 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] M. Fiedler. Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23(2):298–305, 1973. [WoS] Zbl0265.05119
- [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] P.-O. Fjällström. Algorithms for graph partitioning: A survey. Linköping electronic articles in Computer and Information Science, 3(10), 1998.
- [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] 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] 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] M. R. Garey and D. S. Johnson. Computers and Intractability:A Guide to Theory of NP-completeness. W.H Freeman and Co, 1970.
- [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] K. M. Hall. An r-dimensional quadratic placement algorithm. Management Science, 17(3):219–229, 1970. [Crossref] Zbl0203.52503
- [22] P. Holme and J. Saramäki. Temporal networks. Physics reports, 519(3): 97–125, 2012.
- [23] R.A. Horn and C.A. Johnson. Matrix Analysis. Cambridge, 1990.
- [24] B. Hendrickson and T. G. Kolda. Graph partitioning models for parallel computing. Parallel Computing, 26:1519–1534, 2000. [Crossref] Zbl0948.68130
- [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] 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] 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] B. Mohar. Isoperimetric number of graphs. Journal of Combinatorial Theory, 47:274–291, 1989. Zbl0719.05042
- [29] M. Reed and B. Simon. Methods of Modern Mathematical Physics: Analysis of Operators, volume 4. Academic Press, 1978. Zbl0401.47001
- [30] J. Scott. Social Network Analysis: A Handbook. SAGE, 2000.
- [31] J. Shi and J.Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis andMachine Intelligence, 22(8):888–905, 2000.
- [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 ?

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