Chained graphs and some applications
Chained graphs and some applications
复制标题
DOI：
10.1007/s41109-021-00377-4
复制
发表时间：
2021-06-01
影响因子：
2.2
通讯作者：
Zhang, Yunzi
中科院分区：
文献类型：
--
作者：
Concas, Anna;Reichel, Lothar;Zhang, Yunzi
本文引入了链图和半链图的概念。图的链，当存在时，精炼了二分性的概念并传达了重要的结构信息。同时引入了中心顶点v(c)的概念。它是一个顶点，其到图中所有其他顶点的距离的p次和是最小的，其中一对顶点之间的距离{v(c)， v}是由从v(c)到v所需要遍历的最小边数来测量的。这个概念扩展了接近中心性的定义。中心节点的重要应用包括信息传输和城市规划。给出了近似中心节点的识别算法，并给出了算例。
This paper introduces the notions of chained and semi-chained graphs. The chain of a graph, when existent, refines the notion of bipartivity and conveys important structural information. Also the notion of a center vertex v(c) is introduced. It is a vertex, whose sum of p powers of distances to all other vertices in the graph is minimal, where the distance between a pair of vertices {v(c), v} is measured by the minimal number of edges that have to be traversed to go from v(c) to v. This concept extends the definition of closeness centrality. Applications in which the center node is important include information transmission and city planning. Algorithms for the identification of approximate central nodes are provided and computed examples are presented.