Partitions of networks that are robust to vertex permutation dynamics

Gary Froyland ; Eric Kwok

Special Matrices, Tome 3 (2015), / Harvested from The Polish Digital Mathematics Library

Résumé

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.

Détail

Publié le : 2015-01-01

Zbl 1311.05096

EUDML-ID : urn:eudml:doc:270000

Bibliographie

[1] N. Alon. Eigenvalues and expanders. Combinatorica, 6:83–96, 1986. [Crossref] | Zbl 0661.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] | Zbl 0918.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. | Zbl 0594.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] | Zbl 1287.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] | Zbl 1302.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] | Zbl 1285.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] | Zbl 0259.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] | Zbl 0265.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. | Zbl 0437.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] | Zbl 1042.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. | Zbl 1311.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] | Zbl 0203.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] | Zbl 0948.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] | Zbl 1152.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. | Zbl 1226.91056

[28] B. Mohar. Isoperimetric number of graphs. Journal of Combinatorial Theory, 47:274–291, 1989. | Zbl 0719.05042

[29] M. Reed and B. Simon. Methods of Modern Mathematical Physics: Analysis of Operators, volume 4. Academic Press, 1978. | Zbl 0401.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]