Harmonic analysis of symmetric random graphs

Steffen Lauritzen

Kybernetika (2020)

  • Volume: 56, Issue: 6, page 1081-1089
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Lauritzen, Steffen. "Harmonic analysis of symmetric random graphs." Kybernetika 56.6 (2020): 1081-1089. <http://eudml.org/doc/296988>.

@article{Lauritzen2020,
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.},
author = {Lauritzen, Steffen},
journal = {Kybernetika},
keywords = {characters; deFinetti's theorem; exchangeability; extreme point models; graph limits; graphons; positive definite functions; semigroups},
language = {eng},
number = {6},
pages = {1081-1089},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Harmonic analysis of symmetric random graphs},
url = {http://eudml.org/doc/296988},
volume = {56},
year = {2020},
}

TY - JOUR
AU - Lauritzen, Steffen
TI - Harmonic analysis of symmetric random graphs
JO - Kybernetika
PY - 2020
PB - Institute of Information Theory and Automation AS CR
VL - 56
IS - 6
SP - 1081
EP - 1089
AB - 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.
LA - eng
KW - characters; deFinetti's theorem; exchangeability; extreme point models; graph limits; graphons; positive definite functions; semigroups
UR - http://eudml.org/doc/296988
ER -

References

top
  1. Aldous, D., 10.1016/0047-259x(81)90099-3, J. Multivar. Anal. 11 (1981), 581-598. MR0637937DOI10.1016/0047-259x(81)90099-3
  2. Aldous, D., 10.1007/bfb0099421, In: École d'Été de Probabilités de Saint-Flour XIII - 1983 (P. Hennequin, ed.), Springer-Verlag, Heidelberg 1985, pp. 1-198. MR0883646DOI10.1007/bfb0099421
  3. Berg, C., Christensen, J. P. R., Ressel, P., 10.1007/bf01360957, Math. Ann. 259 (1976), 253-274. MR0420150DOI10.1007/bf01360957
  4. Berg, C., Christensen, J. P. R., Ressel, P., 10.1007/978-1-4612-1128-0, Springer-Verlag, New York 1984. MR0747302DOI10.1007/978-1-4612-1128-0
  5. Borgs, C., Chayes, J., Lovász, L., Sós, V., Vesztergombi, K., 10.1016/j.aim.2008.07.008, Adv. Math. 219 (2008), 1801-1851. MR2455626DOI10.1016/j.aim.2008.07.008
  6. Diaconis, P., Freedman, D., 10.1214/aop/1176994663, Ann. Probab. 8 (1980), 745-764. MR0577313DOI10.1214/aop/1176994663
  7. Diaconis, P., Freedman, D., 10.1016/0022-2496(81)90039-0, J. Math. Psychol. 24 (1981), 112-138. MR0640207DOI10.1016/0022-2496(81)90039-0
  8. Diaconis, P., Janson, S., Graph limits and exchangeable random graphs., Rendiconti di Matematica, Serie VII 28 (2008), 33-61. MR2463439
  9. Drton, M., Richardson, T. S., 10.1111/j.1467-9868.2007.00636.x, J. Roy. Statist. Soc. Series B 70 (2008), 287-309. MR2424754DOI10.1111/j.1467-9868.2007.00636.x
  10. Freedman, D., 10.1080/01621459.1977.10480637, J. Amer. Statist. Assoc. 72 (1977), 681. MR0445667DOI10.1080/01621459.1977.10480637
  11. Holland, P. W., Leinhardt, S., 10.1080/01621459.1981.10477598, J. Amer. Statist. Assoc. 76 (1981), 33-50. MR0608176DOI10.1080/01621459.1981.10477598
  12. Hoover, D. N., Relations on probability spaces and arrays of random variables., Preprint, Institute of Advanced Study, Princeton 1979. 
  13. Lauritzen, S., Rinaldo, A., Sadeghi, K., Random networks, graphical models, and exchangeability., J. Roy. Statist. Soc., Series B, 80 (2018), 481-508. MR3798875
  14. Lauritzen, S., Rinaldo, A., Sadeghi, K., 10.18409/jas.v10i1.73, J. Algebr. Statist. 10 (2019), 85-114. MR3947125DOI10.18409/jas.v10i1.73
  15. Lauritzen, S. L., General exponential models for discrete observations., Scand. J. Statist. 2 (1975), 23-33. MR0378163
  16. Lauritzen, S. L., 10.1007/978-1-4612-1023-8, Springer-Verlag, Heidelberg 1988. MR0971253DOI10.1007/978-1-4612-1023-8
  17. Lauritzen, S. L., 10.1007/bf02419265, Rendiconti di Matematica, Serie VII 28 (2008), 83-95. MR2463441DOI10.1007/bf02419265
  18. Lovász, L., 10.1090/coll/060, Colloquium Publications, American Mathematical Society, Rhode Island 2012. MR3012035DOI10.1090/coll/060
  19. Lovász, L., Szegedy, B., 10.1016/j.jctb.2006.05.002, J. Combinat. Theory, Series B 96 (2006), 933-957. MR2274085DOI10.1016/j.jctb.2006.05.002
  20. Matúš, F., Finite Partially Exchangeable Arrays., Technical Report 1856, Institute of Information Theory and Automation, Academy of Sciences of the Czech Republic, Prague 1995. 
  21. Orbantz, P., Roy, D. M., 10.1109/tpami.2014.2334607, IEEE Trans. Pattern Anal. Machine Intel. 37 (2015), 437-461. DOI10.1109/tpami.2014.2334607
  22. Ressel, P., 10.1214/aop/1176992913, Ann. Probab. 13 (1985), 898-922. MR0799427DOI10.1214/aop/1176992913
  23. Ressel, P., Exchangeability and semigroups., Rendiconti di Matematica, Serie VII 28 (2008), 63-81. MR2463440
  24. Silverman, B. W., 10.1017/s0001867800042932, Adv. Appl. Probab. 8 (1976), 806-819. MR0431348DOI10.1017/s0001867800042932
  25. Snijders, T. A. B., Pattison, P. E., Robins, G. L., Handcock, M. S., 10.1111/j.1467-9531.2006.00176.x, Sociolog. Methodology 36 (2006), 99-153. DOI10.1111/j.1467-9531.2006.00176.x

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.