An invariant of scale-free graphs

In many applications (including biology and the study of computer networks) graphs are found to be scale-free. It has been argued that this property alone does not tell us much about the structure of the graph. In this paper, we introduce a numerical characteristic of a graph, which we call the astral index, and which can be calculated efficiently. We demonstrate that the Barabási-Albert algorithm for generating scale-free graphs produces not just scale-free graphs, but only scale-free graphs with a constant astral index. On some examples of biological graphs, we see that they not only are scale-free, but also share the value of the astral index with Barabási-Albert graphs. For comparison, we demonstrate that the Erdős–Rényi model for generating random graphs also generates only graphs with a constant astral index, whose value significantly differs from that of graphs generated by the Barabási-Albert algorithm.