Title
Sparsity Measure of a Network Graph: Gini Index.
Abstract
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.
Year
DOI
Venue
2018
10.1016/j.ins.2018.05.044
Information Sciences
Keywords
DocType
Volume
Network graph,Sparsity measure,Gini index,Edge density,Degree distribution,Power law,Network community detection algorithm
Journal
462
ISSN
Citations 
PageRank 
0020-0255
1
0.39
References 
Authors
0
3
Name
Order
Citations
PageRank
Swati Goswami110.39
C. A. Murthy21388126.63
Asit Kumar Das37316.06