Spectral Pyramid

Problemstellung:

Jeder Graph kann mit einer Adjazenzmatrix dargestellt werden, auf der man die Principal Component Analysis (PCA) durchfuehren kann, um den Graphen auf der strukturellen Ebene zu analysieren d.h. das Spektrum des Graphen zu studieren. Der Dual Graph Contraction Algorithm wird angewandt um eine Graphenpyramide zu bilden, die ein Stack von aufeinanderfolgenden reduzierten Graphen ist (siehe das Foto).
Die Frage die hier gestellt werden kann ist "Wie aendern sich die Spektra der Graphpyramide waehrend Graphkontraktion?".

Vertex id.	1	2	3	4	5	6	7	8	9	10	11	12
1	2	-1	0	0	-1	0	0	0	0	0	0	0
2	-1	3	-1	0	0	-1	0	0	0	0	0	0
3	0	-1	3	-1	0	0	1	0	0	0	0	0
4	0	0	-1	2	0	0	0	-1	0	0	0	0
5	-1	0	0	0	3	-1	0	0	-1	0	0	0
6	0	-1	0	0	-1	4	-1	0	0	-1	0	0
7	0	0	-1	0	0	-1	4	-1	0	0	-1	0
8	0	0	0	-1	0	0	-1	3	0	0	0	-1
9	0	0	0	0	-1	0	0	0	2	-1	0	0
10	0	0	0	0	0	-1	0	0	-1	3	-1	0
11	0	0	0	0	0	0	-1	0	0	-1	3	-1
12	0	0	0	0	0	0	0	-1	0	0	-1	2

Wo die Elemente der Laplacematrix:
L(v,w)= { degree_of_vertex(v) if v=w; -1 if u und v benahbart; 0 anders}
Diese Matrix kann fuer die Eigenvaluedecomposition verwendet werden.

Ziel des Praktikums:

Die Spektren der Graphpyramiden mittels Eingenvaluedecomposition zu analysieren. Um Moeglichkeiten fuer Performancegewinnen zu erschliessen.

Gliederung des Praktikums

• Spektren der Graphen zu berechnen.
• Experimente zur Bewertung der Eigenverte auf verschidene Graphen in der Pyramide.
• Implementirung eines Analysetools fuer Graphenspektren als Erweiterung der bereits bestehenden C++ Library.

Fuer dieses Praktikum besteht auch die Moeglichkeit eine Diplomarbeit anzuschliessen.

Literatur

• Spectral Graph Theory. Fan R. K. Chung. First chapter.
• W.G. Kropatsch. Building Irregular Pyramids by Dual Graph Contraction. IEE-Proc. Vision, Image and Signal Processing, Vol. 142,366-374, 1995.
  Also as PRIP technical report Nr.35.

Betreuer: Yll Haxhimusa

Praktikum