# Questions tagged [random-graphs]

The tag has no usage guidance.

28 questions
Filter by
Sorted by
Tagged with
74 views

### Distribution of $k$-matchings in a random graph

Take the Erdos-Renyi random graph $G(n,p)$, i.e. the random graph with $n$ vertices and where each possible edge has an independent probability of $p$ of being present. Recall that a $k$-matching is a ...
71 views

### Generating graphs with partially overlapping cliques

Currently, I am working on a research project where I will utilise reinforcement learning for the diversified top-$k$ clique search problem. To train the reinforcement learning algorithm, I need to ...
64 views

### Expected behavior in the min max random assignment problem

Consider the standard assignment problem: $n$ people are assigned to n jobs (one person to one job) so to minimize the sum of costs. When the costs are generated randomly (using the exponential (1) ...
31 views

751 views

### Probability of k-clique in a random graph

I need to find the order of the minimum k = k(n) such that the probability of having at least 1 k-clique in a random graph $G(n, \frac{1}{2}$) is $\mathcal{O}(\frac{1}{n})$. $X_k$ is the random ...
173 views

### Fitness model for scale free networks

In order to generate scale-free networks, we can use this algorithm, derived from Barabási–Albert model: 1) we assign every node a "weight" $\theta_i$ (or two in the direct case). 2) we place $m$ ...
236 views

### How many edges before a random graph is connected?

Let $G$ be a undirected graph with $n$ vertices and no edges, and let $f(k)$ be the probability that if we add $k$ edges randomly to $G$ that $G$ will be connected. How would one determine $f(k)$ for ...
656 views

### Expected weight of euclidean minimum spanning tree on a unit square

Suppose I randomly generate $n$ points from the unit square $[0,1]^2$, form a complete graph in which the weight of each edge is just the Euclidean distance between its endpoints, and compute the ...
1 vote
92 views

### probability that the vertex set {1,...,k} is component of random graph

Consider a graph with vertices 1,...,n and suppose that each of the $\binom{n}{2}$pairs of vertices is, independently, an edge of this graph with probability p.Let $P_n$ denote the probability that ...
310 views

### Complexity class of maximum flow problem with random arc capacity

Given a graph $G=(N,E)$ with a special source node $s$ and sink node $t$. There is a subset of arcs $E^* \subset E$ that has the capacity drawn from a probability distribution $F$ independently. Then ...
217 views

### Has this model of random directed graphs been studied?

Youtube recently added a feature called autoplay, where each clip is assigned a (presumably related) clip that follows it. This, in effect, defines a directed graph on the set of youtube clips, where ...
735 views

### Expected number of maximal cliques in $G(n,p)$

The $G(n,p)$ random graph model creates graphs with $n$ vertices and each possible edge exists independently with probability $p\in (0,1)$. Much is known about the (expected) size of a largest ...