Threshold-based network structural dynamics
Research output: Contribution to journal › Journal article › Research › peer-review
Standard
Threshold-based network structural dynamics. / Kipouridis, Evangelos; Spirakis, Paul G.; Tsichlas, Kostas.
In: Theoretical Computer Science, Vol. 944, 113669, 2023.Research output: Contribution to journal › Journal article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Threshold-based network structural dynamics
AU - Kipouridis, Evangelos
AU - Spirakis, Paul G.
AU - Tsichlas, Kostas
N1 - Publisher Copyright: © 2022 Elsevier B.V.
PY - 2023
Y1 - 2023
N2 - The interest in dynamic processes on networks is steadily rising in recent years. In this paper, we consider the (α,β)-Threshold Network Dynamics ((α,β)-Dynamics), where α≤β, in which only structural dynamics (edge dynamics of the network) are allowed, guided by local threshold rules executed by each node. In particular, in each discrete round t, each active pair of nodes u and v, computes a value E(u,v) (the potential of the pair) as a function of the local structure of the network at round t around the two nodes. If E(u,v)<α then the link (if it exists) between u and v is removed; if α≤E(u,v)<β then an existing link among u and v is maintained; if β≤E(u,v) then a link between u and v is established if not already present. New nodes cannot be inserted as a result of the protocol, and existing nodes cannot be removed. The microscopic structure of (α,β)-Dynamics appears to be simple, so that we are able to rigorously argue about it, but still flexible, so that we are able to design meaningful microscopic local rules that give rise to interesting macroscopic behaviors. Our goals are the following: a) to investigate the properties of the (α,β)-Threshold Network Dynamics and b) to show that (α,β)-Dynamics is expressive enough to solve complex problems on networks. Our contribution in these directions is twofold. We rigorously exhibit the claim about the expressiveness of (α,β)-Dynamics, both by designing a simple protocol that provably computes the k-core of the network as well as by showing that (α,β)-Dynamics are in fact Turing-Complete. Second and most important, we construct general tools for proving stabilization that work for a subclass of (α,β)-Dynamics and prove speed of convergence in a restricted setting.
AB - The interest in dynamic processes on networks is steadily rising in recent years. In this paper, we consider the (α,β)-Threshold Network Dynamics ((α,β)-Dynamics), where α≤β, in which only structural dynamics (edge dynamics of the network) are allowed, guided by local threshold rules executed by each node. In particular, in each discrete round t, each active pair of nodes u and v, computes a value E(u,v) (the potential of the pair) as a function of the local structure of the network at round t around the two nodes. If E(u,v)<α then the link (if it exists) between u and v is removed; if α≤E(u,v)<β then an existing link among u and v is maintained; if β≤E(u,v) then a link between u and v is established if not already present. New nodes cannot be inserted as a result of the protocol, and existing nodes cannot be removed. The microscopic structure of (α,β)-Dynamics appears to be simple, so that we are able to rigorously argue about it, but still flexible, so that we are able to design meaningful microscopic local rules that give rise to interesting macroscopic behaviors. Our goals are the following: a) to investigate the properties of the (α,β)-Threshold Network Dynamics and b) to show that (α,β)-Dynamics is expressive enough to solve complex problems on networks. Our contribution in these directions is twofold. We rigorously exhibit the claim about the expressiveness of (α,β)-Dynamics, both by designing a simple protocol that provably computes the k-core of the network as well as by showing that (α,β)-Dynamics are in fact Turing-Complete. Second and most important, we construct general tools for proving stabilization that work for a subclass of (α,β)-Dynamics and prove speed of convergence in a restricted setting.
KW - Network dynamics
KW - Stabilization
U2 - 10.1016/j.tcs.2022.12.019
DO - 10.1016/j.tcs.2022.12.019
M3 - Journal article
AN - SCOPUS:85146080992
VL - 944
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
M1 - 113669
ER -
ID: 371555615