Abstract: A power-law graph is any graph G = (V,E), whose
degree distribution follows a power law i.e. the number of vertices
in the graph with degree i, yi, is proportional to i^{-beta}: y_i is proportional to i^{-beta}. In this paper, we provide information-theoretic lower bounds
on the sample complexity of learning such power-law graphical
models i.e. graphical models whose Markov graph obeys the
power law. In addition, we briefly revisit some existing state of
the art estimators, and explicitly derive their sample complexity
for power-law graphs.
Download: pdf
Citation
- On the Difficulty of Learning Power Law Graphical Models (pdf, software)
R. Tandon, P. Ravikumar.
In IEEE International Symposium on Information Theory (ISIT), 2013.
Bibtex: