Abstract
Many real-world networks have a nested structure. Examples range from biological ecosystems (e.g. mutualistic networks), industry systems (e.g. New York garment industry) to inter-bank networks (e.g. Fedwire bank network). A nested network has a graph topology such that a vertex’s neighborhood contains the neighborhood of vertices of lower degree. Thus, the adjacency matrix is stepwise, which can be found in both bipartite and non-bipartite networks. Despite the strict mathe- matical characterization and their common occurrence, it is not easy to detect nested graphs unequivocally. Among others, there exist three methods for detection and quantification of nestedness that are being widely used: BINMATNEST, NODF, and FCM. However, those methods fail in detecting nestedness for graphs with low (NODF) and high (NODF, BINMATNEST) density or were developed for bipartite networks (FCM). The common shortcoming of these approaches is the underlying asumption that all vertices belong to the nested component. However, many real- world networks have solely a sub-component (i.e. not all elements of the graph) 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 Nestedness detection based on Local Neighborhood (NESTLON). This algorithm detects nestedness on a broad range of nested graphs independently of their density and resorts solely on local information. By means of a benchmarking model we are able to tune the degree of nestedness in a controlled manner. Our results show that NESTLON outperforms both BIN- MATNEST and NODF.
Grimm, Alexander