Geodesic
Harmonic analysis of symmetric random graphs
Kybernetika, Tome 56 (2020) no. 6, pp. 1081-1089
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.14736/kyb-2020-6-1081
Classification : 43A35, 60B99
Keywords: characters; deFinetti's theorem; exchangeability; extreme point models; graph limits; graphons; positive definite functions; semigroups 
@article{10_14736_kyb_2020_6_1081,
     author = {Lauritzen, Steffen},
     title = {Harmonic analysis of symmetric random graphs},
     journal = {Kybernetika},
     pages = {1081--1089},
     year = {2020},
     volume = {56},
     number = {6},
     doi = {10.14736/kyb-2020-6-1081},
     mrnumber = {4199904},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2020-6-1081/}
}
TY  - JOUR
AU  - Lauritzen, Steffen
TI  - Harmonic analysis of symmetric random graphs
JO  - Kybernetika
PY  - 2020
SP  - 1081
EP  - 1089
VL  - 56
IS  - 6
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2020-6-1081/
DO  - 10.14736/kyb-2020-6-1081
LA  - en
ID  - 10_14736_kyb_2020_6_1081
ER  - 
%0 Journal Article
%A Lauritzen, Steffen
%T Harmonic analysis of symmetric random graphs
%J Kybernetika
%D 2020
%P 1081-1089
%V 56
%N 6
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2020-6-1081/
%R 10.14736/kyb-2020-6-1081
%G en
%F 10_14736_kyb_2020_6_1081
Lauritzen, Steffen. Harmonic analysis of symmetric random graphs. Kybernetika, Tome 56 (2020) no. 6, pp. 1081-1089. doi: 10.14736/kyb-2020-6-1081

[1] Aldous, D.: Representations for partially exchangeable random variables. J. Multivar. Anal. 11 (1981), 581-598. | DOI | MR

[2] Aldous, D.: 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 | MR

[3] Berg, C., Christensen, J. P. R., Ressel, P.: Positive definite functions on Abelian semigroups. Math. Ann. 259 (1976), 253-274. | DOI | MR

[4] Berg, C., Christensen, J. P. R., Ressel, P.: Harmonic Analysis on Semigroups. Springer-Verlag, New York 1984. | DOI | MR

[5] Borgs, C., Chayes, J., Lovász, L., Sós, V., Vesztergombi, K.: Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing. Adv. Math. 219 (2008), 1801-1851. | DOI | MR

[6] Diaconis, P., Freedman, D.: Finite exchangeable sequences. Ann. Probab. 8 (1980), 745-764. | DOI | MR

[7] Diaconis, P., Freedman, D.: On the statistics of vision: the Julesz conjecture. J. Math. Psychol. 24 (1981), 112-138. | DOI | MR

[8] Diaconis, P., Janson, S.: Graph limits and exchangeable random graphs. Rendiconti di Matematica, Serie VII 28 (2008), 33-61. | MR

[9] Drton, M., Richardson, T. S.: Binary models for marginal independence. J. Roy. Statist. Soc. Series B 70 (2008), 287-309. | DOI | MR

[10] Freedman, D.: A remark on the difference between sampling with and without replacement. J. Amer. Statist. Assoc. 72 (1977), 681. | DOI | MR

[11] Holland, P. W., Leinhardt, S.: An exponential family of probability distributions for directed graphs. J. Amer. Statist. Assoc. 76 (1981), 33-50. | DOI | MR

[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. | MR

[14] Lauritzen, S., Rinaldo, A., Sadeghi, K.: On exchangeability in network models. J. Algebr. Statist. 10 (2019), 85-114. | DOI | MR

[15] Lauritzen, S. L.: General exponential models for discrete observations. Scand. J. Statist. 2 (1975), 23-33. | MR

[16] Lauritzen, S. L.: Extremal Families and Systems of Sufficient Statistics. Springer-Verlag, Heidelberg 1988. | DOI | MR

[17] Lauritzen, S. L.: Exchangeable Rasch matrices. Rendiconti di Matematica, Serie VII 28 (2008), 83-95. | DOI | MR

[18] Lovász, L.: Large Networks and Graph Limits. Colloquium Publications, American Mathematical Society, Rhode Island 2012. | DOI | MR

[19] Lovász, L., Szegedy, B.: Limits of dense graph sequences. J. Combinat. Theory, Series B 96 (2006), 933-957. | DOI | MR

[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.: Bayesian models of graphs, arrays, and other exchangeable structures. IEEE Trans. Pattern Anal. Machine Intel. 37 (2015), 437-461. | DOI

[22] Ressel, P.: de Finetti-type theorems: An analytical approach. Ann. Probab. 13 (1985), 898-922. | DOI | MR

[23] Ressel, P.: Exchangeability and semigroups. Rendiconti di Matematica, Serie VII 28 (2008), 63-81. | MR

[24] Silverman, B. W.: Limit theorems for dissociated random variables. Adv. Appl. Probab. 8 (1976), 806-819. | DOI | MR

[25] Snijders, T. A. B., Pattison, P. E., Robins, G. L., Handcock, M. S.: New specifications for exponential random graph models. Sociolog. Methodology 36 (2006), 99-153. | DOI

Cité par Sources :