Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-08T22:16:58.068Z Has data issue: false hasContentIssue false
  • English
  • Français

The Vertex Degree Distribution of Passive Random Intersection Graph Models

Published online by Cambridge University Press:  01 July 2008

JERZY JAWORSKI  and
DUDLEY STARK
JERZY JAWORSKI
Affiliation:
Faculty of Mathematics and Computer Science, Adam Mickiewicz University, ul. Umultowska 87, 61-614 Poznań, Poland (e-mail: jaworski@amu.edu.pl)
DUDLEY STARK
Affiliation:
School of Mathematical Sciences, Queen Mary, University of London, London E1 4NS, UK (e-mail: D.S.Stark@maths.qmul.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In a random passive intersection graph model the edges of the graph are decided by taking the union of a fixed number of cliques of random size. We give conditions for a random passive intersection graph model to have a limiting vertex degree distribution, in particular to have a Poisson limiting vertex degree distribution. We give related conditions which, in addition to implying a limiting vertex degree distribution, imply convergence of expectation.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 17 , Issue 4 , July 2008 , pp. 549 - 558
Copyright
Copyright © Cambridge University Press 2008

References

[1]Fill, J. A., Scheinerman, E. R. and Singer-Cohen, K. B. (2000) Random intersection graphs when m = ω(n): An equivalence theorem relating the evolution of the G(n,m,p) and G(n,p) models. Random Struct. Alg. 16 156–176.3.0.CO;2-H>CrossRefGoogle Scholar
[2]Godehardt, E. and Jaworski, J. (2002) Two models of random intersection graphs for classification. In Exploratory Data Analysis in Empirical Research: Proc. 25th Annual Conference of the Gesellschaft für Klassifikation e.V., University of Munich, March 14–16, 2001 (Schwaiger, M. and Opitz, O., eds), Springer, pp. 67–81.Google Scholar
[3]Jaworski, J., Karoński, M. and Stark, D. (2006) The degree of a typical vertex in generalized random intersection graph models. Discrete Math. 306/18 2152–2165.CrossRefGoogle Scholar
[4]Karoński, M., Scheinerman, E. R. and Singer-Cohen, K. B. (1999) On random intersection graphs: The subgraph problem. Combin. Probab. Comput. 8 131–159.CrossRefGoogle Scholar
[5]Royden, H. L. (1988) Real Analysis, 3rd edn, Prentice-Hall.Google Scholar
[6]Singer, K. B. (1995) Random intersection graphs. Dissertation, Johns Hopkins University.Google Scholar
[7]Stark, D. (2004) The vertex degree distribution of random intersection graphs. Random Struct. Alg. 24 249–258.CrossRefGoogle Scholar