Description
Abstract:
Real-world networks evolve over time via additions or removals of vertices
and edges. In network evolution models, vertex degree may vary arbitrarily
as the network grows. However, in real-world networks where maintaining
connections has some local non-negligible cost, vertex degrees are bounded
by intrinsic properties of the underlying node (e.g., the number of friends
in social networks, or the number of physical connections of nodes in
infrastructure networks). The degrees of vertices can even be constants over
time in some networks (e.g., the valency of an atom in a molecule).
The recently introduced degree-preserving network growth (DPG) family of
models preserves the vertex degree throughout the growth process.
Following up on the lecture by Zoltán Toroczkai on DPG models from a
physicist's point of view (held in the previous semester), in this talk we will
explore the connections of DPG to matchings, Pósa's theorem, Kundu's theorem,
scale free networks, and prime numbers.