Hanke Moritz, Foraita Ronja
Leibniz Institute for Prevention Research and Epidemiology - BIPS, Department of Biometry and Data Management, Achterstr. 30, Bremen, Germany.
BMC Bioinformatics. 2017 May 16;18(1):261. doi: 10.1186/s12859-017-1677-x.
Different phenomena like the spread of a disease, social interactions or the biological relation between genes can be thought of as dynamic networks. These can be represented as a sequence of static graphs (so called graph snapshots). Based on this graph sequences, classical vertex centrality measures like closeness and betweenness centrality have been extended to quantify the importance of single vertices within a dynamic network. An implicit assumption for the calculation of temporal centrality measures is that the graph sequence contains all information about the network dynamics over time. This assumption is unlikely to be justified in many real world applications due to limited access to fully observed network data. Incompletely observed graph sequences lack important information about duration or existence of edges and may result in biased temporal centrality values.
To account for this incompleteness, we introduce the idea of extending original temporal centrality metrics by cloning graphs of an incomplete graph sequence. Focusing on temporal betweenness centrality as an example, we show for different simulated scenarios of incomplete graph sequences that our approach improves the accuracy of detecting important vertices in dynamic networks compared to the original methods. An age-related gene expression data set from the human brain illustrates the new measures. Additional results for the temporal closeness centrality based on cloned snapshots support our findings. We further introduce a new algorithm called REN to calculate temporal centrality measures. Its computational effort is linear in the number of snapshots and benefits from sparse or very dense dynamic networks.
We suggest to use clone temporal centrality measures in incomplete graph sequences settings. Compared to approaches that do not compensate for incompleteness our approach will improve the detection rate of important vertices. The proposed REN algorithm allows to calculate (clone) temporal centrality measures even for long snapshot sequences.
诸如疾病传播、社交互动或基因间的生物学关系等不同现象可被视为动态网络。这些网络可表示为一系列静态图（即所谓的图快照）。基于这些图序列，像接近中心性和中介中心性等经典顶点中心性度量已得到扩展，以量化动态网络中单个顶点的重要性。计算时间中心性度量的一个隐含假设是图序列包含了网络随时间动态变化的所有信息。由于获取完全观测到的网络数据存在限制，在许多实际应用中这个假设不太可能成立。不完全观测到的图序列缺乏关于边的持续时间或存在性的重要信息，可能导致时间中心性值出现偏差。
为了解决这种不完整性，我们提出通过克隆不完全图序列的图来扩展原始时间中心性度量的想法。以时间中介中心性为例，我们针对不完全图序列的不同模拟场景表明，与原始方法相比，我们的方法提高了在动态网络中检测重要顶点的准确性。来自人类大脑的一个与年龄相关的基因表达数据集说明了这些新度量。基于克隆快照的时间接近中心性的其他结果支持了我们的发现。我们还引入了一种名为REN的新算法来计算时间中心性度量。其计算量与快照数量呈线性关系，并且在稀疏或非常密集的动态网络中都有优势。
我们建议在不完全图序列设置中使用克隆时间中心性度量。与不补偿不完整性的方法相比，我们的方法将提高重要顶点的检测率。所提出的REN算法即使对于长快照序列也能计算（克隆）时间中心性度量。
