Computational Properties of General Indices on Random Networks

Abstract

We perform a detailed (computational) scaling study of well-known general indices (the first and second variable Zagreb indices, M1α(G) and M2α(G), and the general sum-connectivity index, χα(G)) as well as of general versions of indices of interest: the general inverse sum indeg index ISIα(G) and the general first geometric-arithmetic index GAα(G) (with α∈R). We apply these indices on two models of random networks: Erdös–Rényi (ER) random networks GER(nER,p) and random geometric (RG) graphs GRG(nRG,r). The ER random networks are formed by nER vertices connected independently with probability p∈[0,1]; while the RG graphs consist of nRG vertices uniformly and independently distributed on the unit square, where two vertices are connected by an edge if their Euclidean distance is less or equal than the connection radius r∈[0,2]. Within a statistical random matrix theory approach, we show that the average values of the indices normalized to the network size scale with the average degree k of the corresponding random network models, where kER=(nER−1)p and kRG=(nRG−1)(πr2−8r3/3+r4/2). That is, X(GER)/nER≈X(GRG)/nRG if kER=kRG, with X representing any of the general indices listed above. With this work, we give a step forward in the scaling of topological indices since we have found a scaling law that covers different network models. Moreover, taking into account the symmetries of the topological indices we study here, we propose to establish their statistical analysis as a generic tool for studying average properties of random networks. In addition, we discuss the application of specific topological indices as complexity measures for random networks.

Keywords

• computational analysis of networks
• general topological indices
• Erdös–Rényi networks
• random geometric graphs