Probabilistic Inductive Classes of Graphs

DOI10.1080/00222500801931586zbMATH Open1135.91424arXivmath/0612778OpenAlexW3102305050WikidataQ59723860 ScholiaQ59723860MaRDI QIDQ3499446FDOQ3499446

Authors: Nataša Kejžar, Z. Nikoloski, Vladimir Batagelj 

Publication date: 29 May 2008

Published in: The Journal of Mathematical Sociology (Search for Journal in Brave)

Abstract: Models of complex networks are generally defined as graph stochastic processes in which edges and vertices are added or deleted over time to simulate the evolution of networks. Here, we define a unifying framework - probabilistic inductive classes of graphs - for formalizing and studying evolution of complex networks. Our definition of probabilistic inductive class of graphs (PICG) extends the standard notion of inductive class of graphs (ICG) by imposing a probability space. A PICG is given by: (1) class B of initial graphs, the basis of PICG, (2) class R of generating rules, each with distinguished left element to which the rule is applied to obtain the right element, (3) probability distribution specifying how the initial graph is chosen from class B, (4) probability distribution specifying how the rules from class R are applied, and, finally, (5) probability distribution specifying how the left elements for every rule in class R are chosen. We point out that many of the existing models of growing networks can be cast as PICGs. We present how the well known model of growing networks - the preferential attachment model - can be studied as PICG. As an illustration we present results regarding the size, order, and degree sequence for PICG models of connected and 2-connected graphs.

Full work available at URL: https://arxiv.org/abs/math/0612778

Recommendations

• scientific article; zbMATH DE number 512934
• scientific article; zbMATH DE number 3918277
• Growing Protean Graphs
• Random graph models of social networks
• scientific article; zbMATH DE number 1792101

zbMATH Keywords

network modelsprobabilistic methodgrowing networksinductive classes of graphs

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30)

Cites Work

• The degree sequence of a scale-free random graph process
• Title not available (Why is that?)
• Random Deletion in a Scale-Free Random Graph Process
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (5)

• Labelled graph strategic rewriting for social networks
• Labelled graph rewriting meets social networks
• Title not available (Why is that?)
• Probabilistic construction of proportional graphs
• Strategic port graph rewriting: an interactive modelling framework

Uses Software

• NetLogo

This page was built for publication: Probabilistic Inductive Classes of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3499446)