Giant descendant trees, matchings, and independent sets in age-biased attachment graphs
From MaRDI portal
Publication:5086992
Abstract: We study two models of an age-biased graph process: the -version of the preferential attachment graph model (PAM) and the uniform attachment graph model (UAM), with attachments for each of incoming vertices. We show that almost surely the scaled size of a breadth-first (descendant) tree rooted at a fixed vertex converges, for , to a limit whose distribution is a mixture of two beta-distributions and a single beta-distribution respectively, and that for the limit is . We also analyze the likely performance of two greedy (online) algorithms, for a large matching set and a large independent set, and determine--for each model and each greedy algorithm--both a limiting fraction of vertices involved and an almost sure convergence rate.
Recommendations
- A note on the number of matchings and independent sets in trees
- scientific article; zbMATH DE number 1334618
- On the independence number and the chromatic number of generalized preferential attachment models
- On maximal independent sets of nodes in trees
- On tree census and the giant component in sparse random graphs
- On subgraph number independence in trees
- Connected graphs with a large number of independent sets
- Matchings in random superpositions of bipartite trees
- Scaling limits and influence of the seed graph in preferential attachment trees
- Publication:4726290
Cites work
- scientific article; zbMATH DE number 3150484 (Why is no real title available?)
- scientific article; zbMATH DE number 1246225 (Why is no real title available?)
- scientific article; zbMATH DE number 1540669 (Why is no real title available?)
- scientific article; zbMATH DE number 3443655 (Why is no real title available?)
- A new class of scale free random graphs
- Asymptotic behavior and distributional limits of preferential attachment graphs
- Concentration of measure and isoperimetric inequalities in product spaces
- Crawling on Simple Models of Web Graphs
- Directed scale-free graphs
- Emergence of Scaling in Random Networks
- High Degree Vertices and Eigenvalues in the Preferential Attachment Graph
- Introduction to Random Graphs
- Joint degree distributions of preferential attachment random graphs
- Linearized chord diagrams and an upper bound for vassiliev invariants
- Looking for vertex number one
- Lower Bounds and Algorithms for Dominating Sets in Web Graphs
- Note on the heights of random recursive trees and random m‐ary search trees
- On Bollobás‐Riordan random pairing model of preferential attachment graph
- On a memory game and preferential attachment graphs
- On a random graph evolving by degrees
- On certain connectivity properties of the internet topology
- On connectivity, conductance and bootstrap percolation for a random \(K\)-out, age-biased graph
- On random trees
- On the probable behaviour of some algorithms for finding the stability number of a graph
- Perfect matchings and Hamiltonian cycles in the preferential attachment model
- Preferential attachment without vertex growth: emergence of the giant component
- Random Graphs
- Random graphs and complex networks. Volume 1
- Random graphs.
- Random recursive trees and preferential attachment trees are random split trees
- Robustness and Vulnerability of Scale-Free Random Graphs
- The Maximum Degree of the Barabási–Albert Random Tree
- 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
This page was built for publication: Giant descendant trees, matchings, and independent sets in age-biased attachment graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5086992)
