Comparison of large networks with sub-sampling strategies.
Comparison of large networks with sub-sampling strategies.
复制标题
DOI：
10.1038/srep28955
复制
发表时间：
2016-07-06
影响因子：
4.6
通讯作者：
Reinert G
中科院分区：
文献类型：
--
作者：
Ali W;Wegner AE;Gaunt RE;Deane CM;Reinert G
网络通常被用来表示大型数据集，这使得网络的比较在许多领域成为一个诱人的研究问题。这类分析的技术从简单地比较网络汇总统计数据到复杂但计算代价高昂的基于比对的方法各不相同。大多数现有的方法要么不能很好地推广到不同类型的网络，要么不能提供网络之间的定量相似性分数。相比之下，基于无对齐拓扑的网络相似性得分使我们能够分析包含不同类型和大小的数据的大型网络集。NETDIS是这样一个分数，它通过所有节点的局部邻域中的小的子图的计数来定义网络相似性。在这里，我们介绍了一种基于邻域的子抽样过程，通过局部邻域比较与网络比较的框架自然地联系在一起。我们的理论论证证明，Netdis的统计数据是基于类似大小的社区样本进行的。我们在经验数据集和合成数据集上的测试表明，通常只有10%的网络邻域足以实现最优性能，导致计算需求大幅减少。该抽样过程即使在网络的小样本已知的情况下也适用，因此为非常大且可能不完整的数据集的网络比较提供了一种新的工具。
Networks are routinely used to represent large data sets, making the comparison of networks a tantalizing research question in many areas. Techniques for such analysis vary from simply comparing network summary statistics to sophisticated but computationally expensive alignment-based approaches. Most existing methods either do not generalize well to different types of networks or do not provide a quantitative similarity score between networks. In contrast, alignment-free topology based network similarity scores empower us to analyse large sets of networks containing different types and sizes of data. Netdis is such a score that defines network similarity through the counts of small sub-graphs in the local neighbourhood of all nodes. Here, we introduce a sub-sampling procedure based on neighbourhoods which links naturally with the framework of network comparisons through local neighbourhood comparisons. Our theoretical arguments justify basing the Netdis statistic on a sample of similar-sized neighbourhoods. Our tests on empirical and synthetic datasets indicate that often only 10% of the neighbourhoods of a network suffice for optimal performance, leading to a drastic reduction in computational requirements. The sampling procedure is applicable even when only a small sample of the network is known, and thus provides a novel tool for network comparison of very large and potentially incomplete datasets.