Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-02T20:38:00.028Z Has data issue: false hasContentIssue false
  • English
  • Français

Asymptotic Poisson distributions with applications to statistical analysis of graphs

Published online by Cambridge University Press:  01 July 2016

Krzysztof Nowicki
Krzysztof Nowicki*
Affiliation:
University of Lund
*
∗Postal address: Department of Mathematical Statistics, University of Lund, Box 118, S-22100 Lund, Sweden.
Get access Rights & Permissions [Opens in a new window]

Abstract

Various types of graph statistics for graphs and digraphs are presented as numerators of incomplete U-statistics, with symmetric and asymmetric kernels, respectively. Thus, asymptotic Poisson limits of these statistics are provided by using limit theorems for the sums of dissociated random variables. Several applications to statistical analysis of graphs are given.

Keywords

RANDOM GRAPHS AND DIGRAPHSSUBGRAPH COUNTSINCOMPLETE U-STATISTICSDISSOCIATED RANDOM VARIABLESPOISSON LIMIT THEOREMS
Type
Research Article
Information
Advances in Applied Probability , Volume 20 , Issue 2 , June 1988 , pp. 315 - 330
Copyright
Copyright © Applied Probability Trust 1988 

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

Footnotes

Partial support for this paper was given by the Swedish Council for Research in the Humanities and Social Sciences under contract No. F46/84.

References

Barbour, A. D. and Eagleson, G. K. (1984) Poisson convergence for dissociated statistics. J. R. Statist. Soc. B 46, 397–402.Google Scholar
Barlow, R. E. and Proschan, F. (1965) Mathematical Theory of Reliability. Wiley, New York.Google Scholar
Barlow, R. E. and Proschan, F. (1975) Statistical Theory of Reliability and Life Testing. Holt, New York.Google Scholar
Bollobàs, B. (1981) Threshold functions for small subgraphs. Math. Proc. Camb. Phil. Soc. 90, 197–206.Google Scholar
Erdós, P. and Renyi, A. (1959) On random graphs 1. Publ. Math. Debrecen 6, 290–297.CrossRefGoogle Scholar
Erdós, P. and Renyi, A. (1960) On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5, 17–61.Google Scholar
Fienberg, S., Meyer, M. and Wasserman, S. (1985) Statistical analysis of multiple sociometric relations. J. Amer. Statist. Assoc. 80, 51–67.CrossRefGoogle Scholar
Frank, O. (1980) Transitivity in stochastic graphs and digraphs. J. Math. Sociol. 7, 199–213.CrossRefGoogle Scholar
Frank, O. and Gaul, W. (1982) On reliability in stochastic graphs. Networks 12, 119–126.CrossRefGoogle Scholar
Frank, O. and Harary, F. (1982) Cluster inference by using transitivity indices in empirical graphs. J. Amer. Statist. Assoc. 77, 835–840.Google Scholar
Frank, O. and Strauss, D. (1986) Markov graphs. J. Amer. Statist. Assoc. 81, 832–842.Google Scholar
Gilbert, E. N. (1959) Random graphs. Ann. Math. Statist. 30, 1141–1144.CrossRefGoogle Scholar
Harary, F. and Kommel, H. (1979) Matrix measures for transitivity and balance. J. Math. Sociol. 6, 199–210.Google Scholar
Hoeffding, W. (1948) A class of statistics with asymptotically normal distribution. Ann. Math. Statist. 19, 293–325.Google Scholar
Holland, P. and Leinhardt, S. (1971) Transitivity in structural models of small groups. Comparative Group Studies 2, 107–124.Google Scholar
Holland, P. and Leinhardt, S., (Eds) (1979) Perspectives on Social Network Research. Academic Press, New York.Google Scholar
Holland, P. and Leinhardt, S. (1981) An exponential family of probability distributions for directed graphs. J. Amer. Statist. Assoc. 76, 33–51.Google Scholar
Karonski, M. (1984) Balanced Subgraphs of Large Random Graphs. Uniwersytet im. Adama Mickiewicza w Poznaniu, Seria Matematyka nr. 7.Google Scholar
Karonski, M. and Rucinski, A. (1983) On the number of strictly balanced subgraphs of a random graph. Graph Theory, Lagów 1981. Lectures Notes in Mathematics 1018, Springer-Verlag, 79–83.Google Scholar
Kendall, M. and Babington Smith, B. (1940) On the method of paired comparisons. Biometrika 31, 324–345.Google Scholar
Knoke, D. and Kuklinski, J. H. (1982) Network Analysis. Sage Publications, Beverly Hills.Google Scholar
Moon, J. W. (1968) Topics in Tournaments. Holt, New York.Google Scholar
Moore, E. F. and Shannon, C. E. (1956) Reliable circuits using reliable relays. J. Franklin Inst. 262, 191–208; 281-297.CrossRefGoogle Scholar
Moran, P. A. (1947) On the method of paired comparisons. Biometrika 34, 363–365.Google Scholar
Nowicki, K. (1985) Asymptotic normality of graph statistics. J. Statist. Planning Inf. To appear.Google Scholar
Nowicki, K. (1986) Asymptotic normality of triad counts for directed graphs. University of Lund, Stat. Res. Rep. 1986:7, 1–17.Google Scholar
Silverman, B. and Brown, T. (1978) Short distances, flat triangles and Poisson limit. J. Appl. Prob. 15, 815–825.CrossRefGoogle Scholar