Spread of Infection over P.A. random graphs with edge insertion

Caio Alves; Rodrigo Ribeiro

doi:10.30757/ALEA.v19-50

Spread of Infection over P.A. random graphs with edge insertion

Caio Alves, Rodrigo Ribeiro

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

1 Scopus citations

Abstract

In this work we investigate a bootstrap percolation process on random graphs generated by a random graph model which combines preferential attachment and edge insertion between previously existing vertices. The probabilities of adding either a new vertex or a new connection between previously added vertices are time dependent and given by a function f called the edge-step function. We show that under integrability conditions over the edge-step function the graphs are highly susceptible to the spread of infections, which requires only 3 steps to infect a positive fraction of the whole graph.

Original language	English
Pages (from-to)	1221-1239
Number of pages	19
Journal	Alea (Rio de Janeiro)
Volume	19
Issue number	2
DOIs	https://doi.org/10.30757/ALEA.v19-50
State	Published - 2022
Externally published	Yes

Funding

Received by the editors April 21st, 2021; accepted August 4th, 2022. 2010 Mathematics Subject Classification. Primary 05C82; Secondary 60K40, 68R10. Key words and phrases. preferential attachment, random graphs, Bootstrap percolation, Karamata’s theory, regular varying function. C.A. was supported by the Noise-Sensitivity everywhere ERC Consolidator Grant 772466.

Funders	Funder number
Noise-Sensitivity everywhere ERC
Horizon 2020 Framework Programme	772466

Keywords

Bootstrap percolation
Karamata’s theory
Preferential attachment
Random graphs
Regular varying function

Access to Document

10.30757/ALEA.v19-50

Cite this

@article{78c79007f3ca4f3c8af365b47341801f,

title = "Spread of Infection over P.A. random graphs with edge insertion",

abstract = "In this work we investigate a bootstrap percolation process on random graphs generated by a random graph model which combines preferential attachment and edge insertion between previously existing vertices. The probabilities of adding either a new vertex or a new connection between previously added vertices are time dependent and given by a function f called the edge-step function. We show that under integrability conditions over the edge-step function the graphs are highly susceptible to the spread of infections, which requires only 3 steps to infect a positive fraction of the whole graph.",

keywords = "Bootstrap percolation, Karamata{\textquoteright}s theory, Preferential attachment, Random graphs, Regular varying function",

author = "Caio Alves and Rodrigo Ribeiro",

year = "2022",

doi = "10.30757/ALEA.v19-50",

language = "English",

volume = "19",

pages = "1221--1239",

journal = "Alea (Rio de Janeiro)",

issn = "1980-0436",

number = "2",

}

TY - JOUR

T1 - Spread of Infection over P.A. random graphs with edge insertion

AU - Alves, Caio

AU - Ribeiro, Rodrigo

PY - 2022

Y1 - 2022

N2 - In this work we investigate a bootstrap percolation process on random graphs generated by a random graph model which combines preferential attachment and edge insertion between previously existing vertices. The probabilities of adding either a new vertex or a new connection between previously added vertices are time dependent and given by a function f called the edge-step function. We show that under integrability conditions over the edge-step function the graphs are highly susceptible to the spread of infections, which requires only 3 steps to infect a positive fraction of the whole graph.

AB - In this work we investigate a bootstrap percolation process on random graphs generated by a random graph model which combines preferential attachment and edge insertion between previously existing vertices. The probabilities of adding either a new vertex or a new connection between previously added vertices are time dependent and given by a function f called the edge-step function. We show that under integrability conditions over the edge-step function the graphs are highly susceptible to the spread of infections, which requires only 3 steps to infect a positive fraction of the whole graph.

KW - Bootstrap percolation

KW - Karamata’s theory

KW - Preferential attachment

KW - Random graphs

KW - Regular varying function

UR - http://www.scopus.com/inward/record.url?scp=85138130469&partnerID=8YFLogxK

U2 - 10.30757/ALEA.v19-50

DO - 10.30757/ALEA.v19-50

M3 - Article

AN - SCOPUS:85138130469

SN - 1980-0436

VL - 19

SP - 1221

EP - 1239

JO - Alea (Rio de Janeiro)

JF - Alea (Rio de Janeiro)

IS - 2

ER -

Spread of Infection over P.A. random graphs with edge insertion

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this