Large cliques in sparse random intersection graphs
From MaRDI portal
(Redirected from Publication:528977)
Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Density (toughness, etc.) (05C42)
Abstract: Given positive integers n and m, and a probability measure P on {0, 1, ..., m} the random intersection graph G(n,m,P) on vertex set V = {1,2, ..., n} and with attribute set W = {w_1, w_2, ..., w_m} is defined as follows. Let S_1, S_2, ..., S_n be independent random subsets of W such that for any v in V and any S subseteq W we have pr(S_v = S) = P(|S|) / �inom (m, |S|). The edge set of G(n,m,P) consists of those pairs {u,v} V for which S_u and S_v intersect. We study the asymptotic order of the clique number omega(G(n,m,P)) in random intersection graphs with bounded expected degrees. For instance, in the case m = Theta(n) we show that if the vertex degree distribution is power-law with exponent alpha in (1;2), then the maximum clique is of a polynomial size, while if the variance of the degrees is bounded, then the maximum clique has (ln n)/(ln ln n) (1 + o_P(1)) vertices whp. In each case there is a polynomial algorithm which finds a clique of size omega(G(n,m,P)) (1-o_P(1)).
Recommendations
Cites work
- scientific article; zbMATH DE number 3727274 (Why is no real title available?)
- scientific article; zbMATH DE number 1246230 (Why is no real title available?)
- scientific article; zbMATH DE number 1168330 (Why is no real title available?)
- scientific article; zbMATH DE number 1540669 (Why is no real title available?)
- Assortativity and clustering of sparse random intersection graphs
- Collective dynamics of `small-world' networks
- Coloring Random Intersection Graphs and Complex Networks
- Degree and clustering coefficient in sparse random intersection graphs
- Degree distribution of a typical vertex in a general random intersection graph
- Erdős-Ko-Rado for random hypergraphs: asymptotics and stability
- Erdős-Ko-Rado in random hypergraphs
- Large cliques in a power-law random graph
- Number of cliques in random scale-free network ensembles
- On Random Intersection Graphs: The Subgraph Problem
- On local weak limit and subgraph counts for sparse random graphs
- On small subgraphs in a random intersection digraph
- Poisson approximation of the number of cliques in random intersection graphs
- Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints
- RANDOM INTERSECTION GRAPHS WITH TUNABLE DEGREE DISTRIBUTION AND CLUSTERING
- Regularly Varying Sequences
- Statistical mechanics of complex networks
Cited in
(14)- The number of triangles in random intersection graphs
- On local weak limit and subgraph counts for sparse random graphs
- On the chromatic index of random uniform hypergraphs
- On CLIQUE Problem for Sparse Graphs of Large Dimension
- Clique and cycle frequencies in a sparse random graph model with overlapping communities
- Random subcube intersection graphs. I: Cliques and covering
- Finding cliques in social networks: a new distribution-free model
- Large independent sets in general random intersection graphs
- Phase transitions for detecting latent geometry in random graphs
- Large cliques in a power-law random graph
- Large cliques and independent sets all over the place
- On the kernel size of clique cover reductions for random intersection graphs
- Poisson approximation of the number of cliques in random intersection graphs
- A spectral algorithm for finding maximum cliques in dense random intersection graphs
This page was built for publication: Large cliques in sparse random intersection graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q528977)
