A signature of power law network dynamics
Can one hear the ‘sound’ of a growing network? We address the problem of recognizing the topology of evolving biological or social networks. Starting from percolation theory, we analytically prove a linear inverse relationship between two simple graph parameters—the logarithm of the average cluster size and logarithm of the ratio of the edges of the graph to the theoretically maximum number of edges for that graph—that holds for all growing power law graphs. The result establishes a novel property of evolving power-law networks in the asymptotic limit of network size. Numerical simulations as well as fitting to real-world citation co-authorship networks demonstrate that the result holds for networks of finite sizes, and provides a convenient measure of the extent to which an evolving family of networks belongs to the same power-law class.