Is there any "famous" random graph model in which the probability of at least one isolated clique forming is monotonic in the parameters?
For instance, are any results known in this matter for the random graph model of Newman, Mark EJ. "Random graphs with clustering." Physical review letters 103.5 (2009): 058701 ?
Notes
- By isolated clique, I mean a clique for which no node in the clique is connected to any node outside the clique.
- Ideally, I am looking for models of directed graphs, in which I view a clique as a set of nodes $S$ such that for every $i,j \in S$, both link $ij$ and link $ji$ have formed. But results for models of undirected graphs are also welcome.
- I know it's not clear what a "famous" random graph model is. If you want something more precise, you can take it to mean " a random graph model mentioned in Random Graphs by Bolloxes (or any other textbook)".But I guess what I really mean here is I am not interested in simple examples of the type "for all $n$, the probability is 1 in the random graph model $G(n)$ which assigns equal probability to all graphs with isolated cliques, and zero to others".)
===================================
To make things more concrete:
The example I have in mind is one in which nodes are agents who have to form teams. The set of agents $j$ an agent $i$ "points to" (i.e. the set of $j$ for which $ij = 1$) represents $i$'s favorite team. In this context, the fact that agents in $T$ form an isolated clique means that everyone in $T$ agrees that $T$ is their best possible team.
In this kind of settings, we could expect a fair amount of clustering on average, and it seems reasonable to hope that isolated cliques will emerge from time to time.
The question is : is there a "reasonable" random graph model for these kinds of situations in which the probability of an isolated clique forming is increasing in the parameters?
This is the example I have in mind, but any answer to the more general question above is welcome.
I don't think you'll find any well-established model of random graphs that suits your needs. However, if you define a process that make sense regarding the application you have in mind, it is a perfectly reasonable model of random graphs (papers related to social sciences abound in specific models).
Sparse graphs with clustering are particularly unnatural in random graphs, as the more 'random' the model is, the less probable it is that cliques are formed. Indeed, when there are $\Theta(n)$ edges independently distributed, the graph is asymptotically tree-like, and this remains true if you fix the degree sequence for example. In the existing models where you add cliques [0][1] (in a maybe artificial manner), the probability to find such cliques to be isolated is going to be very small, since one of the goals in modeling 'small-worlds' is to minimize distances between vertices.
On the other hand, if you graph is likely to form cliques, it is likely to have a high edge density, and thus the probability to have an isolated clique becomes vanishingly small.
Random graph models are hard to analyze, so there's the models of theoretical study are generally not the same as the ones used for social research or applications. In your case, you are probably better off devising a model suiting your problem.
You may find something that works well in the setting of a 'random geometric graph' setting, where you have vertices in a space (not necessarily homogeneously distributed), and the probability to link them is related to their distance. The space can represent say the opinion of vertices on a subject, and so the more they agree and the more they are likely to be linked. The reference on random geometric graphs is Penrose's book [2].
[0] Janson - Sparse random graphs with clustering
[1] Guillaume, Latapy - Bipartite graphs as models of complex networks
[2] Mathew Penrose - Random Geometric Graphs