Research Repository

An invariant of scale-free graphs

Vernitski, A (2015) An invariant of scale-free graphs. University of Essex.


Download (426kB) | Preview


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.

Item Type: Other
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science and Health > Mathematical Sciences, Department of
Depositing User: Jim Jamieson
Date Deposited: 16 Jan 2015 14:24
Last Modified: 17 Aug 2017 17:42

Actions (login required)

View Item View Item