Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
characters; deFinetti's theorem; exchangeability; extreme point models; graph limits; graphons; positive definite functions; semigroups
characters; deFinetti's theorem; exchangeability; extreme point models; graph limits; graphons; positive definite functions; semigroups
Summary:
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.
References:
[1] Aldous, D.: Representations for partially exchangeable random variables. J. Multivar. Anal. 11 (1981), 581-598. DOI 10.1016/0047-259x(81)90099-3 | MR 0637937
[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 10.1007/bfb0099421 | MR 0883646
[3] Berg, C., Christensen, J. P. R., Ressel, P.: Positive definite functions on Abelian semigroups. Math. Ann. 259 (1976), 253-274. DOI 10.1007/bf01360957 | MR 0420150
[4] Berg, C., Christensen, J. P. R., Ressel, P.: Harmonic Analysis on Semigroups. Springer-Verlag, New York 1984. DOI 10.1007/978-1-4612-1128-0 | MR 0747302
[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 10.1016/j.aim.2008.07.008 | MR 2455626
[6] Diaconis, P., Freedman, D.: Finite exchangeable sequences. Ann. Probab. 8 (1980), 745-764. DOI 10.1214/aop/1176994663 | MR 0577313
[7] Diaconis, P., Freedman, D.: On the statistics of vision: the Julesz conjecture. J. Math. Psychol. 24 (1981), 112-138. DOI 10.1016/0022-2496(81)90039-0 | MR 0640207
[8] Diaconis, P., Janson, S.: Graph limits and exchangeable random graphs. Rendiconti di Matematica, Serie VII 28 (2008), 33-61. MR 2463439
[9] Drton, M., Richardson, T. S.: Binary models for marginal independence. J. Roy. Statist. Soc. Series B 70 (2008), 287-309. DOI 10.1111/j.1467-9868.2007.00636.x | MR 2424754
[10] Freedman, D.: A remark on the difference between sampling with and without replacement. J. Amer. Statist. Assoc. 72 (1977), 681. DOI 10.1080/01621459.1977.10480637 | MR 0445667
[11] Holland, P. W., Leinhardt, S.: An exponential family of probability distributions for directed graphs. J. Amer. Statist. Assoc. 76 (1981), 33-50. DOI 10.1080/01621459.1981.10477598 | MR 0608176
[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 3798875
[14] Lauritzen, S., Rinaldo, A., Sadeghi, K.: On exchangeability in network models. J. Algebr. Statist. 10 (2019), 85-114. DOI 10.18409/jas.v10i1.73 | MR 3947125
[15] Lauritzen, S. L.: General exponential models for discrete observations. Scand. J. Statist. 2 (1975), 23-33. MR 0378163
[16] Lauritzen, S. L.: Extremal Families and Systems of Sufficient Statistics. Springer-Verlag, Heidelberg 1988. DOI 10.1007/978-1-4612-1023-8 | MR 0971253
[17] Lauritzen, S. L.: Exchangeable Rasch matrices. Rendiconti di Matematica, Serie VII 28 (2008), 83-95. DOI 10.1007/bf02419265 | MR 2463441
[18] Lovász, L.: Large Networks and Graph Limits. Colloquium Publications, American Mathematical Society, Rhode Island 2012. DOI 10.1090/coll/060 | MR 3012035
[19] Lovász, L., Szegedy, B.: Limits of dense graph sequences. J. Combinat. Theory, Series B 96 (2006), 933-957. DOI 10.1016/j.jctb.2006.05.002 | MR 2274085
[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 10.1109/tpami.2014.2334607
[22] Ressel, P.: de Finetti-type theorems: An analytical approach. Ann. Probab. 13 (1985), 898-922. DOI 10.1214/aop/1176992913 | MR 0799427
[23] Ressel, P.: Exchangeability and semigroups. Rendiconti di Matematica, Serie VII 28 (2008), 63-81. MR 2463440
[24] Silverman, B. W.: Limit theorems for dissociated random variables. Adv. Appl. Probab. 8 (1976), 806-819. DOI 10.1017/s0001867800042932 | MR 0431348
[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 10.1111/j.1467-9531.2006.00176.x
Search
Partner of
