Degree-dependent threshold-based random sequential adsorption on random trees

Thomas M.M. Meyfroyt

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

Uittreksel

We consider a special version of random sequential adsorption (RSA) with nearest-neighbor interaction on infinite tree graphs. In classical RSA, starting with a graph with initially inactive nodes, each of the nodes of the graph is inspected in a random order and is irreversibly activated if none of its nearest neighbors are active yet. We generalize this nearest-neighbor blocking effect to a degree-dependent threshold-based blocking effect. That is, each node of the graph is assumed to have its own degree-dependent threshold and if, upon inspection of a node, the number of active direct neighbors is less than that node's threshold, the node will become irreversibly active. We analyze the activation probability of nodes on an infinite tree graph, given the degree distribution of the tree and the degree-dependent thresholds. We also show how to calculate the correlation between the activity of nodes as a function of their distance. Finally, we propose an algorithm which can be used to solve the inverse problem of determining how to set the degree-dependent thresholds in infinite tree graphs in order to reach some desired activation probabilities.

TaalEngels
Pagina's302-326
Aantal pagina's25
TijdschriftAdvances in Applied Probability
Volume50
Nummer van het tijdschrift1
DOI's
StatusGepubliceerd - 1 mrt 2018

Vingerafdruk

Random Sequential Adsorption
Random Trees
Chemical activation
Adsorption
Dependent
Vertex of a graph
Inverse problems
Graph in graph theory
Inspection
Nearest Neighbor
Activation
Degree Distribution
Inverse Problem
Calculate
Generalise

Trefwoorden

    Citeer dit

    @article{eedc8493a19f4e2d8857b0812e6c164d,
    title = "Degree-dependent threshold-based random sequential adsorption on random trees",
    abstract = "We consider a special version of random sequential adsorption (RSA) with nearest-neighbor interaction on infinite tree graphs. In classical RSA, starting with a graph with initially inactive nodes, each of the nodes of the graph is inspected in a random order and is irreversibly activated if none of its nearest neighbors are active yet. We generalize this nearest-neighbor blocking effect to a degree-dependent threshold-based blocking effect. That is, each node of the graph is assumed to have its own degree-dependent threshold and if, upon inspection of a node, the number of active direct neighbors is less than that node's threshold, the node will become irreversibly active. We analyze the activation probability of nodes on an infinite tree graph, given the degree distribution of the tree and the degree-dependent thresholds. We also show how to calculate the correlation between the activity of nodes as a function of their distance. Finally, we propose an algorithm which can be used to solve the inverse problem of determining how to set the degree-dependent thresholds in infinite tree graphs in order to reach some desired activation probabilities.",
    keywords = "Analytical model, counter-based gossip protocol, interacting particle system, jamming limit, random sequential adsorption, random tree graph",
    author = "Meyfroyt, {Thomas M.M.}",
    year = "2018",
    month = "3",
    day = "1",
    doi = "10.1017/apr.2018.14",
    language = "English",
    volume = "50",
    pages = "302--326",
    journal = "Advances in Applied Probability",
    issn = "0001-8678",
    publisher = "University of Sheffield",
    number = "1",

    }

    Degree-dependent threshold-based random sequential adsorption on random trees. / Meyfroyt, Thomas M.M.

    In: Advances in Applied Probability, Vol. 50, Nr. 1, 01.03.2018, blz. 302-326.

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    TY - JOUR

    T1 - Degree-dependent threshold-based random sequential adsorption on random trees

    AU - Meyfroyt,Thomas M.M.

    PY - 2018/3/1

    Y1 - 2018/3/1

    N2 - We consider a special version of random sequential adsorption (RSA) with nearest-neighbor interaction on infinite tree graphs. In classical RSA, starting with a graph with initially inactive nodes, each of the nodes of the graph is inspected in a random order and is irreversibly activated if none of its nearest neighbors are active yet. We generalize this nearest-neighbor blocking effect to a degree-dependent threshold-based blocking effect. That is, each node of the graph is assumed to have its own degree-dependent threshold and if, upon inspection of a node, the number of active direct neighbors is less than that node's threshold, the node will become irreversibly active. We analyze the activation probability of nodes on an infinite tree graph, given the degree distribution of the tree and the degree-dependent thresholds. We also show how to calculate the correlation between the activity of nodes as a function of their distance. Finally, we propose an algorithm which can be used to solve the inverse problem of determining how to set the degree-dependent thresholds in infinite tree graphs in order to reach some desired activation probabilities.

    AB - We consider a special version of random sequential adsorption (RSA) with nearest-neighbor interaction on infinite tree graphs. In classical RSA, starting with a graph with initially inactive nodes, each of the nodes of the graph is inspected in a random order and is irreversibly activated if none of its nearest neighbors are active yet. We generalize this nearest-neighbor blocking effect to a degree-dependent threshold-based blocking effect. That is, each node of the graph is assumed to have its own degree-dependent threshold and if, upon inspection of a node, the number of active direct neighbors is less than that node's threshold, the node will become irreversibly active. We analyze the activation probability of nodes on an infinite tree graph, given the degree distribution of the tree and the degree-dependent thresholds. We also show how to calculate the correlation between the activity of nodes as a function of their distance. Finally, we propose an algorithm which can be used to solve the inverse problem of determining how to set the degree-dependent thresholds in infinite tree graphs in order to reach some desired activation probabilities.

    KW - Analytical model

    KW - counter-based gossip protocol

    KW - interacting particle system

    KW - jamming limit

    KW - random sequential adsorption

    KW - random tree graph

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

    U2 - 10.1017/apr.2018.14

    DO - 10.1017/apr.2018.14

    M3 - Article

    VL - 50

    SP - 302

    EP - 326

    JO - Advances in Applied Probability

    T2 - Advances in Applied Probability

    JF - Advances in Applied Probability

    SN - 0001-8678

    IS - 1

    ER -