Spectral Characterization of Network Structures an

Authors: Anirban Banerjee Jürgen Jost

Publish Date: 2009

Volume: , Issue: , Pages: 117-132

PDF Link

Abstract

Mathematically graphs defy a systematic and complete classification and empirically the graphs representing networks come in a bewildering multitude We have developed some tools 8 9 710 that at least allow for a rough classification of graphs that reflects the difference in the empirical domains from which network data are produced and that does not depend on sophisticated visualization toolsAs such a graph is a rather simple formal structure It consists of nodes or vertices that are connected by edges or links These nodes then represent the elements of a network and we shall often not distinguish between the network and its underlying graph and the edges represent relations between them These could be chemical interactions as in intracellular networks of genes proteins or metabolites synaptic connections between neurons physical links in infrastructural networks links between Internet pages cooccurrences between words in sentences or on text pages email contacts between people coauthorships between scientists and so on This structure then can be expected to be somehow adapted to the function of the network by evolution selforganization or design In turn any dynamics supported by the network will be constrained by this underlying structureOur approach is based on associating certain mathematical objects—which ultimately just yield some numbers—to a graph which reflect its structural properties and which in particular encode the constraints on the dynamics that it can support The mathematical objects will be an operator the graph Laplacian a discrete analogue of the Laplace operator in real analysis and its eigenfunctions and the numbers alluded to will be the eigenvalues of that operator

Keywords: