Questions tagged [random-graphs]
The random-graphs tag has no usage guidance.
28
questions
2
votes
0
answers
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 ...
4
votes
0
answers
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 ...
- 41
0
votes
1
answer
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) ...
- 183
0
votes
0
answers
31
views
Stochastic matching with fewer queries
Given a graph $G = (V,E)$ and a probability $p \in [0,1]$ with which each edge is sampled from the graph $G$. The goal of the stochastic matching problem with fewer queries is to find a subgraph $H \...
- 1
1
vote
1
answer
62
views
Probability of arising of simple graph in configuration model
I am studying a configuration model building $d$-regular graphs and reading the following article:
The expansion of random regular graphs by David Ellis.
I am stuck on the following step:
Each simple ...
- 158
2
votes
1
answer
359
views
Generating sparse connected Erdős–Rényi random graphs
Given a random graph $G(n, p)$, where $n$ is the number of nodes and $p$ is the probability of connecting any two edges, it is known that $t = \frac{\ln(n)}{n}$ is a threshold for the connectedness of ...
- 21
11
votes
0
answers
120
views
Min-eigenvalue bound for a random d-regular graph
I need help proving the following fact: Let $G$ be a random $d$-regular graph with adjacency matrix $A$. The smallest eigenvalue $\lambda_n$ of $A$ should satisfy $|\lambda_n| = o_d(d)$. (In ...
- 156
3
votes
1
answer
51
views
Efficient Algorithms for Complex Networks
Most standard works on random graphs focus on $G_{n,p}$ and random regular graphs. However, such models are far from a good abstraction to describe the types of networks that one typically encounters ...
- 339
4
votes
1
answer
57
views
Marginal Probability of Generating a Tree
Fix some finite graph $G = (V, E)$, and some vertex $x$.
Suppose I generate a random sub-tree of $G$ of size $N$, containing $x$, as follows:
Let $T_0 = \{ x \}$.
For $0 < n \leqslant N$
i. Let ...
- 143
3
votes
1
answer
59
views
Reference asking: phase transition in SAT
This is not a technical question, I hope this community has a room for such questions, but I will delete it in case this is inappropriate.
It has been experimentally observed (e.g. here) that when ...
- 33
3
votes
0
answers
54
views
Random linear arrangement of a tree with constrained edge lengths
Let $T$ be a tree with $V$ and edges $E$. Let a linear arrangement $\pi$ of $T$ be a bijective mapping from nodes to integers in the range $\{1, \dots, |V|\}$. You can think of $\pi$ as defining the ...
- 131
1
vote
1
answer
42
views
Singleton in a simple SBM
I can't work out the solution to the following exercise:
We have $2n$ vertices grouped in $2$ clusters of equal size. The probability of having an edge between $i$ and $j$ is $p$ if $i$ and $j$ are ...
- 37
2
votes
1
answer
2k
views
How to generate random adjacency matrix with given number of components in graph
I am building a graph package in C and a part of the work involves generating a random graph with a given number of components in the graph.
For example, if I wanted to generate a graph of 50 ...
1
vote
1
answer
70
views
Given a simple graph G, what's the quickest known way to sample one of its spanning trees at random?
Let's say I have a simple graph G with an edge set E, vertex set V, and at least 1 cycle.
We can determine the number of spanning trees in this graph by finding its graph Laplacian matrix, striking ...
2
votes
0
answers
127
views
Eigenvalues of an induced subgraph of a random graph
Suppose $G$ is a random graph on $n$ vertices where each edge appears with probability half. Suppose someone looks at the resulting graph and chooses an arbitrary subset $W$ of vertices of size $k>\...
- 464
2
votes
1
answer
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 ...
- 21
2
votes
1
answer
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$ ...
2
votes
1
answer
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 ...
- 145
2
votes
1
answer
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 ...
- 125
1
vote
0
answers
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 ...
2
votes
0
answers
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 ...
- 41
7
votes
2
answers
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 ...
- 339
6
votes
1
answer
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 ...
- 649
5
votes
2
answers
2k
views
Generation of random binary trees
Given n, I want to randomly generate a binary tree (unlabelled) that has n end nodes. Could someone kindly provide a reference containing an algorithm for doing that?
I attempted to do as follows: ...
- 515
9
votes
4
answers
1k
views
What is a good algorithm for generating random DFAs?
I am generating random DFAs to test a DFA reduction algorithm on them.
The algorithm that I'm using right now is as follows: for each state $q$, for each symbol in the alphabet $c$, add $\delta (q, c)...
- 665
2
votes
1
answer
90
views
Mean number of edges between two equal partitions
For a random undirected graph with $n$ nodes, where each node has $k$ incident edges ($nk/2$ edges in total), the vertex set is partitioned into two sets each having $n/2$ nodes.
What is the ...
- 129
3
votes
1
answer
1k
views
What is the probability of friendship conditioned on the number of mutual friends
Let Alice and Bob be two users chosen uniformly at random from a social network (e.g. Facebook). What is the probability that they are friends assuming that they share $k$ mutual friends?
I am ...
- 22.1k
13
votes
1
answer
2k
views
Number of clique in random graphs
There is a family of random graphs $G(n, p)$ with $n$ nodes (due to Gilbert). Each possible edge is independently inserted into $G(n, p)$ with probability $p$. Let $X_k$ be the number of cliques of ...
- 641