# Large deviation for the empirical degree distribution of an Erdos-Renyi graph

@article{Mukherjee2013LargeDF, title={Large deviation for the empirical degree distribution of an Erdos-Renyi graph}, author={S. Mukherjee}, journal={arXiv: Probability}, year={2013} }

With $(d_1,\cdots,d_n)$ denoting the labeled degrees of an Erdos Renyi graph with parameter $\beta/n$, the large deviation principle for $\frac{1}{n}\sum\limits_{j=1}^n\delta_{d_j}$ (the empirical distribution of the degrees) is derived with a good rate function, with respect to a topology stronger than the weak topology.
As an application the degeneracy of some sparse ERGM models used in social networks is studied rigorously, showing in particular that using terms such as "gwd (geometrically… Expand

#### 5 Citations

Exponential Approximation, Method of Types for Empirical Neighbourhood Distributions of Random Graphs by Random Allocations

- Mathematics
- 2014

In this article we find exponential good approximation of the empirical neigbourhood distribution of symbolled random graphs conditioned to a given empirical symbol distribution and empirical pair… Expand

Exponential Approximation, Method of types for Empirical Neighbourhood Measures of Random graphs by Random Allocation

- Mathematics
- 2012

In this article we find exponential good approximation of the empirical neigbourhood distribution of symbolled random graphs conditioned to a given empirical symbol distribution and empirical pair… Expand

Joint large deviation result for empirical measures of the coloured random geometric graphs

- Mathematics, Medicine
- SpringerPlus
- 2016

We prove joint large deviation principle for the empirical pair measure and empirical locality measure of the near intermediate coloured random geometric graph models on n points picked uniformly in… Expand

Botnet Detection Based on Anomaly and Community Detection

- Computer Science
- IEEE Transactions on Control of Network Systems
- 2017

A novel two-stage approach for the important cybersecurity problem of detecting the presence of a botnet and identifying the compromised nodes (the bots) ideally before the botnet becomes active, and establishes sharp bounds on the suboptimality gap. Expand

Botnet detection using social graph analysis

- Computer Science, Physics
- 2014 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton)
- 2014

A novel botnet detection method that analyzes the social relationships among nodes that uses a refined modularity measure and formulates the problem as a non-convex optimization problem for which appropriate relaxation strategies are developed. Expand

#### References

SHOWING 1-10 OF 12 REFERENCES

Large deviations of empirical neighborhood distribution in sparse random graphs

- Mathematics
- 2015

Consider the Erdős–Renyi random graph on $$n$$n vertices where each edge is present independently with probability $$\lambda /n$$λ/n, with $$\lambda >0$$λ>0 fixed. For large $$n$$n, a typical random… Expand

The large deviation principle for the Erdős-Rényi random graph

- Computer Science, Mathematics
- Eur. J. Comb.
- 2011

The formulation and proof of the main result uses the recent development of the theory of graph limits by Lovasz and coauthors and Szemeredi's regularity lemma from graph theory to establish a large deviation principle under an appropriate topology. Expand

Large deviation principles for empirical measures of colored random graphs.

- Mathematics
- 2010

For any finite colored graph we define the empirical neighborhood measure, which counts the number of vertices of a given color connected to a given number of vertices of each color, and the… Expand

New Specifications for Exponential Random Graph Models

- Mathematics
- 2006

The most promising class of statistical models for expressing structural properties of social networks observed at one moment in time is the class of exponential random graph models (ERGMs), also… Expand

Specification of Exponential-Family Random Graph Models: Terms and Computational Aspects.

- Computer Science, Medicine
- Journal of statistical software
- 2008

The classes of statistics that are currently available in the ergm package are described and means for controlling the Markov chain Monte Carlo (MCMC) algorithm that the package uses for estimation are described. Expand

$I$-Divergence Geometry of Probability Distributions and Minimization Problems

- Mathematics
- 1975

JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide range of content in a trusted digital archive. We use information technology and… Expand

On an Elementary Proof of Some Asymptotic Formulas in the Theory of Partitions

- Mathematics
- 1942

Denote by p(n) the number of partitions of n. Hardy and Ramanujan^1 proved in their classical paper that ρ (n) 1 4n3+ C, c =π (\ f ra c { 2 } { 3 }) ^ \ f r a c { 1 } { 2 } , using complex function… Expand

Inference in Curved Exponential Family Models for Networks

- Mathematics
- 2006

Network data arise in a wide variety of applications. Although descriptive statistics for networks abound in the literature, the science of fitting statistical models to complex network data is still… Expand

Large Deviations Techniques and Applications

- Computer Science, Mathematics
- 1998

The LDP for Abstract Empirical Measures and applications-The Finite Dimensional Case and Applications of Empirically Measures LDP are presented. Expand

Asymptotics for symmetric 0 − 1 matrices with prescribed row sums

- Ars Combinatoria,
- 1985