Large cliques in sparse random intersection graphs

zbMATH Open1361.05117arXiv1302.4627MaRDI QIDQ528977FDOQ528977

Authors: Mindaugas Bloznelis, Valentas Kurauskas 

Publication date: 18 May 2017

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1302.4627

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Large cliques in a power-law random graph
• Large independent sets in general random intersection graphs
• Degree and clustering coefficient in sparse random intersection graphs

zbMATH Keywords

clusteringgreedy algorithmcomplex networkcliquepower-lawrandom intersection graph

Mathematics Subject Classification ID

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)

Cites Work

• Statistical mechanics of complex networks
• Title not available (Why is that?)
• Collective dynamics of `small-world' networks
• On Random Intersection Graphs: The Subgraph Problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Erdős-Ko-Rado for random hypergraphs: asymptotics and stability
• Title not available (Why is that?)
• Poisson approximation of the number of cliques in random intersection graphs
• Coloring Random Intersection Graphs and Complex Networks
• Erdős-Ko-Rado in random hypergraphs
• Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints
• Assortativity and clustering of sparse random intersection graphs
• Degree and clustering coefficient in sparse random intersection graphs
• RANDOM INTERSECTION GRAPHS WITH TUNABLE DEGREE DISTRIBUTION AND CLUSTERING
• Degree distribution of a typical vertex in a general random intersection graph
• Large cliques in a power-law random graph
• Regularly Varying Sequences
• Number of cliques in random scale-free network ensembles
• On small subgraphs in a random intersection digraph
• On local weak limit and subgraph counts for sparse random graphs

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)