Partitions of networks that are robust to vertex permutation dynamics

• Autorzy: Gary Froyland , Eric Kwok
• Języki publikacji: EN

Abstrakty

EN

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.

• Wydawca: De Gruyter Open
• Czasopismo: Special Matrices
• Rocznik: 2015
• Tom: 3
• Numer: 1

Daty

otrzymano

2014-09-23

zaakceptowano

2015-02-13

online

2015-02-25

Twórcy

autor

Gary Froyland

• School of Mathematics and Statistics, The University of New South Wales, Sydney NSW 2052, Australia

autor

Eric Kwok

• School of Mathematics and Statistics, The University of New South Wales, Sydney NSW 2052, Australia

Bibliografia

• [1] N. Alon. Eigenvalues and expanders. Combinatorica, 6:83–96, 1986. [Crossref]
• [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]
• [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.
• [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]
• [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]
• [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]
• [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]
• [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]
• [14] M. Fiedler. A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czechoslovak Mathematical Journal, 25:619–633, 1975.
• [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]
• [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.
• [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]
• [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]
• [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]
• [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.
• [28] B. Mohar. Isoperimetric number of graphs. Journal of Combinatorial Theory, 47:274–291, 1989.
• [29] M. Reed and B. Simon. Methods of Modern Mathematical Physics: Analysis of Operators, volume 4. Academic Press, 1978.
• [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]

Identyfikatory

DOI

10.1515/spma-2015-0003