Threshold-based Network Structural Dynamics
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Threshold-based Network Structural Dynamics. / Kipouridis, Evangelos; Spirakis, Paul; Tsichlas, K.
Structural Information and Communication Complexity: 28th International Colloquium, SIROCCO 2021, Wrocław, Poland, June 28 – July 1, 2021, Proceedings. ed. / Tomasz Jurdzińsk; Stefan Schmid. Springer, 2021. p. 127-145 (Lecture Notes in Computer Science, Vol. 12810).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
, Wrocław, Poland, 28/06/2021. https://doi.org/10.1007/978-3-030-79527-6_8
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Threshold-based Network Structural Dynamics
AU - Kipouridis, Evangelos
AU - Spirakis, Paul
AU - Tsichlas, K.
PY - 2021
Y1 - 2021
N2 - The interest in dynamic processes on networks is steadily rising in recent years. In this paper, we consider the $(\alpha,\beta)$-Thresholded Network Dynamics ($(\alpha,\beta)$-Dynamics), where $\alpha\leq \beta$, in which only structural dynamics (dynamics of the network) are allowed, guided by local thresholding rules executed in each node. In particular, in each discrete round $t$, each pair of nodes $u$ and $v$ that are allowed to communicate by the scheduler, computes a value $\mathcal{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 $\mathcal{E}(u,v) < \alpha$ then the link (if it exists) between $u$ and $v$ is removed; if $\alpha \leq \mathcal{E}(u,v) < \beta$ then an existing link among $u$ and $v$ is maintained; if $\beta \leq \mathcal{E}(u,v)$ then a link between $u$ and $v$ is established if not already present. The microscopic structure of $(\alpha,\beta)$-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 $(\alpha,\beta)$-Thresholded Network Dynamics and b) to show that $(\alpha,\beta)$-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 $(\alpha,\beta)$-Dynamics, both by designing a simple protocol that provably computes the $k$-core of the network as well as by showing that $(\alpha,\beta)$-Dynamics is in fact Turing-Complete. Second and most important, we construct general tools for proving stabilization that work for a subclass of $(\alpha,\beta)$-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 $(\alpha,\beta)$-Thresholded Network Dynamics ($(\alpha,\beta)$-Dynamics), where $\alpha\leq \beta$, in which only structural dynamics (dynamics of the network) are allowed, guided by local thresholding rules executed in each node. In particular, in each discrete round $t$, each pair of nodes $u$ and $v$ that are allowed to communicate by the scheduler, computes a value $\mathcal{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 $\mathcal{E}(u,v) < \alpha$ then the link (if it exists) between $u$ and $v$ is removed; if $\alpha \leq \mathcal{E}(u,v) < \beta$ then an existing link among $u$ and $v$ is maintained; if $\beta \leq \mathcal{E}(u,v)$ then a link between $u$ and $v$ is established if not already present. The microscopic structure of $(\alpha,\beta)$-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 $(\alpha,\beta)$-Thresholded Network Dynamics and b) to show that $(\alpha,\beta)$-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 $(\alpha,\beta)$-Dynamics, both by designing a simple protocol that provably computes the $k$-core of the network as well as by showing that $(\alpha,\beta)$-Dynamics is in fact Turing-Complete. Second and most important, we construct general tools for proving stabilization that work for a subclass of $(\alpha,\beta)$-Dynamics and prove speed of convergence in a restricted setting.
UR - https://www.youtube.com/watch?v=Tso9CBikRTI
U2 - 10.1007/978-3-030-79527-6_8
DO - 10.1007/978-3-030-79527-6_8
M3 - Article in proceedings
SN - 978-3-030-79526-9
T3 - Lecture Notes in Computer Science
SP - 127
EP - 145
BT - Structural Information and Communication Complexity
A2 - Jurdzińsk, Tomasz
A2 - Schmid, Stefan
PB - Springer
T2 - 28th International Colloquium, SIROCCO 2021<br/>
Y2 - 28 June 2021 through 1 July 2021
ER -
ID: 287622462