Clustering in preferential attachment random graphs with edge-step

Caio Alves; Rodrigo Ribeiro; Rémy Sanchis

doi:10.1017/jpr.2021.20

Clustering in preferential attachment random graphs with edge-step

Caio Alves, Rodrigo Ribeiro, Rémy Sanchis

Discrete Algorithms

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

We prove concentration inequality results for geometric graph properties of an instance of the Cooper-Frieze [5] preferential attachment model with edge-steps. More precisely, we investigate a random graph model that at each time, with probability p adds a new vertex to the graph (a vertex-step occurs) or with probability an edge connecting two existent vertices is added (an edge-step occurs). We prove concentration results for the global clustering coefficient as well as the clique number. More formally, we prove that the global clustering, with high probability, decays as for a positive function of p, whereas the clique number of these graphs is, up to subpolynomially small factors, of order.

Original language	English
Pages (from-to)	890-908
Number of pages	19
Journal	Journal of Applied Probability
Volume	58
Issue number	4
DOIs	https://doi.org/10.1017/jpr.2021.20
State	Published - Dec 18 2021

Funding

We are grateful to Roberto Imbuzeiro Oliveira for the many inspiring conversations. C. A. was partially supported by FAPESP, grants 2013/24928-2 and 2015/18930-0, and by the DFG grant SA 3465/1-1. R. R. was partially supported by Conselho Nacional de Desenvolvimento Científicoe Tecnológico (CNPq) and by the project Stochastic Models of Disordered and Complex Systems. The Stochastic Models of Disordered and Complex Systems is a Millennium Nucleus (NC120062) supported by the Millenium Scientific Initiative of the Ministry of Science and Technology (Chile). R. S. has been partially supported by Conselho Nacional de Desenvolvimento Científicoe Tecnológico (CNPq) and by FAPEMIG (Programa Pesquisador Mineiro), grant PPM 00600/16.

Keywords

Complex networks
clique number
clustering coefficients
concentration bounds
transitivity

Access to Document

10.1017/jpr.2021.20

Cite this

@article{164eb4197bf14f58aa089c594b4fd7e1,

title = "Clustering in preferential attachment random graphs with edge-step",

abstract = "We prove concentration inequality results for geometric graph properties of an instance of the Cooper-Frieze [5] preferential attachment model with edge-steps. More precisely, we investigate a random graph model that at each time, with probability p adds a new vertex to the graph (a vertex-step occurs) or with probability an edge connecting two existent vertices is added (an edge-step occurs). We prove concentration results for the global clustering coefficient as well as the clique number. More formally, we prove that the global clustering, with high probability, decays as for a positive function of p, whereas the clique number of these graphs is, up to subpolynomially small factors, of order.",

keywords = "Complex networks, clique number, clustering coefficients, concentration bounds, transitivity",

author = "Caio Alves and Rodrigo Ribeiro and R{\'e}my Sanchis",

note = "Publisher Copyright: {\textcopyright} The Author(s), 2021. Published by Cambridge University Press on behalf of Applied Probability Trust.",

year = "2021",

month = dec,

day = "18",

doi = "10.1017/jpr.2021.20",

language = "English",

volume = "58",

pages = "890--908",

journal = "Journal of Applied Probability",

issn = "0021-9002",

publisher = "Cambridge University Press",

number = "4",

}

TY - JOUR

T1 - Clustering in preferential attachment random graphs with edge-step

AU - Alves, Caio

AU - Ribeiro, Rodrigo

AU - Sanchis, Rémy

N1 - Publisher Copyright: © The Author(s), 2021. Published by Cambridge University Press on behalf of Applied Probability Trust.

PY - 2021/12/18

Y1 - 2021/12/18

N2 - We prove concentration inequality results for geometric graph properties of an instance of the Cooper-Frieze [5] preferential attachment model with edge-steps. More precisely, we investigate a random graph model that at each time, with probability p adds a new vertex to the graph (a vertex-step occurs) or with probability an edge connecting two existent vertices is added (an edge-step occurs). We prove concentration results for the global clustering coefficient as well as the clique number. More formally, we prove that the global clustering, with high probability, decays as for a positive function of p, whereas the clique number of these graphs is, up to subpolynomially small factors, of order.

AB - We prove concentration inequality results for geometric graph properties of an instance of the Cooper-Frieze [5] preferential attachment model with edge-steps. More precisely, we investigate a random graph model that at each time, with probability p adds a new vertex to the graph (a vertex-step occurs) or with probability an edge connecting two existent vertices is added (an edge-step occurs). We prove concentration results for the global clustering coefficient as well as the clique number. More formally, we prove that the global clustering, with high probability, decays as for a positive function of p, whereas the clique number of these graphs is, up to subpolynomially small factors, of order.

KW - Complex networks

KW - clique number

KW - clustering coefficients

KW - concentration bounds

KW - transitivity

UR - https://www.scopus.com/pages/publications/85120621182

U2 - 10.1017/jpr.2021.20

DO - 10.1017/jpr.2021.20

M3 - Article

AN - SCOPUS:85120621182

SN - 0021-9002

VL - 58

SP - 890

EP - 908

JO - Journal of Applied Probability

JF - Journal of Applied Probability

IS - 4

ER -

Clustering in preferential attachment random graphs with edge-step

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this