Paper Info
Title
Detecting Nestedness in Graphs.
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 -upon node reordering- the adjacency matrix is stepwise, and it can be found in both bipartite and non-bipartite networks. Despite the strict mathematical 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 widely used: BINMATNEST, NODF, and FCM. However, these methods fail in detecting nestedness for graphs with low (NODF) and high (NODF, BINMATNEST) density or are developed for bipartite networks (FCM). Another common shortcoming of these approaches is the underlying asumption that all vertices belong to a nested component. However, many real-world networks have solely a sub-component (i.e. not all 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 Nestedness detection based on Local Neighborhood (NESTLON) [7]. This algorithm detects nestedness on a broad range of nested graphs independently of their density and resorts solely on local information. Further, by means of a benchmarking model we are able to tune the degree of nestedness in a controlled manner and study its efficiency. Our results show that NESTLON outperforms both BINMATNEST and NODF.
Year
DOI
Venue
2016
10.1007/978-3-319-50901-3_14
Studies in Computational Intelligence
Field
DocType
Volume
Adjacency matrix,Social network,Vertex (geometry),Computer science,Bipartite graph,Theoretical computer science,Topological graph theory,Benchmarking,Nestedness,Dense graph
Conference
693
ISSN
Citations 
PageRank 
1860-949X
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Alexander Grimm100.34
Claudio J. Tessone211615.73