CENTRALITY INDEX OF A GRAPH
CENTRALITY INDEX OF A GRAPH
复制标题
DOI：
10.1007/bf02289527
复制
发表时间：
1966-01-01
期刊：
影响因子：
3
通讯作者：
SABIDUSSI, G
中科院分区：
文献类型：
--
作者：
SABIDUSSI, G
看来，在社会学和心理学文献中广泛使用的一个指标，其目的是衡量集中程度的图表。这种所谓的Bavelas中心性指数是由Leavitt（[10]，p.47）引入的，它是基于描述图的顶点位于中心的程度的相对中心性（由Bavelas在[1]和[2]中定义）。相对中心性是由Harary [6]独立引入的，唯一的区别是他考虑了有向图而不是无向图。Harary的大多数定义已经可以在[1和2]中找到。关于巴韦拉斯指数和相对中心性（称为距离和）的讨论也可以在（[9]，ch. 6，pp. 185-191）。最近有人提出了一些问题，巴韦拉斯指数的真实的意义。Flament（[5]，pp. 1999）指出，指数和直观中心性之间的对应关系并不令人满意。51-52）。他给出了两个例子（n-电路和完整的n-图），显然有很大的不同，在中心性（完整的n-图是高度集中的，n-电路几乎没有），但有相同的巴韦拉斯指数。然后给出了一个简单的分析，以表明所有的齐次图，即所有的顶点是自守的图，有最小的Bavelas指数，而不管它们的实际结构，从而证实了该指数反映直觉，但差。通过这一讨论，Flament进而认为，指数真正衡量的是”图中点之间的差异程度”或”自同构程度“。“我们将表明（第2节）Flament的批评还远远不够。虽然一个图的齐性意味着指数的极小性，但匡威则不成立。事实上，我们将给出一个具有最小指数且没有单个非平凡自同构的图的例子（可以给出无限多个其他例子）。Beauchamp [3]在Flament的基础上又进一步定义了一个新的指数，它是对Bavelas指数的改进。这种说法似乎是基于这样一个事实，即新的指数以与直觉相容的方式区分所有具有
It appears that widespread use is made in the sociological and psychological literature of an index which purports to measure the degree of centralization of a graph. This so-called Bavelas centrality index was introduced by Leavitt ([10], p. 47), and is based on the relative centraIities (defined by Bavelas in [1] and [2]) which describe the extent to which a vertex of a graph is centrally located. Relative centralities were independently introduced by Harary [6], the only difference being that he considers directed graphs instead of undirected ones. Most of Harary's definitions can already be found in [1 and 2]. A discussion of the Bavelas index and relative centralities (there called distance sums) can also be found in ([9], ch. 6, pp. 185-191). Recently some questions have been raised as to the real significance of Bavelas's index. That the correspondence between index and intuitive centrality is not very satisfactory has been noted by Flament ([5], pp. 51-52). He gives two examples (n-circuits and complete n-graphs) which obviously differ greatly in centrality (the complete n-graph being highly centralized, the n-circuit hardly at all) but have the same Bavelas index. A brief analysis is then given to show that all homogeneous graphs, ie, graphs all of whose vertices are automorphic, have minimal Bavelas index irrespective of their actual structure, thus confirming that the index reflects intuition but poorly. Through this discussion Flament is then led to think that what the index really measures is" the degree of disparity between the points of a graph" or" a degree of automorphism." We shall show (section 2) that Flament's criticism has not gone nearly far enough. Although homogeneity of a graph implies minimality of the index, the converse is by no means true. In fact, we shall give an example (and infinitely many others can be given) of a graph with minimum index and not a single nontrivial automorphism. Thus minimum index may be attained even in the case of extreme non-homogeneity.Beauchamp [3] has gone a step beyond Flament by actually defining a new index which, it is claimed, is an improvement over the Bavelas index. This claim seems to be based on the fact that the new index distinguishes, in a manner compatible with intuition, between graphs all of which have