Header

UZH-Logo

Maintenance Infos

Detecting nestedness in graphs


Grimm, Alexander; Tessone, Claudio (2017). Detecting nestedness in graphs. In: Cherifi, Hocine; Gaito, Sabrina; Quattrociocchi, Walter; Sala, Alessandra. Complex Networks & Their Applications V : Proceedings of the 5th International Workshop on Complex Networks and their Applications. Zug, Switzerland: Springer, 171-182.

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.

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.

Statistics

Altmetrics

Additional indexing

Item Type:Book Section, refereed, original work
Communities & Collections:03 Faculty of Economics > Department of Business Administration
Dewey Decimal Classification:330 Economics
Language:English
Date:2017
Deposited On:13 Dec 2016 13:48
Last Modified:08 Dec 2017 21:23
Publisher:Springer
Series Name:Studies in Computational Intelligence
Number:693
Number of Pages:12
ISSN:1860-949X
ISBN:978-3-319-50900-6
Publisher DOI:https://doi.org/10.1007/978-3-319-50901-3_14
Related URLs:https://doi.org/10.1007/978-3-319-50901-3 (Publisher)
Other Identification Number:merlin-id:13950

Download

Full text not available from this repository.
View at publisher