Complex Networks & Their Applications V
Complex Networks & Their Applications V
复制标题
复杂网络
DOI：
10.1007/978-3-319-50901-3_12
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Arrigo F
中科院分区：
文献类型：
--
作者：
Arrigo F
描述人与人之间数字交互的时间切片网络通常很大且稀疏。例如，当以秒、分钟或小时测量时，描述社交媒体、语音呼叫或物理接近度的成对连接性就是这种情况。然而，如果我们希望量化和比较网络节点的整体时间依赖中心性，那么我们应该考虑信息在时间上的全球流动。由于时间相关的边结构通常允许信息在网络中广泛传播，因此稀疏但动态的成对交互的自然摘要通常会采用大型密集矩阵的形式。由于这个原因，计算时间依赖网络的节点中心性在计算和存储方面都是非常昂贵的;比单个静态网络要昂贵得多。在这项工作中，我们专注于动态的可通信性，这导致广播和接收中心性措施的情况下。我们推导出一个新的算法，用于计算时间相关的中心性，与动态通信矩阵的稀疏化版本。通过这种方式，计算和存储需求在每个时间点都减少到稀疏静态网络的计算和存储需求。新的算法是合理的，从第一原则，然后在一个大规模的数据集上进行测试。我们发现，即使有非常严格的稀疏性要求（保留不超过10倍的非零的个人时间片的数量），该算法准确地再现了高度中央节点的列表由底层的完整系统。这使我们能够以最小的存储级别和仅随时间点数量线性扩展的成本来捕获随时间变化的中心性。
Time sliced networks describing human-human digital interactions are typically large and sparse. This is the case, for example, with pairwise connectivity describing social media, voice call or physical proximity, when measured over seconds, minutes or hours. However, if we wish to quantify and compare the overall time-dependent centrality of the network nodes, then we should account for the global flow of information through time. Because the time-dependent edge structure typically allows information to diffuse widely around the network, a natural summary of sparse but dynamic pairwise interactions will generally take the form of a large dense matrix. For this reason, computing nodal centralities for a time-dependent network can be extremely expensive in terms of both computation and storage; much more so than for a single, static network. In this work, we focus on the case of dynamic communicability, which leads to broadcast and receive centrality measures. We derive a new algorithm for computing time-dependent centrality that works with a sparsified version of the dynamic communicability matrix. In this way, the computation and storage requirements are reduced to those of a sparse, static network at each time point. The new algorithm is justified from first principles and then tested on a large scale data set. We find that even with very stringent sparsity requirements (retaining no more than ten times the number of nonzeros in the individual time slices), the algorithm accurately reproduces the list of highly central nodes given by the underlying full system. This allows us to capture centrality over time with a minimal level of storage and with a cost that scales only linearly with the number of time points.