[{Image src='imrich-wilfried-12.jpg' caption='' width='500' alt='Wilfried Imrich' class='image_left'}]''__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.