Berlin 2008 – scientific programme

Parts | Days | Selection | Search | Downloads | Help

DY: Fachverband Dynamik und Statistische Physik

DY 3: Statistical physics of complex networks I

DY 3.7: Talk

Monday, February 25, 2008, 12:00–12:15, A 053

A Monte Carlo method for generation of random graphs — •Bartlomiej Waclaw¹, Leszek Bogacz², Zdzislaw Burda², and Wolfhard Janke¹ — ¹Institut für Theoretische Physik, Universität Leipzig, Vor dem Hospitaltore 1, 04103 Leipzig, Germany — ²Faculty of Physics, Astronomy and Applied Informatics, Jagellonian University, Reymonta 4, 30-059 Krakow, Poland

Random graphs are widely used for modeling the Internet, transportation, biological or social networks. Many models, based on some simple rules for growth and rewiring of links, have been proposed to explain their specific structural features as for instance power-law degree distribution and small diameter. However, to study dynamical phenomena taking place on networks with a given structure, it is desirable to have a general algorithm which produces a variety of random graphs. The method presented here is based on a random walk in the space of graphs. By ascribing to each graph a certain statistical weight we can set up a sort of Markovian process that generates networks with the desired probability. One can change their typical properties by tuning the weight function and thus to generate networks of different types. The method works for both growing and maximal-entropy graphs, that is graphs which are maximally random for a given constraint. Various properties, like power-law degree distribution, degree-degree correlations or higher clustering can be easily obtained. The method is very flexible and allows for further improvement, e.g. multicanonical simulations.