When can you wire up a network?

Statistical Physics and Complexity Group meeting

When can you wire up a network?

Event details

Networks - collections of nodes and links between them - provide a generic description of the interactions between components of a large variety of complex systems. Quite often one wants to build a network with specific properties, and very often the property in question is the degree distribution - that is, the number of nodes that have a given number of neighbours. This raises the question: given a particular degree sequence (i.e., a list of the number of neighbours each node has), does there exist at least one way to connect the nodes with links to actually arrive at this degree sequence? What if we insist on the network being connected? And/or if we exclude the possibility that two nodes are connected by multiple links? Although this seems like a hard question to answer in general, it turns out that the criteria are fairly simple and the proofs are not too difficult. I shall attempt to decode Hakim (1962) J Soc Indust Appl Math 10 496 into more physicist-friendly language.