Recent studies of complex systems have significantly increased the interest in modeling classes of graphs and networks. While random graphs have been studied for a long time, the standard (Gilbert; Erdos and Renyi) models appear to be inappropriate because they do not share the characteristics observed in real life systems. Several new models were proposed that better match the reality. Most of them are variations of the small-world model (Watts and Strogatz) or of the preferential attachment model (Barabási and Albert). We present some efficient algorithms for generating random graphs for these models.

Often we are interested in random graphs with some additional properties (connectivity, planarity, …). We present the probabilistic inductive classes of graphs that allow us to consider also these additional requirements. An probabilistic inductive class of graphs consists of a set of initial (basic) graphs and a set of generating/transformation rules. Starting with a random initial graph these rules are randomly applied to a current graph thus producing a sequence of graphs - the construction sequence of a graph from the class. Some examples of probabilistic inductive classes of graphs and some approaches for their analysis will be presented.

Keywords: Random graph; Random network; Probabilistic inductive class of graphs; Random generator

Biography: Vladimir Batagelj is Full Professor of Discrete and Computational Mathematics at the University of Ljubljana, Slovenia. He is also a member of the Institute of Mathematics, Physics and Mechanics. His main research interests are in graph theory, algorithms on graphs and networks, combinatorial optimization, data analysis, and applications of information technology in education. He is coauthor (with Andrej Mrvar) of Pajek - a program for analysis and visualization of large networks. He coauthored two books 'Generalized blockmodeling' (with Doreian and Ferligoj) and 'Exploratory Network Analysis with Pajek' (with de Nooy and Mrvar) that were published in 2005 by the Cambridge University Press. In 2007 the book 'Generalized blockmodeling' received the Harrison White Outstanding Book Award from Mathematical Sociology Section of American Sociological Association. In 2007 he (with A. Ferligoj) also received the Simmel Award from INSNA. He is a member of IEEE, IFCS, CSNA, INSNA, IASC, and ISI.