Unlabeled Network Science

Even though the structure of a network is an unlabeled graph, a vast majority of network models in network science and random graphs are models of labeled graphs. The difference between labeled and unlabeled random graph models is typically negligible in dense graphs. In sparse graphs, however, this difference is quite significant.

We illustrate this difference in three examples. We first review what is currently known about unlabeled Erdos-Renyi (ER) graphs. Even though the leading term of their entropy is the same as in labeled ER graphs (a necessary but not sufficient condition for model equivalence), their degree distributions are very different. In the configuration model (random graphs with a given degree sequence), the leading entropy terms may have different prefactors in labeled and unlabeled graphs. Our main results are tight lower and upper bounds for the entropy of labeled and unlabeled sparse one-dimensional random geometric graphs. We prove that their entropies scale differently, indicating that the leading contribution to the "randomness" of the labeled graphs comes from their random labeling, versus their random structure.

These results suggest a need for "unlabeled network science," reexamining the adequacy of certain models of random labeled graphs in applications to the statistical analysis of the structure of real-world networks. The difference between labeled and unlabeled random structures is likely to be even more significant in higher-order network models (hypergraphs and simplicial complexes), and poses a collection of challenging open problems in the theory of sparse graph limits.