Miklos Z. Racz
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
Miklos Z. Racz has a total of 15 co-authors. Here are the top co-authors by number of shared publications:
- Elchanan Mossel
Massachusetts Institute of Technology, Cambridge, USA
9 shared publications - Ronen Eldan
Weizmann Institute of Science, Rehovot, Israel
5 shared publications - Sébastien Bubeck
Microsoft Research
4 shared publications - Balint Toth
Budapest University of Technology
2 shared publications - Jian Ding
University of Pennsylvania, Philadelphia, USA
2 shared publications - Junhyong Kim
University of Pennsylvania
2 shared publications
Latest Publications
- 21 November 2016
- Published by Wiley in Random Structures & Algorithms
- Vol. 50 (4) , 584-611
Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors
- 21 November 2016
- Published by Wiley in Random Structures & Algorithms
- Vol. 50 (4) , 584-611
Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors
- 9 February 2016
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 25 (6) , 797-822
Coexistence in Preferential Attachment Networks
We introduce a new model of competition on growing networks. This extends the preferential attachment model, with the key property that node choices evolve simultaneously with the network. When a new node joins the network, it chooses neighbours by preferential attachment, and selects its type based on the number of initial neighbours of each type. The model is analysed in detail, and in particular, we determine the possible proportions of the various types in the limit of large networks. An important qualitative feature we find is that, in contrast to many current theoretical models, often several competitors will coexist. This matches empirical observations in many real-world networks.
- 9 February 2016
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 25 (6) , 797-822
Coexistence in Preferential Attachment Networks
We introduce a new model of competition on growing networks. This extends the preferential attachment model, with the key property that node choices evolve simultaneously with the network. When a new node joins the network, it chooses neighbours by preferential attachment, and selects its type based on the number of initial neighbours of each type. The model is analysed in detail, and in particular, we determine the possible proportions of the various types in the limit of large networks. An important qualitative feature we find is that, in contrast to many current theoretical models, often several competitors will coexist. This matches empirical observations in many real-world networks.
- Top Cited Papers
- 6 January 2016
- Published by Wiley in Random Structures & Algorithms
- Vol. 49 (3) , 503-532
Testing for high‐dimensional geometry in random graphs
We study the problem of detecting the presence of an underlying high‐dimensional geometric structure in a random graph. Under the null hypothesis, the observed graph is a realization of an Erdős‐Rényi random graph G(n, p). Under the alternative, the graph is generated from the model, where each vertex corresponds to a latent independent random vector uniformly distributed on the sphere , and two vertices are connected if the corresponding latent vectors are close enough. In the dense regime (i.e., p is a constant), we propose a near‐optimal and computationally efficient testing procedure based on a new quantity which we call signed triangles. The proof of the detection lower bound is based on a new bound on the total variation distance between a Wishart matrix and an appropriately normalized GOE matrix. In the sparse regime, we make a conjecture for the optimal detection boundary. We conclude the paper with some preliminary steps on the problem of estimating the dimension in . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 503–532, 2016
- 6 January 2016
- Published by Wiley in Random Structures & Algorithms
- Vol. 49 (3) , 503-532
Top Cited PapersTesting for high‐dimensional geometry in random graphs
We study the problem of detecting the presence of an underlying high‐dimensional geometric structure in a random graph. Under the null hypothesis, the observed graph is a realization of an Erdős‐Rényi random graph G(n, p). Under the alternative, the graph is generated from the model, where each vertex corresponds to a latent independent random vector uniformly distributed on the sphere , and two vertices are connected if the corresponding latent vectors are close enough. In the dense regime (i.e., p is a constant), we propose a near‐optimal and computationally efficient testing procedure based on a new quantity which we call signed triangles. The proof of the detection lower bound is based on a new bound on the total variation distance between a Wishart matrix and an appropriately normalized GOE matrix. In the sparse regime, we make a conjecture for the optimal detection boundary. We conclude the paper with some preliminary steps on the problem of estimating the dimension in . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 503–532, 2016
- Open Access
Coexistence in preferential attachment networks
We introduce a new model of competition on growing networks. This extends the preferential attachment model, with the key property that node choices evolve simultaneously with the network. When a new node joins the network, it chooses neighbours by preferential attachment, and selects its type based on the number of initial neighbours of each type. The model is analysed in detail, and in particular, we determine the possible proportions of the various types in the limit of large networks. An important qualitative feature we find is that, in contrast to many current theoretical models, often several competitors will coexist. This matches empirical observations in many real-world networks.
Open AccessCoexistence in preferential attachment networks
We introduce a new model of competition on growing networks. This extends the preferential attachment model, with the key property that node choices evolve simultaneously with the network. When a new node joins the network, it chooses neighbours by preferential attachment, and selects its type based on the number of initial neighbours of each type. The model is analysed in detail, and in particular, we determine the possible proportions of the various types in the limit of large networks. An important qualitative feature we find is that, in contrast to many current theoretical models, often several competitors will coexist. This matches empirical observations in many real-world networks.
- Open Access
Testing for high-dimensional geometry in random graphs
We study the problem of detecting the presence of an underlying high-dimensional geometric structure in a random graph. Under the null hypothesis, the observed graph is a realization of an Erd\H{o}s-R\'enyi random graph $G(n,p)$. Under the alternative, the graph is generated from the $G(n,p,d)$ model, where each vertex corresponds to a latent independent random vector uniformly distributed on the sphere $\mathbb{S}^{d-1}$, and two vertices are connected if the corresponding latent vectors are close enough. In the dense regime (i.e., $p$ is a constant), we propose a near-optimal and computationally efficient testing procedure based on a new quantity which we call signed triangles. The proof of the detection lower bound is based on a new bound on the total variation distance between a Wishart matrix and an appropriately normalized GOE matrix. In the sparse regime, we make a conjecture for the optimal detection boundary. We conclude the paper with some preliminary steps on the problem of estimating the dimension in $G(n,p,d)$.Open AccessTesting for high-dimensional geometry in random graphs
We study the problem of detecting the presence of an underlying high-dimensional geometric structure in a random graph. Under the null hypothesis, the observed graph is a realization of an Erd\H{o}s-R\'enyi random graph $G(n,p)$. Under the alternative, the graph is generated from the $G(n,p,d)$ model, where each vertex corresponds to a latent independent random vector uniformly distributed on the sphere $\mathbb{S}^{d-1}$, and two vertices are connected if the corresponding latent vectors are close enough. In the dense regime (i.e., $p$ is a constant), we propose a near-optimal and computationally efficient testing procedure based on a new quantity which we call signed triangles. The proof of the detection lower bound is based on a new bound on the total variation distance between a Wishart matrix and an appropriately normalized GOE matrix. In the sparse regime, we make a conjecture for the optimal detection boundary. We conclude the paper with some preliminary steps on the problem of estimating the dimension in $G(n,p,d)$. - Open Access
Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors
We study how the spectral gap of the normalized Laplacian of a random graph changes when an edge is added to or removed from the graph. There are known examples of graphs where, perhaps counterintuitively, adding an edge can decrease the spectral gap, a phenomenon that is analogous to Braess's paradox in traffic networks. We show that this is often the case in random graphs in a strong sense. More precisely, we show that for typical instances of Erd\H{o}s-R\'enyi random graphs $G(n,p)$ with constant edge density $p \in (0,1)$, the addition of a random edge will decrease the spectral gap with positive probability, strictly bounded away from zero. To do this, we prove a new delocalization result for eigenvectors of the Laplacian of $G(n,p)$, which might be of independent interest.Open AccessBraess's paradox for the spectral gap in random graphs and delocalization of eigenvectors
We study how the spectral gap of the normalized Laplacian of a random graph changes when an edge is added to or removed from the graph. There are known examples of graphs where, perhaps counterintuitively, adding an edge can decrease the spectral gap, a phenomenon that is analogous to Braess's paradox in traffic networks. We show that this is often the case in random graphs in a strong sense. More precisely, we show that for typical instances of Erd\H{o}s-R\'enyi random graphs $G(n,p)$ with constant edge density $p \in (0,1)$, the addition of a random edge will decrease the spectral gap with positive probability, strictly bounded away from zero. To do this, we prove a new delocalization result for eigenvectors of the Laplacian of $G(n,p)$, which might be of independent interest. - 1 March 2015
- Published by Elsevier in Theoretical Population Biology
- Vol. 100, 26-38
Can one hear the shape of a population history?
- 1 March 2015
- Published by Elsevier in Theoretical Population Biology
- Vol. 100, 26-38
Can one hear the shape of a population history?
- Open Access
From trees to seeds: on the inference of the seed from large trees in the uniform attachment model
We study the influence of the seed in random trees grown according to the uniform attachment model, also known as uniform random recursive trees. We show that different seeds lead to different distributions of limiting trees from a total variation point of view. To do this, we construct statistics that measure, in a certain well-defined sense, global "balancedness" properties of such trees. Our paper follows recent results on the same question for the preferential attachment model.
Open AccessFrom trees to seeds: on the inference of the seed from large trees in the uniform attachment model
We study the influence of the seed in random trees grown according to the uniform attachment model, also known as uniform random recursive trees. We show that different seeds lead to different distributions of limiting trees from a total variation point of view. To do this, we construct statistics that measure, in a certain well-defined sense, global "balancedness" properties of such trees. Our paper follows recent results on the same question for the preferential attachment model.
- Open Access
Can one hear the shape of a population history?
Reconstructing past population size from present day genetic data is a major goal of population genetics. Recent empirical studies infer population size history using coalescent-based models applied to a small number of individuals. Here we provide tight bounds on the amount of exact coalescence time data needed to recover the population size history of a single, panmictic population at a certain level of accuracy. In practice, coalescence times are estimated from sequence data and so our lower bounds should be taken as rather conservative.
Open AccessCan one hear the shape of a population history?
Reconstructing past population size from present day genetic data is a major goal of population genetics. Recent empirical studies infer population size history using coalescent-based models applied to a small number of individuals. Here we provide tight bounds on the amount of exact coalescence time data needed to recover the population size history of a single, panmictic population at a certain level of accuracy. In practice, coalescence times are estimated from sequence data and so our lower bounds should be taken as rather conservative.