Generating realistic labelled, weighted random graphs

DOI10.3390/A8041143MaRDI QIDQ1736741zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Xianqiang Yang

Publication date 26 March 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a8041143

zbMATH Keywords

Bayesian estimationbeta distributiongenerative algorithmslabelled graphsmaximum likelihood estimationmixture modelingnetwork modelsrandom graphsvariational inferenceweighted graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Bayesian inference (62F15)

Review text

Summary: Generative algorithms for random graphs have yielded insights into the structure and evolution of real-world networks. Most networks exhibit a well-known set of properties, such as heavy-tailed degree distributions, clustering and community formation. Usually, random graph models consider only structural information, but many real-world networks also have labelled vertices and weighted edges. In this paper, we present a generative model for random graphs with discrete vertex labels and numeric edge weights. The weights are represented as a set of Beta Mixture Models (BMMs) with an arbitrary number of mixtures, which are learned from real-world networks. We propose a Bayesian Variational Inference (VI) approach, which yields an accurate estimation while keeping computation times tractable. We compare our approach to state-of-the-art random labelled graph generators and an earlier approach based on Gaussian Mixture Models (GMMs). Our results allow us to draw conclusions about the contribution of vertex labels and edge weights to graph structure.

Recommendations

• Generating graphs by creating associative and random links between existing nodes
• Random graph generation using multiple switches of edges
• Generating Random Unlabelled Graphs
• Towards a Systematic Evaluation of Generative Network Models
• A program generating homogeneous random graphs with given weights

Cites work

• Bayesian estimation of Dirichlet mixture model with variational inference
• Conjugate priors for exponential families
• Efficient Algorithms for Shortest Paths in Sparse Networks
• Emergence of Scaling in Random Networks
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 1059776 (Why is no real title available?)
• Kronecker graphs: an approach to modeling networks
• Latent Space Approaches to Social Network Analysis
• Networks. An introduction.
• OddBall
• On the usefulness of weight-based constraints in frequent subgraph mining
• Pattern recognition and machine learning.
• PRMLT
• Stochastic Blockmodels for Directed Graphs
• Variational inference for Dirichlet process mixtures

Cited in

(2)

• Generating graphs by creating associative and random links between existing nodes
• Interplay between topology and edge weights in real-world graphs: concepts, patterns, and an algorithm

Describes a project that uses

Uses Software

• OddBall
• PRMLT
• KronFit

This page was built for publication: Generating realistic labelled, weighted random graphs

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