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.

Filter by
Sorted by
Tagged with
1
vote
1answer
24 views

I don't understand the fast generation algorithm for Stochastic Kronecker Graphs

I've been reading this paper and using this link as a reference while reading about Stochastic Kronecker Graphs, and I don't understand the algorithm that generates such a graph recursively and in $O(...
0
votes
0answers
11 views

Expected values of adjacency matrix elements of double edge swap randomized graphs

Problem Suppose I have a simple graph $G$ with adjacency matrix $A_{ij}$ and there are no self-loops. Consider the distribution of graphs obtained by randomizing $G$ through double edge swap ...
0
votes
1answer
27 views

Expected number of nodes of degree $1$ in binary tree with $n$ edges

What is the expected number of nodes of degree 1 in a binary tree with $n$ edges? The binary tree need not be full; 1 child node is allowed. I have looked at Catalan numbers. These can give you the ...
0
votes
0answers
25 views

Generative Model for random graphs with community structure based on Random Walks (similar to Stochastic Block Model)

There are many algorithms in which the community structure of a graph is recovered using Random Walk based methods such as Walktrap, Markov Clustering Algorithm etc. One of the most popular random ...
2
votes
0answers
35 views

representing of expectation for submatrices

Consider a matrix $$ A= \begin{pmatrix} a_{11} & a_{12} & a_{13} & a_{14} & a_{15} & a_{16} \\ a_{21} & a_{22} & a_{23} & a_{24} & a_{25} & a_{26} \end{pmatrix}...
2
votes
1answer
56 views

Why the clique numbers of almost all graphs are concentrated at two values?

I read that for fixed $0\leq p \leq 1$, the clique number of $G(n, p)$ is concentrated at $d$ and $d+1$, where $d$~$2log_{\frac{1}{p}}n$. The key point is that $d$ is the maximum integer with $\binom{...
0
votes
1answer
55 views

Why are the probability and mean number of edges between two nodes in a network equal for large networks?

Slide 18 in this lecture goes: What is the probability of an edge between nodes $i$ and $j$? There are $k_i$ stubs at node $i$ and $k_j$ at $j$ The probability that one of the $k_i$ stubs of node $...
1
vote
2answers
72 views

How do you mathematically define a random line or in general, a random subspace of a Euclidean space?

I'm looking for a definition of random $k$-dimensional vector subspace of the Euclidean space $\mathbb{R}^d, k, d$ are fixed. I'm guessing one should start with a random basis, i.e. a set of ...
0
votes
2answers
41 views

How many times does the graph of $x = t^2 - t - 6$, $y = 2t, -5 < t < 5$ cross the $y$-axis?

Although I know that it will pass through $y$-axis twice, when $t = - 2$ at $(0, - 4)$ and when $t = 3$ at $(0, 6)$ but what is the explanation to it?
1
vote
1answer
31 views

Graphon model for random graphs and almost surely dense graphs

Consider the random graph generating process from a graphon. A random graph model is an exchangeable random graph model if and only if it can be defined in terms of a (possibly random) graphon. It ...
0
votes
0answers
8 views

In a hypergraph, the edges are selected to be in some set with probability $p$. What is the probability that some vertex $v$ is not in that set?

For a $r$-uniform hypergraph $H$ on $n$ vertices with edge set $E$, each edge is picked independently to be in $E' \subset E$ with probability $p$. For a vertex $v \in H$ with deg$(v) = k$, I want to ...
0
votes
0answers
11 views

Does this definition for cycles in hypergraphs appear anywhere?

I'm looking for a definition of a cycle on a $k$-uniform hypergraph that is equivalent to the following definition: Let $H=(V,E)$ be a $k$-uniform (each hyperedge contains $k$ vertices) hypergraph on $...
0
votes
0answers
31 views

Probability of a vertex not belonging to a set of edges in a random hypergraph.

Let $H(n,p)$ be a $r$-uniform random hypergraph on $n$ vertices, with vertex set $V$ and edge set $E$. Let $E' \subset E$ be a set of edges with some known characteristics, and $V' = V \setminus \{u_i:...
0
votes
1answer
25 views

Cover and fractional covers

I have troubles understanding this definition of a fractional cover. It was in the context of graphs and random variables. The $1_V$ stands for the indicator function: Let $V$ be a finite set and let ...
1
vote
1answer
28 views

High probability range of chromatic number

Prove that there is an absolute constant $c$, for every $n>1,$ there is an interval $I_{n}$ of at most $c \sqrt{n} /$ log $n$ consecutive integers such that the probability that the chromatic ...
1
vote
1answer
18 views

Value $p$ that makes the random hypergraph $H^{(k)}(n,p)$ a good cover?

I need help understanding the following argument. Definition. A $(k, t)$-covering of $[n]$ is a family of $k$-sets $\mathcal{F} \subseteq\left(\begin{array}{c}{[n]} \\ k\end{array}\right)$ such that ...
0
votes
0answers
22 views

Distance between two vertices from the ER graph.

Let $G$ be an ER graph $G = G(n,p)$ which is constructed by connecting nodes randomly and each edge is included in the graph with probability $p$ independent from every other edge. For every pair of ...
0
votes
0answers
12 views

For $G \sim G(3,p)$ with potential edge set $\{e_1,e_2,e_3\}$, and $\omega(G)$ the size of the largest clique, what is $\mathbb{E}[\omega(G) | e_1]$?

So I'm interested in the quantity $\mathbb{E}[\omega(G) | e_1]$. By definition, this can be calculated as $$\mathbb{E}[\omega(G) | e_1] = 1 \cdot P(\omega(G) = 1 | e_1) + 2 \cdot P(\omega(G) = 2 | e_1)...
0
votes
1answer
55 views

Interpretation of martingales in graphs.

Here's a definition and an example/framework from our class. Definition 5.4.3 (Martingale) A martingale is a sequence $Z_{0}, Z_{1}, \ldots, Z_{m}$ of random variables such that, for each $1 \leq i \...
3
votes
0answers
25 views

Model Epidemic Random Graph

I'm reading on random graphs and understand that they can be used to model disease spread (seems particularly germane at the moment). The papers I've found so far are focused on quite complex models. ...
0
votes
0answers
27 views

Number of triangles in a random graph.

Let G be the random graph $G\left(n,\frac{\log(n)}n\right)$, i.e. the graph on $n$ vertices with each edge independently having probability $\frac{\log(n)}n$ of being in the graph. I wrote a program ...
1
vote
1answer
72 views

zero-one-law in percolation theory

I am currently working on a paper by Lyons from 1990 which can be found at https://projecteuclid.org/download/pdf_1/euclid.aop/1176990730. In chapter 6 Percolation (page 951, 21 respectively) the ...
1
vote
1answer
24 views

A graph $G(n,p)$ has $\Omega(k^2)$ edges of a special type, $k \in \mathbb{Z}^+$. If $p = \omega(k^{-2})$, then w.h.p. one of the edges is in $G$.

Why is it so? I know that the probability that none of those edges appears in the graph is $(1-p)^{k^2}$, but not sure how to continue with the reasoning.
0
votes
0answers
18 views

Hiting line in a 2D plane in a 1m radius with shortest walk

Imagine you where in a 2d plane and the place is so dark that you can't see anything. In a 1 meter radius around you, there is a rope (straight line). What would the shortest walk be for hitting that ...
1
vote
0answers
18 views

Construct a subgraph of the complete graph with a fixed distribution of valences

Suppose that I want to find a "well connected" large random graph where the distribution of the valences follow a fixed distribution. Is there a smart way to construct such a graph? More ...
1
vote
1answer
37 views

Expected value of random walk over signed network

A connected weighted graph $G(V,E,W)$ is give, where $w_{uv}$ corresponds to the probability to jump from node $u$ to node $v$. Also, a function $l$ maps nodes with positive and negative labels, where ...
1
vote
1answer
29 views

For $G \sim G(n, 0.5)$, $I$ a $k$-set of vertices, and event $E_I = \{G[I] \cong K_k \text{ or } K_k^c \}$, how many events does $E_I$ depend on?

The note in my lecture says that $E_I$ is independent of all events with disjoint edge-sets, and so it depends on at most ${k \choose 2}\left({{n-2}\choose {k-2}}-1\right)$ other events. I don't ...
1
vote
1answer
37 views

Lines randomly drawn on a page.

Suppose I have a $m \times m$ sheet of paper. Now suppose I draw a line of length $L$. The center of the line must lie within the piece of paper, and the orientation of the line is randomly chosen ...
0
votes
1answer
31 views

Let $\varepsilon > 0$ be fixed. Then the random graph $G(n,m=(1+\varepsilon))$ is a.a.s not planar.

The exact question is in the title. I understand that I somehow need to find a graph with $K_{3,3}$ or $K_5$ as a minor, but I don't really know how. I got that having $K_5$ as a minor is equivalent ...
1
vote
0answers
16 views

Stochastic Block Models regimes and topology

Hi I'm trying to understand how regimes and thresholds of Erdős–Rényi model are valid in symmetric stochastic block model. In Erdős–Rényi model $G(n,p)$ each edge is drawn independently with ...
3
votes
0answers
18 views

Average shortest path and diameter in Poisson-Delaunay graphs

For a given set of $N$ random points, distributed uniformly on a unit square, I construct its Delaunay triangulation. Taking the triangulation as an unweighted graph, I need to know the expected ...
1
vote
1answer
39 views

How many 2-hop neighbors in ER network?

An ER network is a graph $G=(V,E)=\mathcal{G} (n, p)$, where there're $n$ nodes and for each two nodes $i,j\in V$, the edge $(i,j)$ has the probability $p$ of being present in $E$ and $(1-p)$ of being ...
1
vote
1answer
19 views

Probability that a node loses an edge in the Barabási-Albert (BA) model with removal of edges

I'm following the book Networks by Mark Newman. He considers an extension to the BA model where edges are removed uniformly at random. He computes the probability that a particular node $i$ loses an ...
3
votes
1answer
47 views

Number of edges of a random connected undirected graph created by a random walk

Consider the following algorithm that generates a random connected undirected graph with $n$ vertices. Choose a random starting vertex and perform a random walk as follows. At each step $i$ of the ...
1
vote
2answers
47 views

How to understand graph property thresholds?

Here are some definitions: Definition 1: A graph property $\cal{P}$ is monotone (increasing) if adding edges preserves $\cal{P}$. Examples include containing a subgraph $H \subset G$, having $...
1
vote
0answers
19 views

Generating function exponential random graphs with expected number of edges ⟨m⟩

We refers to Statistical mechanics of networks by Park and Newman in the section. Random graphs Considering exponential random graphs with fixed number of vertices n we know only the expected ...
1
vote
1answer
53 views

Edge probability and expected number of edges in the configuration model

This question is related to question: Probability that exists at least an edge in the configuration model There is something I do not understand about the computation of the expected number of edges ...
1
vote
1answer
25 views

In a random graph $G(n,p)$ with $\delta(G) \geq \delta$, how is the event $\{S \subset V \text{ is not a dominating set} \}$ characterized?

This is a problem from my class, with the first part of the solution. I'd like to ask something about the set $S \subset V$ as defined below. Problem: Given $G$ on $n$ vertices with $\delta(G) \geq ...
0
votes
0answers
9 views

Lemma about bounding the weight of a half edge in a random graph

I have a couple of questions about Lemma $11$, page $949$ here. The lemma needs some background about construction of a tree which is described in section $6.2$, right above the lemma in page $948$. ...
1
vote
1answer
44 views

Expected number of isolated vertices in a random graph.

I'd like to find the expected number of isolated vertices in the random graph $G=(V,E)$, where $V=\{1,\ldots,n\}$, constructed choosing uniformly at random $m$ edges out of the $\binom{n}{2}$ possible ...
2
votes
1answer
34 views

In a connected random graph, when the degree of each node is at least 2?

In random graphs, we know while $p>ln(n)/n$, the graph is connected. In a connected graph, I want to know when the degree of each node is at least 2 ? If $X$ is ${B(n,p)}$ $n\to+\infty$ When $p$ ...
1
vote
0answers
14 views

Adjacency spectra of a graph interpretation

I'm not a mathematician and I have a question about spectral graph theory. Is it possible to conclude that we have a fully connected network, if an adjacency spectra of a graph is continuous with no ...
0
votes
1answer
66 views

Given a set of $n$ random variables, such that each $k_n$ of them are indepedent, can we say something “global” about their independence?

I'm thinking about a certain problem regarding the existance of structures in random graphs, and somwhow it comes down (after some simplifications) to the following probabilistic problem. Assume we ...
1
vote
0answers
20 views

Average path length in random DAG

Suppose I have a random directed acyclic graph (DAG). By random I mean that edges are drawn uniformly at random so that the adjacency matrix is lower triangular with i.i.d. entries. Is there any ...
2
votes
0answers
49 views

Broadcast in random graph

In a random graph $G(n, m)$, there are $n$ vertexes and $m$ edges, the degree mean is $k$. $G$ is connected, i.e., $m>\frac{1}{2}n\ln(n)$, $n\to +\infty$ Broadcasting process: round 0: A vertex ...
0
votes
0answers
24 views

Constructing a large balanced bipartition of $G(2n,1/2)$ with high probability

Consider the random graph $G(2n,1/2)$. After picking each edge uniformly and independently with probability $1/2$ suppose that we have exactly $m$ edges in total (note: $m$ is not fixed!). Prove that ...
0
votes
0answers
34 views

Clustering number on ring lattice

I have seen in several places a useful formula that let us calculates the clustering number of regular ring lattice graphs with even degree but I have not found a convincing proof of it. Concretely, ...
1
vote
1answer
17 views

For $X,Y,$ RVs on $\{0,1\}^V$, does $P(v \in X) \geq P(v \in Y)$ for every $v \in V$ imply that X stochastically dominates Y?

More specifically, for an infinite graph $G = (V,E)$, and random variables $X,Y$ taking values on the subsets of $V$: Suppose that, for every $v \in V$, $$\mathsf{P}(v \in X) \geq \mathsf{P}(v \in Y)...
0
votes
0answers
27 views

How to generate random graphs subject to a set of logic rule constraints?

I would like to generate a large graph for simulation. For example, given some rules: (A, fatherOf, B), (B, fatherOf, C) -> (A, grandFatherOf, C) (A, tallerThan, B), (B, tallerThan, C), (C, ...
0
votes
1answer
31 views

Edge density in subgraphs of an Erdos-Renyi graph $G(n,p)$

Given an Erdos-Renyi random graph $G\sim G(n,p)$, I want to estimate the probability that all the subgraphs of $G$ (that are not too small, say subgraphs on $m>\epsilon n$ vertices) have edge ...

1
2 3 4 5
13