Entropy of labeled versus unlabeled networks

Jeremy Paton, Harrison Hartle, Huck Stepanyants, Pim van der Hoorn, Dmitri Krioukov

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
10 Downloads (Pure)


The structure of a network is an unlabeled graph, yet graphs in most models of complex networks are labeled by meaningless random integers. Is the associated labeling noise always negligible, or can it overpower the network-structural signal? To address this question, we introduce and consider the sparse unlabeled versions of popular network models and compare their entropy against the original labeled versions. We show that labeled and unlabeled Erdos-Rényi graphs are entropically equivalent, even though their degree distributions are very different. The labeled and unlabeled versions of the configuration model may have different prefactors in their leading entropy terms, although this remains conjectural. Our main results are upper and lower bounds for the entropy of labeled and unlabeled one-dimensional random geometric graphs. We show that their unlabeled entropy is negligible in comparison with the labeled entropy. This means that in sparse networks the entropy of meaningless labeling may dominate the entropy of the network structure. The main implication of this result is that the common practice of using exchangeable models to reason about real-world networks with distinguishable nodes may introduce uncontrolled aberrations into conclusions made about these networks, suggesting a need for a thorough reexamination of the statistical foundations and key results of network science.

Original languageEnglish
Article number054308
Number of pages11
JournalPhysical Review E
Issue number5
Publication statusPublished - 17 Nov 2022


Dive into the research topics of 'Entropy of labeled versus unlabeled networks'. Together they form a unique fingerprint.

Cite this