Core–periphery models for graphs based on their δ-hyperbolicity: An example using biological networks. Issue 1 (March 2017)

• Record Type: Journal Article
• Authors: Alrasheed, Hend; Dragan, Feodor F
• Is Part Of: Journal of algorithms & computational technology. Volume 11:Issue 1(2017)
• Page Start: 40
• Page End: 57
• Publication Date: 2017-03
• Subjects: Biological networks -- δ-hyperbolicity -- vertex eccentricity -- eccentricity centrality -- graph eccentricity layering -- eccentricity-based bending property -- shortest-path bending -- core–periphery organization; Computer algorithms -- Periodicals; Numerical calculations -- Periodicals; Computer algorithms; Numerical calculations; Periodicals; 518.1
• DOI: 10.1177/1748301816665519
• Languages: English
• ISSNs: 1748-3018

Abstract

Hyperbolicity is a global property of graphs that measures how close their structures are to trees in terms of their distances. It embeds multiple properties that facilitate solving several problems that found to be hard in the general graph form. In this paper, we investigate the hyperbolicity of graphs not only by considering Gromov's notion of δ -hyperbolicity but also by analyzing its relationship to other graph's parameters. This new perspective allows us to classify graphs with respect to their hyperbolicity and to show that many biological networks are hyperbolic. Then we introduce the eccentricity-based bending property which we exploit to identify the core vertices of a graph by proposing two models: the maximum-peak model and the minimum cover set model. In this extended version of the paper, we include some new theorems, as well as proofs of the theorems proposed in the conference paper. Also, we present the algorithms we used for each of the proposed core identification models, and we provide more analysis, explanations, and examples.