A survey of data mining of graphs using spectral graph theory

PDF

Authors
  1. Sawilla, R.
Corporate Authors
Defence R&D Canada - Ottawa, Ottawa ONT (CAN)
Abstract
Relational data may be represented by four classes of graphs: undirected graphs, directed graphs, hypergraphs, and directed hypergraphs. We present examples of data that is well suited to each type and describe how linear algebra has been used in the literature to cluster like objects, rank objects according to their importance to the system the graph represents, and predict relationships that likely exist in the system but have not yet been identified. In particular, we associate affinity and Laplacian matrices with a graph and apply spectral graph theory — the study of the eigenvalues, eigenvectors, and characteristic polynomial of graph matrices — to mine hidden patterns in the graphs. Shortcomings of existing techniques and open problems for future work are identified.

Il y a un résumé en français ici.

Report Number
DRDC-OTTAWA-TM-2008-317 — Technical Memorandum
Date of publication
01 Dec 2008
Number of Pages
48
DSTKIM No
CA032266
CANDIS No
531357
Format(s):
CD ROM

Permanent link

Document 1 of 1

Date modified: