Large deviations for the degree structure in preferential attachment schemes
From MaRDI portal
Abstract: Preferential attachment schemes, where the selection mechanism is linear and possibly time-dependent, are considered, and an infinite-dimensional large deviation principle for the sample path evolution of the empirical degree distribution is found by Dupuis-Ellis-type methods. Interestingly, the rate function, which can be evaluated, contains a term which accounts for the cost of assigning a fraction of the total degree to an "infinite" degree component, that is, when an atypical "condensation" effect occurs with respect to the degree structure. As a consequence of the large deviation results, a sample path a.s. law of large numbers for the degree distribution is deduced in terms of a coupled system of ODEs from which power law bounds for the limiting degree distribution are given. However, by analyzing the rate function, one can see that the process can deviate to a variety of atypical nonpower law distributions with finite cost, including distributions typically associated with sub and superlinear selection models.
A preferential attachment scheme is specified with two functions of time: a probability \(p(t)\) and a non-negative weight component \(b(t)\). At each time step \(t\) a new node is attached to the current graph. With probability \(p(t)\) it is attached as an isolated node, and with probability \(1-p(t)\) it is attached by an edge to a node in the current graph that is selected with probability proportional to a weight \(w(t,d)=d+b(t)\) of its degree \(d\) and time \(t\). Using this scheme the convergence to power law distributions and other laws are investigated for the empirical degree distribution.
Recommendations
- Degree asymptotics with rates for preferential attachment random graphs
- A scaling limit for the degree distribution in sublinear preferential attachment schemes
- Random networks with sublinear preferential attachment: degree evolutions
- Joint degree distributions of preferential attachment random graphs
- Directed preferential attachment models: limiting degree distributions and their tails
- Large deviation and anomalous fluctuations scaling in degree assortativity on configuration networks
- Scale-free property for degrees and weights in a preferential attachment random graph model
- Asymptotic degree distribution in preferential attachment graph models with multiple type edges
- Random networks with sublinear preferential attachment: the giant component
- Large degrees in scale-free inhomogeneous random graphs
Cites work
- A Brief History of Generative Models for Power Law and Lognormal Distributions
- A general model of web graphs
- Complex graphs and networks
- Complex networks. Structure, robustness and function.
- Connectivity Transitions in Networks with Super-Linear Preferential Attachment
- Emergence of Scaling in Random Networks
- Finiteness and fluctuations in growing networks
- Generalizations of Polya's urn problem
- Growth of preferential attachment random graphs via continuous-time branching processes
- scientific article; zbMATH DE number 1153603 (Why is no real title available?)
- scientific article; zbMATH DE number 1158743 (Why is no real title available?)
- scientific article; zbMATH DE number 2050468 (Why is no real title available?)
- scientific article; zbMATH DE number 1866312 (Why is no real title available?)
- scientific article; zbMATH DE number 2119677 (Why is no real title available?)
- Large deviations for the leaves in some random trees
- Large-Deviation Approximations for General Occupancy Models
- Limits of randomly grown graph sequences
- Multigraph limit of the dense configuration model and the preferential attachment graph
- Networks. An introduction.
- ON A CLASS OF SKEW DISTRIBUTION FUNCTIONS
- On certain connectivity properties of the internet topology
- On random trees
- On the spread of viruses on the Internet
- Random graph dynamics
- Random networks with sublinear preferential attachment: degree evolutions
- Random trees and general branching processes
- Rank-based attachment leads to power law graphs
- Scale-Free Networks
- Scale-free networks: a decade and beyond
- Statistical mechanics of complex networks
- The cover time of the preferential attachment graph
- The degree sequence of a scale-free random graph process
- The diameter of a scale-free random graph
- The Influence of Search Engines on Preferential Attachment
- The Maximum Degree of the Barabási–Albert Random Tree
- The structure and dynamics of networks
- The Structure and Function of Complex Networks
- Typical distances in ultrasmall random networks
- Width of a scale-free tree
Cited in
(10)- On dynamic random graphs with degree homogenization via anti-preferential attachment probabilities
- Rare event asymptotics for exploration processes for random graphs
- Asymptotic dependence of in- and out-degrees in a preferential attachment model with reciprocity
- On the growth of a superlinear preferential attachment scheme
- Distances and large deviations in the spatial preferential attachment model
- Large Deviations for the Stationary Measure of Networks Under Proportional Fair Allocations
- On terminal nodes and the degree profile of preferential dynamic attachment circuits
- A scaling limit for the degree distribution in sublinear preferential attachment schemes
- Large deviation and anomalous fluctuations scaling in degree assortativity on configuration networks
- Preferential attachment random graphs with general weight function
This page was built for publication: Large deviations for the degree structure in preferential attachment schemes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1948702)
