Dynamic random intersection graph: dynamic local convergence and giant structure
The authors study a model of dynamic random graphs (random graphs that evolve with time). Part of their motivation is to model real-life networks with ``local communities, i.e. which contain spots with more connections than the average (and thus, high clustering). It also generalises other random models with clusterings appearing in the literature.\N\NThe definition of the random model is inspired by that of a random intersection graph, as introduced in [\textit{K. B. Singer}, Random intersection graphs. Baltimore, MA: Johns Hopkins University (PhD Thesis) (1996)]. In that model, one first generates a random bipartite graph, with one side representing the vertices and the other part representing the communities. Then, one generates a graph by connecting two vertices if and only if they belong to the same community. The authors extend this basic model in multiple ways: by adding weights to the vertices, by allowing for different probabilities of including, or not, a certain community depending on those weights, and by adding dynamics to this process by allowing the communities to appear or disappear over time. This defines two closely related models: the dynamic version (which evolves with time) and the static version (which essentially corresponds to the typical behaviour of the dynamic model at stationarity). Then, the authors go on to prove various results about these two models, including local limits and the largest connected components in the static model; and local limits, limiting objects, degree distributions, giant components, and maximal group size in the dynamic model.\N\NThe dynamic model considered by the authors can be described as follows. The vertex set is \([n] = \{1, \dots, n \}\), and each vertex \(i\) has a (deterministic) weight \(w_i \ge 0\). Each set \(A \subseteq [n]\) of size at least \(2\) is called a group, and its status will alternate between `on' and `off' according to a continuous-time Markov process. The time each group spends in each state is distributed exponentially, with rates \(\lambda^A_{\text{ON}} = 1\) and \N\[ \N\lambda^A_{\text{OFF}} = f(|A|) \frac{\prod_{i \in A} w_i }{(\sum_{i \in A} w_i)^{|A|-1}}, \N\] \Nwhere \(f(\cdot)\) is a function of the group size, and whose choice gives some flexibility to the model. Then, the graph on \([n]\) is defined by including a clique in each group whose status is `on'. The authors assume some `regularity' properties for the weights and the function \(f\), which allows for non-triviality, sparseness, and well-behavedness of the model which allows for its study.
- A critical point for random graphs with a given degree sequence
- A new approach to the giant component problem
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- A survey of dynamical percolation
- An old approach to the giant component problem
- Assortativity and clustering of sparse random intersection graphs
- Asymptotic equivalence and contiguity of some random graphs
- Community structure in social and biological networks
- Complex graphs and networks
- Component evolution in general random intersection graphs
- Connected components in random graphs with given expected degree sequences
- Connectivity of the uniform random intersection graph
- Contagions in random networks with overlapping communities
- Cutoff for random walk on dynamical Erdős-Rényi graph
- Degree and clustering coefficient in sparse random intersection graphs
- Degree distribution of an inhomogeneous random intersection graph
- Degree-degree distribution in a power law random intersection graph with clustering
- Diameter, connectivity, and phase transition of the uniform random intersection graph
- Dynamical percolation
- Emergence of Scaling in Random Networks
- Epidemics on random intersection graphs
- Generating simple random graphs with prescribed degree distribution
- scientific article; zbMATH DE number 1713116 (Why is no real title available?)
- scientific article; zbMATH DE number 3168330 (Why is no real title available?)
- scientific article; zbMATH DE number 1354815 (Why is no real title available?)
- scientific article; zbMATH DE number 2042286 (Why is no real title available?)
- Limit laws for self-loops and multiple edges in the configuration model
- Linking the mixing times of random walks on static and dynamic random graphs
- Networks. An introduction.
- ON A CLASS OF SKEW DISTRIBUTION FUNCTIONS
- On a conditionally Poissonian graph process
- On analytical approaches to epidemics on networks
- On Random Intersection Graphs: The Subgraph Problem
- Phase transition in random intersection graphs with communities
- Random Graphs and Complex Networks
- Random intersection graphs whenm=?(n): An equivalence theorem relating the evolution of theG(n,m,p) andG(n,p) models
- Random intersection graphs with communities
- RANDOM INTERSECTION GRAPHS WITH TUNABLE DEGREE DISTRIBUTION AND CLUSTERING
- Random walks on dynamic configuration models: a trichotomy
- Recurrence of distributional limits of finite planar graphs
- Susceptible-infected-removed epidemic models with dynamic partnerships
- The phase transition in inhomogeneous random graphs
- The Size of the Giant Component of a Random Graph with a Given Degree Sequence
- The Volume of the Giant Component of a Random Graph with Given Expected Degrees
This page was built for publication: Dynamic random intersection graph: dynamic local convergence and giant structure
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7027475)
