Estimating the global density of graphs by a sparseness index

摘要

Computation of sparse matrix is key in a wide range of applications of science and engineering. Matrix is tightly bound to the graph data structure and frequently used as an effective alternative: the complexity of fairly complicated operations on graphs can be measured as the computer time required to execute a number of arithmetic operations on nonzero quantities of a matrix. In this perspective, sparse matrices are computationally advantageous.We present a rigorous refinement of the completeness index, a mathematical function designed to quantify the sparsity of matrices. We prove its mathematical properties as well as its usefulness in the biological realm.