Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-27T08:34:14.311Z Has data issue: false hasContentIssue false
  • English
  • Français

ENTROPY OF SOME MODELS OF SPARSE RANDOM GRAPHS WITH VERTEX-NAMES

Published online by Cambridge University Press:  31 January 2014

David J. Aldous  and
Nathan Ross
David J. Aldous
Affiliation:
Department of Statistics, 367 Evans Hall no. 3860, U.C. Berkeley, CA 94720 E-mail: [email protected]; www.stat.berkeley.edu/users/aldous
Get access Rights & Permissions [Opens in a new window]

Abstract

Consider the setting of sparse graphs on N vertices, where the vertices have distinct “names”, which are strings of length O(log N) from a fixed finite alphabet. For many natural probability models, the entropy grows as c N log N for some model-dependent rate constant c. The mathematical content of this paper is the (often easy) calculation of c for a variety of models, in particular for various standard random graph models adapted to this setting. Our broader purpose is to publicize this particular setting as a natural setting for future theoretical study of data compression for graphs, and (more speculatively) for discussion of unorganized versus organized complexity.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 28 , Issue 2 , April 2014 , pp. 145 - 168
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Alderson, D.L. & Doyle, J.C. (2010). Contrasting views of complexity and their implications for network-centric infrastructures. Systems, Man and Cybernetics 40: 839–852.Google Scholar
2.Aldous, D. (1991). The continuum random tree. I. Annals of Probability 19(1): 1–28.Google Scholar
3.Aldous, D. & Lyons, R. (2007). Processes on unimodular random networks. Electronic Journal of Probability 12(54): 1454–1508.Google Scholar
4.Aldous, D. & Michael Steele, J. (2004). The objective method: probabilistic combinatorial optimization and local weak convergence. Probability on Discrete Structures, Vol. 110, Encyclopaedia of Mathematical Science, Berlin: Springer, pp. 1–72.Google Scholar
5.Boldi, P. & Vigna, S. (2003). The webgraph framework I: compression techniques. In: Proceedings of the 13th International World Wide Web Conference, pp. 595–601. New York: ACM Press.Google Scholar
6.Chierichetti, F., Kumar, R., Lattanzi, S., Mitzenmacher, M., Panconesi, A., & Raghavan, P. (2009). On compressing social networks. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’09), New York, NY, USA, ACM, pp. 219–228.Google Scholar
7.Choi, Y. & Szpankowski, W. (2012). Compression of graphical structures: Fundamental limits, algorithms, and experiments. IEEE Transaction on Information Theory 58: 620–638.Google Scholar
8.Chung, F. & Lu, L. (2006). Complex graphs and networks, Vol. 107 CBMS Regional Conference Series in Mathematics. Published for the Conference Board of the Mathematical Sciences, Washington, DC.Google Scholar
9.Cover, T.M. & Thomas, J.A. (2006). Elements of Information Theory, 2nd ednHoboken, NJ, Wiley-Interscience [John Wiley & Sons].Google Scholar
10.Dehmer, M. & Mowshowitz, A. (2011). A history of graph entropy measures. Information Science 181(1): 57–78.Google Scholar
11.Kang, R.J. & McDiarmid, C. (2010). The t-improper chromatic number of random graphs. Combinatorics, Probabability and Computing 19(1): 87–98.Google Scholar
12.Kontoyiannis, I. (2003). Pattern matching and lossy data compression on random fields. IEEE Transaction on Information Theory 49(4): 1047–1051.Google Scholar
13.Orlitsky, A., Santhanam, N.P. & Zhang, J. (2004). Universal compression of memoryless sources over unknown alphabets. IEEE Transaction on Information Theory 50(7): 1469–1481.CrossRefGoogle Scholar
14.van den Berg, J. & Kesten, H. (1985). Inequalities with applications to percolation and reliability. Journal of Applied Probability 22(3): 556–569.Google Scholar
15.Wagner, A.B., Viswanath, P., & Kulkarni, S.R. (2011). Probability estimation in the rare-events regime. IEEE Transaction on Information Theory 57(6): 3207–3229.Google Scholar