ICCS2004 Application Submission/Review

Abstract for
"Random graphs with clustering and arbitrary degree distribution"

Random graphs may be suitable models of real networks, such as social networks, the Internet, and epidemiological networks of susceptible and infectious individuals. Random graphs may be used as null hypotheses to test conjectures about network structure, and sometimes it is essential to use random graphs as a model of a real network when it is impossible to sample an entire network. Recent work has shown that real networks have statistical properties which differ from pure-random graphs, most prominently in their degree distribution and their clustering coefficient (a measure of triadic closure). Random graph models have been devised to mimic both specified degree distributions (Barabasi model) and clustering levels (Watts-Strogatz model), but so far no algorithm has been devised to generate random graphs with both specified degree distributions and clustering levels. We here propose such an algorithm, and use it to illustrate the vulnerability of networks to diffusion processes.