|Hemanshu Kaul (UIUC Math)|
Small-world graphs - new random graph models
Abstract: We are interested in two basic parameters of a graph G: lG is the average distance between two vertices in the graph, and CG (the clustering coefficient) is the average density of the subgraphs induced by vertex neighborhoods. Naturally evolving massive networks like the social networks of acquaintances (used to model the spread of diseases, rumors, etc.), the internet, the power grid, airline traffic, etc., share common characteristics like short average distance and high clustering coefficient.
In the past, these networks have been modelled by the classical random graphs Gn,p, but Gn,p does not show any local clustering, making it a bad model for these networks. Recently, several random graph models have been proposed to incorporate the "small world effect" - average distance like that of the random graph, but much higher clustering coefficient. We will discuss some of these models and their properties.
In addition to the small world effect, some of the above mentioned networks, like the internet and telephone call graphs, have been observed to have the property that the number of vertices of degree k is proportional to k-c for some constant c > 0. Graphs having this property are called power law graphs. If time permits, we will also discuss some variations on Gn,p whose degree distribution follows the power law.