Nonparametric sparsification of complex multiscale networks.-猫眼课题宝

DOI：

10.1371/journal.pone.0016431

发表时间：

2011-02-08

期刊：

PloS one

影响因子：

3.7

通讯作者：

中科院分区：

综合性期刊3区

文献类型：

作者：

Foti NJ;Hughes JM;Rockmore DN

来源链接：

https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3035633/?report=classic

许多现实世界的网络往往非常密集。感兴趣的特定示例出现在表示对象之间的成对相似性的网络的构建中。在这些情况下，所考虑的网络被加权，通常在任何两个节点之间具有正权重。此类网络的可视化和分析，特别是当节点数量较多时，可能会带来重大挑战，通常通过减少边集来解决这些挑战。任何有效的“稀疏化”都必须保留和反映网络中的重要结构。一种常见的方法是简单地应用硬阈值，仅保留那些权重超过某个预定值的边缘。一种更有原则的方法是通过在特定的零模型上进行假设检验来保留统计上显著的边缘，或者在应用某种阈值之前适当地转换原始权重矩阵，来提取网络的多尺度“骨干”。不幸的是，这些方法可能无法捕获多尺度结构，其中节点之间可能存在小但局部统计上显著的相似性。在本文中，我们介绍了一种新的方法，骨干提取，不依赖于任何特定的空模型，而是使用经验分布的相似性权重，以确定，然后保留统计上显着的边缘。我们表明，我们的方法适应在几个典型的真实的世界网络的局部边缘的权重分布的异质性，并在这样做保留其多尺度结构相对微不足道的额外计算成本。我们预计，这种简单的方法将在分析大规模，高度连接的加权网络中有很大的用处。

Many real-world networks tend to be very dense. Particular examples of interest arise in the construction of networks that represent pairwise similarities between objects. In these cases, the networks under consideration are weighted, generally with positive weights between any two nodes. Visualization and analysis of such networks, especially when the number of nodes is large, can pose significant challenges which are often met by reducing the edge set. Any effective “sparsification” must retain and reflect the important structure in the network. A common method is to simply apply a hard threshold, keeping only those edges whose weight exceeds some predetermined value. A more principled approach is to extract the multiscale “backbone” of a network by retaining statistically significant edges through hypothesis testing on a specific null model, or by appropriately transforming the original weight matrix before applying some sort of threshold. Unfortunately, approaches such as these can fail to capture multiscale structure in which there can be small but locally statistically significant similarity between nodes. In this paper, we introduce a new method for backbone extraction that does not rely on any particular null model, but instead uses the empirical distribution of similarity weight to determine and then retain statistically significant edges. We show that our method adapts to the heterogeneity of local edge weight distributions in several paradigmatic real world networks, and in doing so retains their multiscale structure with relatively insignificant additional computational costs. We anticipate that this simple approach will be of great use in the analysis of massive, highly connected weighted networks.