How fast can we reach a target vertex in stochastic temporal graphs?
How fast can we reach a target vertex in stochastic temporal graphs?
复制标题
我们能够以多快的速度到达随机时间图中的目标顶点？
DOI：
10.1016/j.jcss.2020.05.005
复制
发表时间：
2020
影响因子：
1.1
通讯作者：
Akrida E
中科院分区：
文献类型：
--
作者：
Akrida E
时间图抽象地对现实生活中固有的动态网络进行建模。给定一个图G，一个以G为底层图的时间图是G的一个子图（快照）序列Gt，其中t≥ 1.本文研究随机时间图，即随机过程G，其随机变量是G上时间图的快照。在各种现实生活场景中观察到的一个自然特征是特定边缘出现概率的记忆效应;即边缘e∈ E在时间步长t出现的概率取决于它在前k步的出现（或不出现）。我们研究了记忆-k（k≥ 0）模型的层次结构，在一个以边为中心的网络演化环境中：G的每条边都有自己独立的概率分布，随着时间的推移它会出现。我们彻底调查两个自然相关，但根本不同的时间路径问题，称为最小到达和最佳策略的复杂性。
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) G t of G, where t≥ 1. In this paper we study stochastic temporal graphs, ie 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; ie 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.
登录
查看更多内容
具有随机链接可用性的临时网络：快速网络的情况
影响因子：
3.8
作者：
Akrida E
通讯作者：
Akrida E
影响因子：
22.7
作者：
O. Michail;P. Spirakis
通讯作者：
P. Spirakis
边均匀随机演化图中的覆盖时间
DOI：
--
发表时间：
2017
期刊：
Safety-critical Systems Symposium
影响因子：
--
作者：
I. Lamprou;R. Martin;P. Spirakis
通讯作者：
P. Spirakis
关于时变网络的延迟：较大的服务速率差异是否意味着较大的延迟？
DOI：
--
发表时间：
2018
期刊：
ACM Interational Symposium on Mobile Ad Hoc Networking and Computing
影响因子：
--
作者：
Sébastien Henri;S. Shneer;Patrick Thiran
通讯作者：
Patrick Thiran
影响因子：
2.8
作者：
Anne-Sophie Himmel;Hendrik Molter;R. Niedermeier;Manuel Sorge
通讯作者：
Anne-Sophie Himmel;Hendrik Molter;R. Niedermeier;Manuel Sorge