Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-08T04:55:47.806Z 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: [email protected])
DUDLEY STARK
Affiliation:
School of Mathematical Sciences, Queen Mary, University of London, London E1 4NS, UK (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

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

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

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