Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Partitions of networks that are robust to vertex permutation dynamics

100%

Froyland G., Kwok E.

Special Matrices

2015

tom 3

nr 1

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.

Ograniczanie wyników

1 Special Matrices

1 Froyland G.

1 Kwok E.

1 2015

Wyniki wyszukiwania

Partitions of networks that are robust to vertex permutation dynamics