Dynamics and evolution of biological and social networks

Graph spectra: A tool for analyzing structure and evolution of a network.

Author: Anirban Banerjee, Max Planck Institute for Molecular Genetics.

Names and affiliation of other authors:

Oral presentation

Abstract:
The existing graph invariants are not sufficient to capture all qualitative aspects of a graph. One of the aim of graph theory to identify on one hand the unique and special feature for the network from a particular class and on the other hand the universal qualities that are shared by other network structures. It is a challenge to specify the domain of a given a network structure, on the basis of certain unique qualitative features. We develop theoretical scheme and apply the general method, based on the spectral plot of the normalized graph Laplacian, that is easily visually analyzed and can be considered as excellent diagnostic to categorize the networks from different sources. We show how useful plausible hypothesis about evolutionary process can be made
by investigating the spectra of a graph constructed from actual data. Based on this idea we have reconstructed protein-protein interaction network which is structurally more close to real protein-protein interaction networks than the
networks constructed by other models. We also introduced a tentative classification scheme for empirical networks based on global qualitative properties detected through the spectrum of the Laplacian of the graph

Dynamics and evolution of biological and social networks. February 18-20th, 2008. Mallorca, Spain.