Scaling of Local Network Density and the Familiarity Model*

Network inhomogeneity usually results in varying densities, depending on the scale of observation, but the scaling of link density has been shown to universally scale inversely with the number of nodes. If, however, we redefine the density as a metric that scales from 0 for a tree structure to 1 for a complete subgraph, the scaling can better distinguish between structures. Here we study how the subgraph network density scales as we vary the scale of observation. Two extreme cases are found: organized structures and random structures such as in Erdos-Renyi networks. We show that real networks usually fall within this range, and can be characterized by the value of a scaling exponent. The results indicate that some real networks, such as the Gnutella sharing network, show signs of random mixture of connections between nodes, while others, such as the Amazon co-purchase network, behave similar to a lattice in terms of density scaling with sample size. To understand the scaling of densities, we introduce the familiarity model which can generate networks with tunable density scaling and it can interpret the results obtained in real networks.