Distinct Degrees and Their Distribution in Complex Networks

Abstract

We investigate a variety of statistical properties associated with the number of distinct degrees that exist in a typical network for various classes of networks. For a single realization of a network with N nodes that is drawn from an ensemble in which the number of nodes of degree k has an algebraic tail, N_k ~ N/k^nu for k>>1, the number of distinct degrees grows as N^{1/nu}. Such an algebraic growth is also observed in scientific citation data. We also determine the N dependence of statistical quantities associated with the sparse, large-k range of the degree distribution, such as the location of the first hole (where N_k=0), the last doublet (two consecutive occupied degrees), triplet, dimer (N_k=2), trimer, etc.

12 pages, 6 figures, iop format. Version 2: minor corrections

References in corpus (5)

• Efficient and exact sampling of simple graphs with given arbitrary degree sequence
• Zipf's Law Leads to Heaps' Law: Analyzing Their Relation in Finite-Size Systems
• Nonuniversal power law scaling in the probability distribution of scientific citations
• Stochastic dynamical model of a growing network based on self-exciting point process
• Runaway Events Dominate the Heavy Tail of Citation Distributions