Tata Institute of Fundamental Research

Laplacian Spectrum of Graphs, Structural Distance and Evolutionary Relationship of Networks

Seminar
Speaker: Anirban Banerjee Max Planck Institute of Molecular Genetics Ihnestrasse 63-73 D-14195 Berlin Germany http
Date: Friday, 26 Feb 2010 (all day)
Venue: A-212 (STCS Seminar Room)

(Scan to add to calendar)
Abstract:  Existing graph measures can retrieve certain structural information, but are not sufficient to capture all aspects of a network. We develop a tool, spectra of normalized graph Laplacian, that helps to understand the network structure with deep perception. Evolution of a network with different graph operations produces specific eigenvalues. Thus, useful hypotheses about evolutionary processes can be made by investigating the spectra of real networks. We also demonstrate that real networks of different classes pose characteristic eigenvalue distributions. Applying a meaningful distance measure, we show that network structures are more similar within the same class than between classes. We analyze 43 metabolic networks from different species and find a separation of the three domains, Bacteria, Archaea and Eukarya.