Sparsity measure of a network graph: Gini index

This article explores the problem of formulating a general measure of sparsity of network graphs. Based on an available definition sparsity of a dataset, namely Gini index, it provides a way to define sparsity measure of a network graph. We name the sparsity measure so introduced as sparsity index. Sparsity measures are commonly associated with six properties, namely, Robin Hood, Scaling, Rising Tide, Cloning, Bill Gates and Babies. Sparsity index directly satisfies four of these six properties; does not satisfy Cloning and satisfies Scaling for some specific cases. A comparison of the proposed index is drawn with Edge Density (the proportion of the sum of degrees of all nodes in a graph compared to the total possible degrees in the corresponding fully connected graph), by showing mathematically that as the edge density of an undirected graph increases, its sparsity index decreases. The paper highlights how the proposed sparsity measure can reveal important properties of a network graph. Further, a relationship has been drawn analytically between the sparsity index and the exponent term of a power law distribution (a distribution known to approximate the degree distribution of a wide variety of network graphs). To illustrate application of the proposed index, a community detection algorithm for network graphs is presented. The algorithm produces overlapping communities with no input requirement on number or size of the communities; has a computational complexity O(n2), where n is the number of nodes of the graph. The results validated on artificial and real networks show its effectiveness.