Questions tagged [random-graphs]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4 votes
0 answers
66 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 ...
user avatar
  • 41
0 votes
1 answer
45 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) ...
user avatar
  • 171
0 votes
0 answers
29 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 \...
user avatar
1 vote
1 answer
30 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 ...
user avatar
2 votes
1 answer
190 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 ...
user avatar
  • 21
11 votes
0 answers
112 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 ...
user avatar
  • 156
3 votes
1 answer
50 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 ...
user avatar
  • 329
4 votes
1 answer
54 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 ...
user avatar
  • 143
3 votes
1 answer
56 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 ...
user avatar
  • 33
3 votes
0 answers
49 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 ...
user avatar
1 vote
1 answer
38 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 ...
user avatar
  • 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 ...
user avatar
1 vote
1 answer
68 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 ...
user avatar
2 votes
0 answers
115 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>\...
user avatar
  • 444
2 votes
1 answer
646 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 ...
user avatar
2 votes
1 answer
157 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$ ...
user avatar
2 votes
1 answer
194 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 ...
user avatar
2 votes
1 answer
584 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 ...
user avatar
  • 125
1 vote
0 answers
81 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 ...
user avatar
2 votes
0 answers
282 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 ...
user avatar
7 votes
2 answers
211 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 ...
user avatar
  • 329
6 votes
1 answer
662 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 ...
user avatar
5 votes
2 answers
1k 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: ...
user avatar
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)...
user avatar
  • 655
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 ...
user avatar
  • 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 ...
user avatar
  • 21.6k
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 ...
user avatar