Node Ordering for Rescalable Network Summarization (or, the Apparent Magic of Word Frequency and Age of Acquisition in the Lexicon)

How can we “scale down” an n-node network G to a smaller network, with k « n nodes, so that G (approximately) maintains the important structural properties of G? There is a voluminous literature on many versions of this problem if k is given in advance, but one’s tolerance for approximation (and the resulting value of k) will vary. Here, then, we formulate a “rescalable” version of this approximation task for complex networks. Specifically, we propose a node ordering version of graph summarization: permute the nodes of G so that the subgraph induced by the first k nodes is a good size-k approximation of G, averaged over the full range of possible sizes k. We consider as a case study the phonological network of English words, and discover two natural word orders (word frequency and age of acquisition) that do a surprisingly good job of rescalably summarizing the lexicon.