Probabilistic Inductive Classes of Graphs

Author: Kejzar Natasa   Nikoloski Zoran   Batagelj Vladimir  

Publisher: Routledge Ltd

ISSN: 0022-250X

Source: Journal of Mathematical Sociology, Vol.32, Iss.2, 2008-04, pp. : 85-109

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

A unifying framework - probabilistic inductive classes of graphs (PICGs) - is defined by imposing a probability space on the rules and their left elements from the standard notion of inductive class of graphs. The rules can model the processes creating real-world social networks, such as spread of knowledge, dynamics of acquaintanceships or sexual contacts, and emergence of clusters. We demonstrate the characteristics of PICGs by casting some well-known models of growing networks in this framework. Results regarding expected size and order are derived. For PICG models of connected and 2-connected graphs order, size and asymptotic degree distribution are presented. The approaches used represent analytic alternative to computer simulation, which is mostly used to obtain the properties of evolving graphs.