Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [random-graphs]

A random graph is a graph - a set of vertices and edges - that is chosen according to some probability distribution. In the most common model, $G_{n, p}$, a graph has $n$ vertices, and edges are present independently with probability $p$. Use (graphing-functions) instead if your question is about graphing or plotting functions.

2
votes
1answer
21 views

Distribution of $(\langle X_i,X_j\rangle)_{i,j=1}^n$ for $X_k\sim\operatorname{Unif}(S^d)$

For two independent random variables distributed uniformly on a $d$-sphere surface ($X_1,X_2\sim\operatorname{Unif}(S^d)$), it is obvious that $$\langle X_1,X_2\rangle\sim -\langle X_1,X_2\rangle$$ by ...
1
vote
0answers
35 views

Is it true that a random graph's degree gives Poission distribution?

In many documents, it is said that a random graph's degree follows Poisson distribution. However, my numerical calculation contradicts with the fact. Assume a random graph whose number of nodes $N = ...
1
vote
1answer
18 views

How many independent even cycles in $G(n,m)$

In the random graph model $G(n,m)$, how many independent even cycles are there ? More precisely, let $C$ be a random variable which counts the independent even cycles. What is $$P(C=c)$$ for $c=0,1,\...
3
votes
1answer
34 views

Isoperimetric constant on random graph

