Grimm Alexander, Tessone Claudio J
1University Research Priority Program Social Networks, University of Zurich, Andreasstrasse 15, Zurich, Switzerland.
2Department of Business Administration, University of Zurich, Andreasstrasse 15, Zurich, Switzerland.
Appl Netw Sci. 2017;2(1):37. doi: 10.1007/s41109-017-0057-9. Epub 2017 Oct 23.
Many bipartite and unipartite real-world networks display a nested structure. Examples pervade different disciplines: biological ecosystems (e.g. mutualistic networks), economic networks (e.g. manufactures and contractors networks) to financial networks (e.g. bank lending networks), etc. A nested network has a topology such that a vertex's neighbourhood contains the neighbourhood of vertices of lower degree; thus -upon vertex reordering- the adjacency matrix is . Despite its strict mathematical definition and the interest triggered by their common occurrence, it is not easy to measure the extent of nested graphs unequivocally. Among others, there exist three methods for detection and quantification of nestedness that are widely used: BINMATNEST, NODF, and fitness-complexity metric (FCM). However, these methods fail in assessing the existence of nestedness for graphs of low (NODF) and high (NODF, BINMATNEST) network density. Another common shortcoming of these approaches is the underlying assumption that all vertices belong to a nested component. However, many real-world networks have solely a sub-component (i.e. a subset of its vertices) that is nested. Thus, unveiling which vertices pertain to the nested component is an important research question, unaddressed by the methods available so far. In this contribution, we study in detail the algorithm (NESTLON). This algorithm resorts solely on local information and detects nestedness on a broad range of nested graphs independently of their nature and density. Further, we introduce a benchmark model that allows us to tune the degree of nestedness in a controlled manner and study the performance of different algorithms. Our results show that NESTLON outperforms both BINMATNEST and NODF.
许多二分和单分的现实世界网络都呈现出嵌套结构。例子遍布不同学科：生物生态系统（如互利网络）、经济网络（如制造商和承包商网络）到金融网络（如银行贷款网络）等。嵌套网络具有这样一种拓扑结构，即一个顶点的邻域包含度数较低顶点的邻域；因此，在对顶点重新排序后，邻接矩阵是……。尽管其有严格的数学定义且因其普遍出现而引发了人们的兴趣，但要明确测量嵌套图的程度并不容易。其中，有三种广泛用于检测和量化嵌套性的方法：BINMATNEST、NODF和适应度 - 复杂度度量（FCM）。然而，这些方法在评估低网络密度（NODF）和高网络密度（NODF、BINMATNEST）的图的嵌套性存在情况时会失效。这些方法的另一个常见缺点是其潜在假设，即所有顶点都属于一个嵌套组件。然而，许多现实世界网络仅具有一个嵌套的子组件（即其顶点的一个子集）。因此，揭示哪些顶点属于嵌套组件是一个重要的研究问题，而迄今为止可用的方法尚未解决这一问题。在本论文中，我们详细研究了算法（NESTLON）。该算法仅依靠局部信息，并且能在广泛的嵌套图上检测嵌套性，而与图的性质和密度无关。此外，我们引入了一个基准模型，使我们能够以可控的方式调整嵌套程度，并研究不同算法的性能。我们的结果表明，NESTLON的性能优于BINMATNEST和NODF。
