Assortativity and bidegree distributions on Bernoulli random graph superpositions

Mindaugas Bloznelis, Joona Karjalainen, Lasse Leskelä*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

1 Citation (Scopus)

Abstract

A probabilistic generative network model with n nodes and m overlapping layers is obtained as a superposition of m mutually independent Bernoulli random graphs of varying size and strength. When n and m are large and of the same order of magnitude, the model admits a sparse limiting regime with a tunable power-law degree distribution and nonvanishing clustering coefficient. This article presents an asymptotic formula for the joint degree distribution of adjacent nodes. This yields a simple analytical formula for the model assortativity, and opens up ways to analyze rank correlation coefficients suitable for random graphs with heavy-tailed degree distributions.
Original languageEnglish
Title of host publicationAlgorithms and Models for the Web Graph - 17th International Workshop, WAW 2020, Proceedings
Subtitle of host publication17th International Workshop, WAW 2020, Warsaw, Poland, September 21–22, 2020, Proceedings
EditorsBogumil Kaminski, Przemyslaw Szufel, Pawel Pralat
Pages68-81
Number of pages14
ISBN (Electronic)978-3-030-48478-1
DOIs
Publication statusPublished - 2 Jun 2020
MoE publication typeA4 Article in a conference publication
EventWorkshop on Algorithms and Models for the Web Graph - SGH Warsaw School of Economics, Warsaw, Poland
Duration: 21 Sep 202022 Sep 2020
Conference number: 17
https://math.ryerson.ca/waw2020/

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer
Volume12091
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

WorkshopWorkshop on Algorithms and Models for the Web Graph
Abbreviated titleWAW
Country/TerritoryPoland
CityWarsaw
Period21/09/202022/09/2020
Internet address

Keywords

  • Joint degree distribution
  • Bidegree distribution
  • Degree–degree distribution
  • Empirical degree distribution
  • Degree correlation
  • Transitivity
  • Statistical network model
  • Erdős–Rényi graph
  • Random intersection graph

Fingerprint

Dive into the research topics of 'Assortativity and bidegree distributions on Bernoulli random graph superpositions'. Together they form a unique fingerprint.

Cite this