2014/10/30 by Rasul Tutunov, Tutunov, Rasul, Haitham Bou Ammar +5
Mathematics · Physics and Astronomy · #60Cxx #Complex Network Analysis Techniques #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Opinion Dynamics and Social Influence #Physics and Society (physics.soc-ph) #Probability (math.PR) #Social and Information Networks (cs.SI) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1410.8515
openalex publication_date 2014/10/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper presents a tighter bound on the degree distribution of arbitrary Pólya urn graph processes, proving that the proportion of vertices with degree d obeys a power-law distribution P(d) ∝ d-γ for d ≤ n(1)/(6)-ε for any ε> 0, where n represents the number of vertices in the network. Previous work by Bollobás et al. formalized the well-known preferential attachment model of Barabási and Albert, and showed that the power-law distribution held for d ≤ n(1)/(15) with γ= 3. Our revised bound represents a significant improvement over existing models of degree distribution in scale-free networks, where its tightness is restricted by the Azuma-Hoeffding concentration inequality for martingales. We achieve this tighter bound through a careful analysis of the first set of vertices in the network generation process, and show that the newly acquired is at the edge of exhausting Bollobás model in the sense that the degree expectation breaks down for other powers.