Refine
Language
- English (5)
Keywords
- giant component (2)
- Stein’s method (1)
- colouring (1)
- complex networks (1)
- connected hypergraphs (1)
- intersection graphs (1)
- limit theorems (1)
- local limit theorems (1)
- random discrete structures (1)
- random graphs (1)
Project
- A5 (5)
Application Area
- A (5)
Random intersection graphs naturally exhibit a certain amount of transitivity and hence can
be used to model real--world networks. We study the evolution of the chromatic number
of a random intersection graph and show that, in a certain range of parameters,
these random graphs can be coloured optimally with high probability using different greedy
algorithms.
Experiments on real network data confirm the positive theoretical predictions and
suggest that heuristics for the clique and the chromatic number can work hand in hand
proving mutual optimality.
Let H_d(n, p) signify a random d-uniform hypergraph with n vertices in which each of the possible edges is present with probability p = p(n) independently, and let H_d(n,m) denote a uniformly distributed d-uniform hypergraph with n vertices and m edges. We derive local limit theorems for the joint distribution of the number of vertices and the number of edges in the largest component of H_d(n, p) and H_d(n,m). As an application, we obtain an asymptotic formula for the probability that H_d(n, p) is connected, and a corresponding formula for H_d(n,m). In addition, we infer a local limit theorem for the conditional distribution of the number of edges in H_d(n, p) given that H_d(n, p) is connected. While most prior work on this subject relies on techniques from enumerative combinatorics, we present a new, purely probabilistic approach.
We study the evolution of the size of the largest and the second largest
component in the random intersection graph model which is suited to re
ect
the transitivity (or clustering property) visible in real-world networks. We
show that certain random intersection graphs differ from Gn;p in that they
have only a polynomial jump in the evolution of the size of the largest
component. On the other hand the moment for the jump is still at the
point where the expected vertex degree becomes 1 which is similar to Gn;p.
We also describe a test of our result on a protein network.