标题： 网络图的稀疏性度量：基尼指数 显示英文标题

标题： Sparsity Measure of a Network Graph: Gini Index

摘要： 本文探讨了稀疏性的一种流行度量方法——基尼系数在网络图中的应用。 各种各样的网络图恰好是稀疏的。 但在网络图中，通常用边密度来衡量稀疏性，它反映了图中所有节点度数之和与相应完全连接图中总可能度数的比例。 因此，边密度是一个简单的比率，并在其定义中存在局限性，主要体现在它所考虑的信息量上。 在本文中，我们通过推广基尼系数的概念，提出了一个定义网络图稀疏性的公式，并称之为稀疏性指数。 大多数常用于比较稀疏性度量的六个性质（即：罗宾汉、缩放、上涨潮、克隆、比尔·盖茨和婴儿）似乎都被所提出的指数所满足。 通过适当的例子，将边密度与稀疏性指数进行了比较，以突出所提出指数的有效性。 此外，理论上也证明了这两种度量在图变化时遵循相似的趋势，即随着图的边密度增加，其稀疏性指数会减少。 此外，本文从分析上建立了稀疏性指数与幂律分布的指数项之间的关系，这种分布已知可以近似各种网络图的度分布。 最后，本文强调了所提出的指数与基尼系数相结合如何揭示网络图的重要特性。 显示英文摘要

摘要： This article examines the application of a popular measure of sparsity, Gini Index, on network graphs. A wide variety of network graphs happen to be sparse. But the index with which sparsity is commonly measured in network graphs is edge density, reflecting the proportion of the sum of the degrees of all nodes in the graph compared to the total possible degrees in the corresponding fully connected graph. Thus edge density is a simple ratio and carries limitations, primarily in terms of the amount of information it takes into account in its definition. In this paper, we have provided a formulation for defining sparsity of a network graph by generalizing the concept of Gini Index and call it sparsity index. A majority of the six properties (viz., Robin Hood, Scaling, Rising Tide, Cloning, Bill Gates and Babies) with which sparsity measures are commonly compared are seen to be satisfied by the proposed index. A comparison between edge density and the sparsity index has been drawn with appropriate examples to highlight the efficacy of the proposed index. It has also been shown theoretically that the two measures follow similar trend for a changing graph, i.e., as the edge density of a graph increases its sparsity index decreases. Additionally, the paper draws a relationship, analytically, between the sparsity index and the exponent term of a power law distribution, a distribution which is known to approximate the degree distribution of a wide variety of network graphs. Finally, the article highlights how the proposed index together with Gini index can reveal important properties of a network graph.