Akrida, Eleni C, Mertzios, George B, Nikoletseas, Sotiris, Raptopoulos, Christoforos, Spirakis, Paul G ORCID: 0000-0001-5396-3749 and Zamaraev, Viktor
ORCID: 0000-0001-5755-4141
(2020)
How fast can we reach a target vertex in stochastic temporal graphs?
Journal of Computer and System Sciences, 114.
pp. 65-83.
Text
Stochastic_Temporal_JCSS_040320.pdf - Author Accepted Manuscript Download (620kB) | Preview |
Abstract
Temporal graphs abstractly model real-life inherently dynamic networks. Given a graph G, a temporal graph with G as the underlying graph is a sequence of subgraphs (snapshots) Gt of G, where t≥1. In this paper we study stochastic temporal graphs, i.e. stochastic processes G whose random variables are the snapshots of a temporal graph on G. A natural feature observed in various real-life scenarios is a memory effect in the appearance probabilities of particular edges; i.e. the probability an edge e∈E appears at time step t depends on its appearance (or absence) at the previous k steps. We study the hierarchy of models of memory-k, k≥0, in an edge-centric network evolution setting: every edge of G has its own independent probability distribution for its appearance over time. We thoroughly investigate the complexity of two naturally related, but fundamentally different, temporal path problems, called MINIMUM ARRIVAL and BEST POLICY.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | Temporal network, Stochastic temporal graph, Temporal path, #P-hard problem, Polynomial-time approximation scheme |
Depositing User: | Symplectic Admin |
Date Deposited: | 01 Jul 2020 09:16 |
Last Modified: | 18 Jan 2023 23:47 |
DOI: | 10.1016/j.jcss.2020.05.005 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3092258 |