Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: grid graph

Sortuj według:

Ogranicz wyniki do:

Weighted Laplacians of Grids and Their Application for Inspection of Spectral Graph Clustering Methods

Kłopotek Mieczysław, Wierzchoń Sławomir, Kłopotek Robert

TASK Quarterly : scientific bulletin of Academic Computer Centre in Gdansk

2021

Vol. 25, No 3

329--353

This paper investigates the relationship between various types of spectral clustering methods and their kinship to relaxed versions of graph cut methods. This predominantly analytical study exploits the closed (or nearly closed) form of eigenvalues and eigenvectors of unnormalized (combinatorial), normalized, and random walk Laplacians of multidimensional weighted and unweighted grids. We demonstrate that spectral methods can be compared to (normalized) graph cut clustering only if the cut is performed to minimize the sum of the weight square roots (and not the sum of weights) of the removed edges. We demonstrate also that the spectrogram of the regular grid graph can be derived from the composition of spectrograms of path graphs into which such a graph can be decomposed, only for combinatorial Laplacians. It is impossible to do so both for normalized and random-walk Laplacians. We investigate the in-the-limit behavior of combinatorial and normalized Laplacians demonstrating that the eigenvalues of both Laplacians converge to one another with an increase in the number of nodes while their eigenvectors do not. Lastly, we show that the distribution of eigenvalues is not uniform in the limit, violating a fundamental assumption of the compact spectral clustering method.

Interfacing graphs

Kämpke T.

Machine Graphics and Vision

2000

Vol. 9, No. 4

797-824

Transformations of vertex sequences of regular grid graph into paths of an arbitrary connected graph are facilitated according to various coarsening and approximation operations, including minimum cost alterations and minimum cost re-routings. The sequence transformations are supposed to support issues of man-machine interaction, which implies lack of an ultimate formal design objective. Furthermore, this implies that formal methods and algorithms have to be combined in a pragmatic fashion. For planar graph, the notion of Voronoi regions is modified to graph Voronoi regions which partition the plane according to proximity to verttices and edges simultaneously. The non-planar case is reduced to the planar case by adding all intersection points of vertex connections to the original vertex set and by splitting vertex connections accordingly. This allows grid point sequences to be intermediately transformed to so-called mixed or region sequences which are eventualy transformed to vertex sequences by production rule-like operations. The algorithmic preprocessing burden of partitioning and indexing the euclidean plane via the graph Voronoi regions or approximations thereof is practically larger and typically more complicated than any of the run time computations.