Show that there is a constant $c=c(p) > 0 $ such that almost all graphs in $\mathcal{G}_{n,p}$ verify the following property : for each subset $X \in V(G)$ with cardinality $|X|\leq n/2$, $$ e(X, V\...
0
votes
0answers
35 views

expected number of in- and out-going links in random PA graph

I am looking at an altered directed random graph of the preferential attachment model. Initial starting configuration is: $t=1,$ one node $v_1$. At each time step $(t+1)$ either we create a new node ...
6
votes
1answer
81 views

Probability that a graph is bipartite

Given the empty graph on $n$ vertices, we add $m$ of the $\binom{n}{2}$ possible edges, uniformly at random. What is the probability that the resulting graph is bipartite (equivalently, contains no ...
0
votes
0answers
15 views

probability of wiring sequence and conditional expectations in random configuration graph

I am reading about the Bollobas Configuration random graph and try to understand the proof of following Proposition: (see Prop 2.1 in https://arxiv.org/pdf/1512.03084.pdf, page 7-8) Proposition: ...
1
vote
1answer
38 views

Largest size of a complete bipartite sub-graph in a random graph

Let $G\in G(n,\frac{1}{2})$ be a random graph. What is the maximum number of edges of a complete bipartite graph that can appear as a subgraph in $G$ almost surely? Let's give an estimate in the ...
0
votes
0answers
17 views

Sampling probabilities for half-sparsification algorithm

https://dl.acm.org/citation.cfm?id=2948062 In their article(simple parallel and distributed algorithms for spectral graph sparsification 2016), Koutis and Xu gave a combinatorial algorithm for ...
2
votes
1answer
32 views

Perfect matching in random bipartite graph - with fixed probability

as a follow up from this question : Suppose that we have a simpler problem, where the probability $p$ is fixed. Of course we could use the above result to proove that almost every graph in the model ...
2
votes
0answers
51 views

Probability of being in same connected component

I would like to answer the following basic question: Let $V$ be a collection of $n$ vertices and fix $x$ and $y$ in $V$. Let $G$ be a random graph on $n$ vertices and $M$ edges. What is the ...
3
votes
1answer
52 views

Random graph with $p \ll n^{-1+\epsilon}$ a.a.s has no subgraph with $k$ vertices with at least $k+1$ edges

Let $G=(n,p)$ with $p \ll n^{-1+\epsilon}$ for all $\epsilon >0$. Then for each $k\in \mathbb{N}$ there are a.a.s no $k$ vertices with at least $k+1$ edges. Proof: We want to show $$\Pr(\...
1
vote
1answer
42 views

Binary trees constructed from the bottom up

I'm dealing with a set of random binary trees which I can't find referenced anywhere in literature. Computer scientists seem to prefer "random search trees" which is a different ensemble than mine (...
0
votes
0answers
23 views

Graph properties along trajectories in $G(n,m)$

I consider a graph that changes randomly over (discrete) time denoted by $(G_t)_{t=0}^{\infty}$ where I call $G_0=(V_0, E_0)$, $V_0$ being the vertex and $E_0$ the edge set my initial condition where $...
0
votes
0answers
17 views

Farkas lemma and matrix spectrum

I am currently looking at a problem of the following type : I have a matrix $\mathbf{M}\in\mathbb{R}^{N \times N}$ such that it's general term is given by $(\mathbf{M})_{ij}=z_i \delta_{ij} - A_{ij}...
0
votes
1answer
28 views

Clustering coefficient in a random graph model with transitivity

Reading the book Networks, by Mark Newman I found this exercise and I have some question about it: "We can make a simple random graph model of a network with clustering or transitivity as follows. We ...
1
vote
1answer
31 views

Connectivity of random network

I'm interested in the following (pretty open-ended) problem : Say we have some network of $n$ nodes, labeled by integers $i\in\mathbb{Z}/n\mathbb{Z}$. Each node $i$ chooses a random subset $\mathrm{...
2
votes
0answers
36 views

Are the eigenvectors of real Wigner matrices made of independent random variables with zero-mean?

I am trying to understand a portion of this paper [p. 3] and got stuck in the following statement, which sounded kind of trivial, but has been deceiving me for a while. Would you help me understand? ...
0
votes
0answers
12 views

Family of graphs that have approximation ratio = 2

My question today is about the approximation algorithms. Well, for Approx-Vertex-Cover problems , we know we can get ratio of 2 just by picking an edge and taking 2 endpoints of the same and ...
1
vote
1answer
46 views

Probability of an edge in directed random configuration graph

I am considering Bollobas' directed random configuration graph of size $N$, constructed by the following random algorithm: Draw a sequence of $N$ node-degree pairs $(j_1,k_1),...,(j_N,k_N)$ ...
3
votes
1answer
33 views

Variance of subgraph counts

I try to calculate the variance of the number of triangles in the uniform model $G_{n, m}$ where $m = \lfloor tN \rfloor$ for $t \in (0,1)$ fixed. I think the variation is $O(n^3)$, but I can not show ...
0
votes
1answer
29 views

Regularity of Erdos Renyi graph

I am interested to find out what’s the probability that an Erdos-Renyi graph $\mathcal{G}(n,p)$ is a regular graph? I believe this is a really hard question whose non-asymptotic results are probably ...
0
votes
0answers
19 views

Estimate the probability of missing links based on partially observed graphs

Suppose the underlying true graph $G^T$ is generated from some known random graph model. We are able to obverse a partial graph $G^O$ (Assume the difference between $G^T$ and $G^O$ is that some links ...
1
vote
0answers
53 views

Distributions of components in random geometric graphs

In the context of random geometric graphs where edges are assigned according to a distance criterion $d_{ij}\le \delta,$ with $d_{ij}$ denoting the Euclidean distance between the vertices $i$ and $j,$ ...
2
votes
0answers
24 views

How to randomly sample a social graph to find paths between at least 20% of profiles?

Given a Graph, where we know Total number of nodes (~100,000) Average no of connections per node (~200) Maximum distance between two nodes (~5) How many nodes (and its connections) do we have to ...
1
vote
1answer
61 views

expected value of sum of weights in a random directed graph

Assuming we have a random directed weighted graph with $n$ nodes. Furthermore let us assume the nodes are divided into two categories: A node $i$ is of category C if there are only outgoing edges or ...
3
votes
1answer
48 views

A random $r$-regular graph can be generated by taking union of a a random $(r-1)$-regular graph and a perfect matching.

$\newcommand{\lrp}[1]{\left(#1\right)}$ $\newcommand{\set}[1]{\{#1\}}$ $\newcommand{\mc}{\mathcal}$ $\newcommand{\E}{\mathbb E}$ $\newcommand{\N}{\mathbb N}$ Definition. Let $(\Omega_n, \mc F_n)$ be ...
2
votes
0answers
83 views

Steady states to this generalized TASEP?

The standard setup of a Totally Asymmetric Simple Exclusion Process is pictured below: We have a one-dimensional lattice of length $n$ populated with particles($p_1,p_2,p_3$ in this case) that hop to ...
1
vote
2answers
22 views

Probability of having a link in union of Erdos Renyi random graph

We have two Erdos-Renyi random graphs, $G_1$ and $G_2$, generated with probability $p_1$ and $p_2$, respectively. If we take the union $G_1$ $\bigcup$ $G_2$, we obtain another Erdos-Renyi graph, $G_3$...
2
votes
1answer
39 views

Probabilistic subsampling of an Erdős–Rényi graph

Suppose I have an Erdős–Rényi graph ${\cal G}(n,p)$, where $n$ is the total number of nodes and $p$ is the probability of an edge between any pair of nodes (edges are added independently). I subsample ...
1
vote
1answer
47 views

Randomly selecting and then removing vs Selecting a random permutation

I have been given an assignment for my Randomized Algorithms class. We begin with a graph and start removing vertices step by step. On each step we randomly select 1 vertix and remove that vertix plus ...
2
votes
1answer
75 views

Creating a uniform distribution on the set of all $r$-regular graphs on $n$ vertices.

On pg 5 of Janson's paper Random Regular Graphs: Asymptotic Distributions and Contiguity the following is mentioned: Given $r$ and a vertex set $V$ with $n$ elements (with $rn$ even), define a ...
1
vote
1answer
39 views

probability of having only outgoing edges of a node in a directed graph

Let $G$ be a directed graph with $n$ nodes and an edge between two nodes with probability $p$. (As in a directed Erdos-Renyi graph $G(n,p)$). For simplicity we assume that we pick each direction by ...
2
votes
2answers
78 views

How to choose a $d$-regular graph on $n$ vertices uniformly at random?

Let $n\geq 1$ be an even number and $d\geq 1$ be integers. In these notes by Luca Trevisan, we see a procedure of coming up with a $d$-regular on $n$ vertices on the first page. The procedure is: ...
2
votes
0answers
14 views

Is $\|\lambda\|_3 << \|\lambda\|_2$ for all sub-matrices of a random matrix?

Let $A\in\{0,1\}^{n\times n}$ be a random, symmetric matrix, in which each upper triangular entry is sampled iid. from Bernoulli($p$). Let $\lambda=(\lambda_1, \dots, \lambda_n)$ be the vector of ...
1
vote
1answer
41 views

Question about a preferential attachment model

I am reading the book Complex Graphs and Networks by Fan Chung and Linyuan Lu, in chapter 3, they described a preferential attachment model: Starting from a initial graph $G_0$ and at each time step, ...
0
votes
1answer
54 views

Conditional degree distribution of a network

Consider a network of $N$ nodes with no self loops described by the adjacency matrix $A \in \{0, 1\}^{N \times N}.$ Let's define as $$\deg(v) = \sum_{w=1}^N a_{v,w}$$ the degree of node $v$. Let's ...
0
votes
1answer
30 views

“net-position” of a node in directed Erdos-Renyi graph

In a directed weighted random Erdos-Renyi graph $G(N,p)$ with only positive weights, let $e_{ij}$ denote the weight going from node $i$ to node $j$ and assume all $e_{ij}$'s are normally distributed. ...
0
votes
1answer
47 views

Expected value of sum of weighted edges in a random graph

Assuming one has a directed weighted graph with n nodes and let us denote the weight going from node $i$ to node $j$ by $e_{ij}$. Then one can simply just sum all weights $e_{ij}$ up. But if we are ...
2
votes
0answers
35 views

A Random Edge-colored Digraph Process

I'd like to understand a particular random graph process that I'll describe below. I don't know if it is difficult or elementary, any pointers would be helpful. For a given set $\{1,\dots,n\}$ of ...
-1
votes
1answer
32 views

How to find an isomorphism between these graphs? [closed]

graphs How to find an isomorphism between these graphs?
1
vote
1answer
65 views

Show that Random Graphs Typically Have Diameter 2 (Probabilistic Method)

Show that random graphs typically have diameter 2. That is, the probability that $G_p$, the graph with p vertices, has diameter 2 converges to 1 as $p \rightarrow \infty$. Hint: Find the probability ...
2
votes
1answer
68 views

Average degree of a scale-free network.

Suppose to generate a scale-free undirected network using the preferential attachment algorithm where with start with an $m$-clique, and we attach each new node to $m$ pre-existing nodes. The ...
2
votes
1answer
43 views

Comparing connectivity of differently built geometric graphs

Suppose we want to build a 2d geometric graph, where the domain is a $L$ by $L$ square and the geometric aspect means two vertices are connected by an edge if their distance is smaller than a given ...
0
votes
0answers
26 views

Learning generative models of graphs

I am trying to understand a research paper bit by bit and I am stuck trying to understand this paragraph. What I have understood from the para- We have a set of graphs G={G1,G2,..} which have been ...
1
vote
1answer
58 views

Bounding the degree of very sparse random graph

I am confused with how to manipulating with big O notation ,here is a problem from section 2.4(Exercise 2.4.3) high dimensional probability by Roman Vershynin Consider a random graph $G \sim G(n,p)$ ...
1
vote
1answer
36 views

Proof that $t(n)=\frac{r}{n-1}$ is a threshold function in random G(n,p) graph

I've been looking everywhere for a rigorous and detailed proof that $$t(n)=\frac{1}{n-1}$$ is a threshold function for the property that a single distinguished node in a random Erdos Reny graph has ...
0
votes
1answer
153 views

Number of directed graph with $n$ vertices [closed]

In terms of $n$, how many distinct digraphs are there whose vertex set is $X$, where $X$ is a nonempty finite set with $|X| = n$? How does the answer change if we allow loops, but not parallel arcs? ...
0
votes
1answer
41 views

Find unordered cycle

In an undirected random graph of 11 vertices the probability of an edge being present between a pair of vertices is 2/5. What is the expected number of unordered cycle of length 3. I think the answer ...
5
votes
1answer
96 views

Random graphs with a hamiltonian path

Suppose we randomly choose a graph with $n$ vertices in the following manner: each edge is included with probability $\frac12$. Thus, each graph has the same probability of being chosen, and there are ...