research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:
TitleThe Second Eigenvalue of Random Walks on Symmetric Random Intersection Graphs
Bibtex cite IDRACTI-RU1-2007-15
Booktitle International Conference on Algebraic Informatics (CAI 2007)
Year published 2007
Month May
Volume 4728/2007
Pages 236-246
Location Thessaloniki, Greece
DOI 10.1007/978-3-540-75414-5
In this paper we examine spectral properties of random intersection graphs when the number of vertices is equal to the number of labels. We call this class symmetric random intersection graphs. We examine symmetric random intersection graphs when the probability that a vertex selects a label is close to the connectivity threshold $\tau_c$. In particular, we examine the size of the second eigenvalue of the transition matrix corresponding to the Markov Chain that describes a random walk on an instance of the symmetric random intersection graph $G_n, n, p$. We show that with high probability the second eigenvalue is upper bounded by some constant $\zeta < 1$.
Nikoletseas, Sotiris
Raptopoulos, Christoforos
Spirakis, Paul
paper24cr.pdf (main file)
Short description of problem, previous work and result
Publication ID21