Yury Malyshkin
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Yury Malyshkin has a total of 3 co-authors. Here are the top co-authors by number of shared publications:
- Maksim Zhukovskii
University of Sheffield
4 shared publications - Elliot Paquette
Department of Mathematics and Statistics McGill University
2 shared publications M.E. Zhukovskii
1 shared publication
Latest Publications
- 19 April 2025
- Published by Elsevier in Statistics & Probability Letters
- Vol. 224
Preferential attachment with choice-based edge step
- 19 April 2025
- Published by Elsevier in Statistics & Probability Letters
- Vol. 224
Preferential attachment with choice-based edge step
- Open Access
Logical convergence laws via stochastic approximation and Markov processes
Since the paper of Kleinberg and Kleinberg, SODA'05, where it was proven that the preferential attachment random graph with degeneracy at least 3 does not obey the first order 0-1 law, no general methods were developed to study logical limit laws for recursive random graph models with arbitrary degeneracy. Even in the (possibly) simplest case of the uniform attachment, it is still not known whether the first order convergence law holds in this model. We prove that the uniform attachment random graph with bounded degrees obeys the first order convergence law. To prove the law, we describe dynamics of first order equivalence classes of the random graph using Markov chains. The convergence law follows from the existence of a limit distribution of the considered Markov chain. To show the latter convergence, we use stochastic approximation processes.
Open AccessLogical convergence laws via stochastic approximation and Markov processes
Since the paper of Kleinberg and Kleinberg, SODA'05, where it was proven that the preferential attachment random graph with degeneracy at least 3 does not obey the first order 0-1 law, no general methods were developed to study logical limit laws for recursive random graph models with arbitrary degeneracy. Even in the (possibly) simplest case of the uniform attachment, it is still not known whether the first order convergence law holds in this model. We prove that the uniform attachment random graph with bounded degrees obeys the first order convergence law. To prove the law, we describe dynamics of first order equivalence classes of the random graph using Markov chains. The convergence law follows from the existence of a limit distribution of the considered Markov chain. To show the latter convergence, we use stochastic approximation processes.
- 24 March 2022
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 314, 223-227
γ-variable first-order logic of preferential attachment random graphs
- 24 March 2022
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 314, 223-227
γ-variable first-order logic of preferential attachment random graphs
- 18 January 2022
- Published by Elsevier in Discrete Mathematics
- Vol. 345 (5)
γ-variable first-order logic of uniform attachment random graphs
- 18 January 2022
- Published by Elsevier in Discrete Mathematics
- Vol. 345 (5)
γ-variable first-order logic of uniform attachment random graphs
- Open Access
$γ$-variable first-order logic of uniform attachment random graphs
We study logical limit laws for uniform attachment random graphs. In this random graph model, vertices and edges are introduced recursively: at time $n+1$, the vertex $n+1$ is introduced together with $m$ edges joining the new vertex with $m$ different vertices chosen uniformly at random from $1,\ldots,n$. We prove that this random graph obeys convergence law for first-order sentences with at most $m-2$ variables.Open Access$γ$-variable first-order logic of uniform attachment random graphs
We study logical limit laws for uniform attachment random graphs. In this random graph model, vertices and edges are introduced recursively: at time $n+1$, the vertex $n+1$ is introduced together with $m$ edges joining the new vertex with $m$ different vertices chosen uniformly at random from $1,\ldots,n$. We prove that this random graph obeys convergence law for first-order sentences with at most $m-2$ variables. - 1 June 2021
- Published by Elsevier in Statistics & Probability Letters
- Vol. 173
MSO 0-1 law for recursive random trees
- 1 June 2021
- Published by Elsevier in Statistics & Probability Letters
- Vol. 173
MSO 0-1 law for recursive random trees
- Open Access
MSO 0-1 law for recursive random trees
We prove the monadic second order 0-1 law for two recursive tree models: uniform attachment tree and preferential attachment tree. We also show that the first order 0-1 law does not hold for non-tree uniform attachment models.
Open AccessMSO 0-1 law for recursive random trees
We prove the monadic second order 0-1 law for two recursive tree models: uniform attachment tree and preferential attachment tree. We also show that the first order 0-1 law does not hold for non-tree uniform attachment models.
- 1 January 2021
- Published by Tver State University in Physical and Chemical Aspects of the Study of Clusters, Nanostructures and Nanomaterials
- No. 13,p. 483-494
PREFERENTIAL ATTACHMENT WITH FITNESS DEPENDENT CHOYICE
- 1 January 2021
- Published by Tver State University in Physical and Chemical Aspects of the Study of Clusters, Nanostructures and Nanomaterials
- No. 13,p. 483-494
PREFERENTIAL ATTACHMENT WITH FITNESS DEPENDENT CHOYICE
- Open Access
Preferential attachment combined with random number of choices
We study an asymptotical behavior of the maximal degree in the degree distribution in an evolving tree model combining the local choice and the Mori's preferential attachment. In the considered model, the random graph is constructed in the following way. At each step, a new vertex is introduced. Then, we connect it with one (the vertex with the largest degree is chosen) of $d$ (for random $d$) possible neighbors, which are sampled from the set of the existing vertices with the probability proportional to their degrees plus some parameter $\beta>-1$. It is known that the maximum of the degree distribution for non-random $d>2$ has linear behaviour and, for $d=2$, asymptoticaly equals to $n/\ln n$ up to a constant factor. We prove that if $\mathbb{E}d2+\beta$, it has linear behavior and if $\mathbb{E}d=2+\beta$ the maximal degree is of order $n/\ln n$. The proof combines standard preferential attachment approaches with martingales and stochastic approximation techniques. We also use stochastic approximation results to get a multidimentional central limit theorem for the numbers of vertices with fixed degrees.Open AccessPreferential attachment combined with random number of choices
We study an asymptotical behavior of the maximal degree in the degree distribution in an evolving tree model combining the local choice and the Mori's preferential attachment. In the considered model, the random graph is constructed in the following way. At each step, a new vertex is introduced. Then, we connect it with one (the vertex with the largest degree is chosen) of $d$ (for random $d$) possible neighbors, which are sampled from the set of the existing vertices with the probability proportional to their degrees plus some parameter $\beta>-1$. It is known that the maximum of the degree distribution for non-random $d>2$ has linear behaviour and, for $d=2$, asymptoticaly equals to $n/\ln n$ up to a constant factor. We prove that if $\mathbb{E}d2+\beta$, it has linear behavior and if $\mathbb{E}d=2+\beta$ the maximal degree is of order $n/\ln n$. The proof combines standard preferential attachment approaches with martingales and stochastic approximation techniques. We also use stochastic approximation results to get a multidimentional central limit theorem for the numbers of vertices with fixed degrees. - Open Access
High degree vertices in the Power of Choice model combined with Preferential Attachment
We find assimpotics for the first $k$ highest degrees of the degree distribution in an evolving tree model combining the local choice and the preferential attachment. In the considered model, the random graph is constructd in the following way. At each step, a new vertex is introduced. Then, we connect it with one (the vertex with the largest degree is chosen) of $d$ ($d>2$) possible neighbors, which are sampled from the set of the existing vertices with the probability proportional to their degrees. It is known that the maximum of the degree distribution in this model has linear behavior. We prove that $k$-th highest dergee has a sublinear behavior with a power depends on $d$. This contrasts sharply with what is seen in the preferential attachment model without choice, where all highest degrees in the degree distribution has the same sublinear order. The proof is based on showing that the considered tree has a persistent hub by comparison with the standard preferential attachment model, along with martingale arguments.Open AccessHigh degree vertices in the Power of Choice model combined with Preferential Attachment
We find assimpotics for the first $k$ highest degrees of the degree distribution in an evolving tree model combining the local choice and the preferential attachment. In the considered model, the random graph is constructd in the following way. At each step, a new vertex is introduced. Then, we connect it with one (the vertex with the largest degree is chosen) of $d$ ($d>2$) possible neighbors, which are sampled from the set of the existing vertices with the probability proportional to their degrees. It is known that the maximum of the degree distribution in this model has linear behavior. We prove that $k$-th highest dergee has a sublinear behavior with a power depends on $d$. This contrasts sharply with what is seen in the preferential attachment model without choice, where all highest degrees in the degree distribution has the same sublinear order. The proof is based on showing that the considered tree has a persistent hub by comparison with the standard preferential attachment model, along with martingale arguments.