Core–periphery models for graphs based on their δ-hyperbolicity: An example using biological networks
Core–periphery models for graphs based on their δ-hyperbolicity: An example using biological networks
复制标题
基于 δ-双曲性的图的核心-外围模型：使用生物网络的示例
DOI：
10.1177/1748301816665519
复制
发表时间：
2017
影响因子：
0.9
通讯作者：
F. Dragan
中科院分区：
文献类型：
--
作者：
H. Alrasheed;F. Dragan
双曲性是图的一个全局性质，它衡量图的结构与树的距离。它嵌入了多个属性，便于解决在一般图形形式中很难解决的几个问题。本文不仅考虑了Gromov的δ-双曲性概念，而且分析了δ-双曲性与图的其它参数之间的关系，研究了图的双曲性。这种新的视角使我们能够根据图的双曲性对图进行分类，并表明许多生物网络是双曲的。然后，我们介绍了偏心度为基础的弯曲属性，我们利用提出了两个模型来确定一个图的核心顶点：最大峰值模型和最小覆盖集模型。在这个扩展版本的文件中，我们包括一些新的定理，以及在会议论文中提出的定理的证明。此外，我们提出的算法，我们所使用的每一个建议的核心识别模型，我们提供更多的分析，解释和例子。
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.