  Introduced the quantitative measure of the structural complexity of the graph
(complex network, etc.) based on a procedure similar to the renormalization
process, considering the difference between actual and averaged graph
structures on different scales. The proposed concept of the graph structural
complexity corresponds to qualitative comprehension of the complexity. The
proposed measure can be obtained for the weighted graphs also. The structural
complexities for various graph types were found - the deterministic infinite
and finite size graphs, artificial graphs of different natures including
percolation structures, and the time series of cardiac rhythms mapped to
complex networks using the parametric visibility graph algorithm. The latter
reaches a maximum near the formation of a giant component in the graph or at
the percolation threshold for 2D and 3D square lattices when a giant cluster
having a fractal structure has emerged. Therefore, the graph structural
complexity allows us to detect and study the processes similar to a
second-order phase transition in complex networks. A new node centrality index,
characterizing the structural complexity of a certain node within the graph
structure is introduced also, it can serve as a good auxiliary or
generalization to the local clustering coefficient. Such an index provides
another new ranking manner for the graph nodes. Being an easily computable
measure, the graph structural complexity might help to reveal different
features of complex systems and processes of the real world.
