Kybernetika 56 no. 6, 1081-1089, 2020

Harmonic analysis of symmetric random graphs

Steffen LauritzenDOI: 10.14736/kyb-2020-6-1081

Abstract:

This note attempts to understand graph limits as defined by Lovasz and Szegedy in terms of harmonic analysis on semigroups. This is done by representing probability distributions of random exchangeable graphs as mixtures of characters on the semigroup of unlabeled graphs with node-disjoint union, thereby providing an alternative derivation of de Finetti's theorem for random exchangeable graphs.

Keywords:

exchangeability, characters, deFinetti's theorem, extreme point models, graph limits, graphons, positive definite functions, semigroups

Classification:

60B99, 43A35

paper.pdf

References:

  1. D. Aldous: Representations for partially exchangeable random variables. J. Multivar. Anal. 11 (1981), 581-598.   DOI:10.1016/0047-259x(81)90099-3
  2. D. Aldous: Exchangeability and related topics. In: École d'Été de Probabilités de Saint-Flour XIII -- 1983 (P. Hennequin, ed.), Springer-Verlag, Heidelberg 1985, pp. 1-198.   DOI:10.1007/bfb0099421
  3. C. Berg, J. P. R. Christensen and P. Ressel: Positive definite functions on Abelian semigroups. Math. Ann. 259 (1976), 253-274.   DOI:10.1007/bf01360957
  4. C. Berg, J. P. R. Christensen and P. Ressel: Harmonic Analysis on Semigroups. Springer-Verlag, New York 1984.   DOI:10.1007/978-1-4612-1128-0
  5. C. Borgs, J. Chayes, L. Lovász, V. Sós and K. Vesztergombi: Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing. Adv. Math. 219 (2008), 1801-1851.   DOI:10.1016/j.aim.2008.07.008
  6. P. Diaconis and D. Freedman: Finite exchangeable sequences. Ann. Probab. 8 (1980), 745-764.   DOI:10.1214/aop/1176994663
  7. P. Diaconis and D. Freedman: On the statistics of vision: the Julesz conjecture. J. Math. Psychol. 24 (1981), 112-138.   DOI:10.1016/0022-2496(81)90039-0
  8. P. Diaconis and S. Janson: Graph limits and exchangeable random graphs. Rendiconti di Matematica, Serie VII 28 (2008), 33-61.   CrossRef
  9. M. Drton and T. S. Richardson: Binary models for marginal independence. J. Roy. Statist. Soc. Series B 70 (2008), 287-309.   DOI:10.1111/j.1467-9868.2007.00636.x
  10. D. Freedman: A remark on the difference between sampling with and without replacement. J. Amer. Statist. Assoc. 72 (1977), 681.   DOI:10.1080/01621459.1977.10480637
  11. P. W. Holland and S. Leinhardt: An exponential family of probability distributions for directed graphs. J. Amer. Statist. Assoc. 76 (1981), 33-50.   DOI:10.1080/01621459.1981.10477598
  12. D. N. Hoover: Relations on probability spaces and arrays of random variables. Preprint, Institute of Advanced Study, Princeton 1979.   CrossRef
  13. S. Lauritzen, A. Rinaldo and K. Sadeghi: Random networks, graphical models, and exchangeability. J. Roy. Statist. Soc., Series B, 80 (2018), 481-508.   CrossRef
  14. S. Lauritzen, A. Rinaldo and K. Sadeghi: On exchangeability in network models. J. Algebr. Statist. 10 (2019), 85-114.   DOI:10.18409/jas.v10i1.73
  15. S. L. Lauritzen: General exponential models for discrete observations. Scand. J. Statist. 2 (1975), 23-33.   CrossRef
  16. S. L. Lauritzen: Extremal Families and Systems of Sufficient Statistics. Springer-Verlag, Heidelberg 1988.   DOI:10.1007/978-1-4612-1023-8
  17. S. L. Lauritzen: Exchangeable Rasch matrices. Rendiconti di Matematica, Serie VII 28 (2008), 83-95.   DOI:10.1007/bf02419265
  18. L. Lovász: Large Networks and Graph Limits. Colloquium Publications, American Mathematical Society, Rhode Island 2012.   DOI:10.1090/coll/060
  19. L. Lovász and B. Szegedy: Limits of dense graph sequences. J. Combinat. Theory, Series B 96 (2006), 933-957.   DOI:10.1016/j.jctb.2006.05.002
  20. F. Matúš: Finite Partially Exchangeable Arrays. Technical Report 1856, Institute of Information Theory and Automation, Academy of Sciences of the Czech Republic, Prague 1995.   CrossRef
  21. P. Orbantz and D. M. Roy: Bayesian models of graphs, arrays, and other exchangeable structures. IEEE Trans. Pattern Anal. Machine Intel. 37 (2015), 437-461.   DOI:10.1109/tpami.2014.2334607
  22. P. Ressel: de Finetti-type theorems: An analytical approach. Ann. Probab. 13 (1985), 898-922.   CrossRef
  23. P. Ressel: Exchangeability and semigroups. Rendiconti di Matematica, Serie VII 28 (2008), 63-81.   CrossRef
  24. B. W. Silverman: Limit theorems for dissociated random variables. Adv. Appl. Probab. 8 (1976), 806-819.   DOI:10.1017/s0001867800042932
  25. T. A. B. Snijders, P. E. Pattison, G. L. Robins and M. S. Handcock: New specifications for exponential random graph models. Sociolog. Methodology { \mi 36} (2006), 99-153.   CrossRef