Network Clocks: Detecting the Temporal Scale of Information Diffusion
Network Clocks: Detecting the Temporal Scale of Information Diffusion
复制标题
网络时钟：检测信息扩散的时间尺度
DOI：
10.1109/icdm.2017.102
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Petko Bogdanov
中科院分区：
文献类型：
--
作者：
Daniel J. DiTursi;Gregorios A. Katsios;Petko Bogdanov
信息扩散模型通常假设一个离散的时间轴，其中信息令牌在网络中传播。由于现实世界网络中的用户在其活动强度和周期上差异很大，我们在这项工作中的目标是回答：如何确定最符合观察到的网络内信息传播的时间尺度？现有方法的一个关键限制是，它们将时间轴聚合到固定大小的窗口中，这可能不适合所有网络节点的活动周期。我们提出了异构网络时钟的概念：事件到离散时间戳的映射，根据给定的级联传播模型最好地解释了它们的发生。我们关注广泛采用的独立级联（IC）模型，并将最佳时钟形式化为使所有观察到的级联的可能性最大化的时钟。单最优时钟（OC）问题可以在多项式时间内精确解决。然而，我们证明了学习多个最优时钟（kOC），对应于网络节点组的时间模式，是np困难的。我们提出了在级联激活总数中几乎线性时间内运行的可扩展解决方案，并讨论了每个变体的近似保证。我们的算法及其检测时钟能够改进级联大小分类（高达8%的F1提升）和改进缺失级联数据推断（提高0.15的召回率）。我们还证明了网络时钟在网络中扩散的内容类型内表现出一致性，并且相对于IC模型的传播概率参数具有鲁棒性。
Information diffusion models typically assume a discrete timeline in which an information token spreads in the network. Since users in real-world networks vary significantly in their intensity and periods of activity, our objective in this work is to answer: How to determine a temporal scale that best agrees with the observed information propagation within a network? A key limitation of existing approaches is that they aggregate the timeline into fixed-size windows, which may not fit all network nodes’ activity periods. We propose the notion of a heterogeneous network clock: a mapping of events to discrete timestamps that best explains their occurrence according to a given cascade propagation model. We focus on the widely-adopted independent cascade (IC) model and formalize the optimal clock as the one that maximizes the likelihood of all observed cascades. The single optimal clock (OC) problem can be solved exactly in polynomial time. However, we prove that learning multiple optimal clocks (kOC), corresponding to temporal patterns of groups of network nodes, is NP-hard. We propose scalable solutions that run in almost linear time in the total number of cascade activations and discuss approximation guarantees for each variant. Our algorithms and their detected clocks enable improved cascade size classification (up to 8% F1 lift) and improved missing cascade data inference (0.15 better recall). We also demonstrate that the network clocks exhibit consistency within the type of content diffusing in the network and are robust with respect to the propagation probability parameters of the IC model.