Wilfried Imrich
Product Graphs and Large Networks

Wilfried Imrich, Montan University, Leoben, Austria


This talk is concerned with the role of products of graphs in the investigation of networks. Networks arise in many different areas, such as biology, ecology, mathematical chemistry, software technology, and operations research. Nonetheless, the investigation of complex networks became a hot research topic only in the last decade, coinciding with increased interest in the Internet network, social networks, citation networks, and neural networks.

The networks are being studied by from many different points of view. Mostly they are representable by graphs with the following properties:
  • Sparsity – the number of edges is bounded by a constant c times the number of vertices.
  • The small world phenomenon – any two vertices are connected by a short path.
  • Power law degree distribution – the number of vertices of given degree is proportional to the degree
  • Fractal-like structure.
A central problem in the area is to generate networks quickly and efficiently that permit investigation using analytical tools, and that are as close as possible to real-world networks.

We will briefly outline the appealing approach in this direction by J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos, and Z. Ghahramani, who use the direct product of graphs (or, equivalently, the Kronecker product of matrices) for the generation of stochastic networks fulfilling these requirements. We then continue with another application of products of graphs that was proposed by B. Stadler, P. Stadler, G. Wagner and W. Fontana for the investigation of the relation between genotypes and phenotypes. It leads to the investigation of graphs that are product-like. We thus present an overview of graph products used for this purposes, and algorithms designed for the recognition of product like graphs which are not sparse. Finally, several ideas for the use of statistical methods in the recognition of sparse approximate products are presented.
Imprint Privacy policy « This page (revision-5) was last updated on Thursday, 6. October 2011, 10:27 by Kaiser Dana
  • operated by