Optimal Timelines for Network Processes
Optimal Timelines for Network Processes
复制标题
网络流程的最佳时间表
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Petko Bogdanov
中科院分区：
文献类型：
--
作者：
Daniel J. DiTursi;Carolyn S. Kaminski;Petko Bogdanov
网络动态的结构模型通常假设网络事件（节点激活或链路创建）的离散时间轴和基于事件历史和网络结构产生新事件的随机生成过程。为了采用这些模型进行预测，观测数据通常以固定的时间分辨率（例如，分钟或天）。然而，底层的网络过程可能在不同的时间点“加速”或“减速”，导致观察不太可能，预测不正确。面临的挑战是优化网络事件数据分析的时间尺度，这反过来又是基于底层网络过程的结构模型。我们介绍了一般的问题，推断网络事件数据的最佳时间分辨率。我们的目标是通过聚集和/或分解原始时间轴，将观察到的网络事件映射到离散的时间步长，从而使结构动力学模型能够很好地解释这些事件。我们统一了网络增长和信息扩散模型，并区分了短记忆和长记忆过程。我们证明，虽然最佳的时间聚合可以在多项式时间内进行，解体，因此，一般的时间尺度推理问题是NP-困难的。我们提出了可扩展的算法的问题，一些近似的保证，并采用它们缺失的事件恢复和时间链接预测，表现出显着的改善（绝对增加10%的F1测量事件恢复和5%的AUC的链接预测）相比，采用相同的算法的默认时间尺度的数据收集。
Structural models for network dynamics typically assume a discrete timeline of network events (node activation or link creation) and a stochastic generative process giving rise to new events based on the event history and the network structure. In order to employ these models for prediction, observational data is often aggregated at a fixed temporal resolution (e.g., minutes or days). However, the underlying network processes may “speed up” or “slow down” at different points in time, rendering observations unlikely and predictions incorrect. The challenge is to optimize the timescale for the analysis of network event data, which in turn is based on structural models of the underlying network processes. We introduce the general problem of inferring the optimal temporal resolution for network event data. The goal is to map observed network events to discrete time steps by aggregation and/or disaggregation of their original timeline such that they are collectively well-explained by structural dynamics models. We unify network growth and information diffusion models and differentiate between short- and long-memory processes. We demonstrate that while optimal temporal aggregation can be performed in polynomial time, disaggregation—and thus, the general timescale inference problem—is NP-hard. We propose scalable heuristics for the problem, some with approximation guarantees, and employ them for missing event recovery and temporal link prediction, demonstrating significant improvements (absolute increase of 10% in F1 measure for event recovery and of 5% in AUC for link prediction) compared to employing the same algorithms on the default timescale of data collection.
影响因子：
3.6
作者：
Amelkin, Victor;Bogdanov, Petko;Singh, Ambuj K.
通讯作者：
Singh, Ambuj K.