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
0 votes
0 answers
13 views

Sampling variance of edge density of subgraphs

I would like to evaluate the mean and variance of the edge density for subgraphs obtained by repeatedly subsampling nodes. Specifically, suppose we have an undirected graph $G$ with $N$ vertices and ...
Till Hoffmann's user avatar
2 votes
0 answers
49 views

In search of a model to describe worm behaviour

For my bachelors thesis I am working with tubifex worms, and trying to develop a graph theoretical model that can help explain some mechanical and dynamical properties of the worms once they have ...
Rowan Potato's user avatar
0 votes
0 answers
17 views

Are there spacial graph models that generate power law distributions with a constant number of nodes? [closed]

I have recently been looking into (random) graph models, and it seems as though most graph models that encompass scale-free properties have growth tied into them. I am interested to know if there are ...
Rowan Potato's user avatar
0 votes
0 answers
46 views

How to solve following binomial equation to get the assortivity?

Proving Assortativity r from Symmetric Binomial Distribution Consider the symmetric binomial form given by the equation: $$e_{jk} = N \binom{j+k}{j} p^j q^k + \binom{j+k}{k} p^k q^j$$ where $p+q=1$, $\...
Nitish Kumar Sharma's user avatar
0 votes
0 answers
36 views

Sequence of degrees of a graph with two colors

With respect to the graph Another concept central to an understanding of fractional isomorphism is that of the iterated degree sequence of a graph. Recall that the degree of a vertex $v\in G$ is the ...
Tomais's user avatar
  • 509
0 votes
2 answers
83 views

Number of triangles in Erdös-Renyi graph

For each ${n}$, let ${(V_n,E_n)}$ be an Erdös-Renyi graph on ${n}$ vertices with parameter ${1/2}$ (we do not require the graphs to be independent of each other). If ${|T_n|}$ is the number of ...
shark's user avatar
  • 751
0 votes
1 answer
38 views

Does this simple model have a name?

For my thesis I created a simple random graph model and studied some of its properties, and I was wondering if this model has a name so I can look into it further. The model essentially takes the ...
Rowan Potato's user avatar
0 votes
0 answers
12 views

Using graphs to quantify the structure/pattern or correlation among the elements of supposedly random matrix

Let's say I have a supposedly random real symmetric matrix. How to use graphs to quantitatively (with a numerical focus) examine any structure/pattern or correlation among its elements ?
Snpr_Physics's user avatar
0 votes
0 answers
35 views

Kullback-Leibler Divergence between a random variable and the product of its entries

Problem Statement I'm currently working with a result about Kullback-Leibler divergence. Let $X$ be an discrete random variable taking values in $\mathcal{X} := \{0,1\}^p$, with $X = (X_1, X_2,...,X_p)...
Ollie's user avatar
  • 61
0 votes
0 answers
46 views

Using Janson inequality to the probabillity that all vertex belongs a triangle

I am working on a random graphs problem, which is stated as follows: Prove that there exists some positive constant $C$ such that with high probability (w.h.p.), every vertex belongs to a triangle in ...
香结丁's user avatar
  • 419
1 vote
0 answers
70 views

Property of vertices in random graphs

For a random graph $G\sim G\left(n,p\right)$ with probability $p$, for every vertex $v$, I need to prove that with high probability, $X=\deg\left(v\right)$ satisfies the condition $\left|X-np\right|\...
Ali AD's user avatar
  • 23
0 votes
1 answer
47 views

How to compute the variance of the vertex degree in $G(n,1/2)$?

Consider the random graph $G(n,1/2)$ and let $d(v)$ be the degree of the vertex $v \in V(G)$. By considering the indicator RV $X_w$ for the evenet $\{v,w\} \in E(G)$ it is easy to see that $$\mathbb{E}...
3nondatur's user avatar
  • 4,128
1 vote
0 answers
23 views

What is the expected distribution of sphere sizes in random graphs with constant degree?

Let $G=(V,E)$ be a random undirected, unweighted graph where each vertex $v\in V$ has degree $n>1.$ Let the $k$-sphere $S(v_0,k)=\{\,v\mid v\in V,\;d(v,v_0)=k\,\}$ of $v_0$ be the set of vertices ...
FUZxxl's user avatar
  • 9,277
0 votes
1 answer
34 views

Question about analyzing greedy algorithm for the max cut problem in random graphs

In https://lucatrevisan.github.io/teaching/bwca17/lectures/lecture02.pdf (Lemma 6), the professor claimed that: "With high probability over the choice of $G$ from $G_{n,\frac{1}{2}}$, the greedy ...
graph lover's user avatar
0 votes
0 answers
14 views

Analytical Proof of Random Failure Tolerance in Scale-free Network

I aim to demonstrate that scale-free networks exhibit greater resilience to random failures compared to random networks. Are there any analytical approaches available for proving this assertion? ...
SDGAL's user avatar
  • 1
1 vote
2 answers
109 views

A doubt about almost all graphs

I am currently trying to understand the paper “On the chromatic index of almost all graphs” by Erdős and Wilson. I have two doubts, I’d be grateful if someone could explain them to me. This is part of ...
boil's user avatar
  • 125
2 votes
0 answers
76 views

Diameters of random bipartite graphs [closed]

Given two partite sets of vertices $U$ and $V$ of size $n$. Each vertex in $U$ uniformly randomly selects $K$ ($K$ is a constant and $K\ll n$) vertices in $V$ without replacement and connects a ...
Zijian Wang's user avatar
0 votes
1 answer
93 views

Probabalistic Method: Using Janson' inequality to estimate the probability of existence of a $4$-clique

Let $c > 0$ and set $p := \frac{c}{n^{2/3}}$. Use Janson's Inequality to find a function $q(c): \mathbb{R}_{>0} \rightarrow (0,1)$ such that $$\mathbb{P}\left[ \text{$G(n,p)$ contains no clique ...
3nondatur's user avatar
  • 4,128
3 votes
1 answer
109 views

Probabilistic Method: Almost every random graph contains all graphs on $k$ vertices as induced subgraphs [duplicate]

Let $k_0 \in k_0(n) \subset \mathbb{N}$ be such that $${n \choose k_0} 2^{-{k_0 \choose 2}} < 1 < {n \choose k_0 - 1} 2^{-{k_0 - 1 \choose 2}}$$ and let $k = k_0 - 4$. Show that $$\mathbb{P}\...
3nondatur's user avatar
  • 4,128
0 votes
0 answers
88 views

When does a random geometric graph become connected?

Fix $n\in \mathbb N$ and let $X_1,\dots,X_n$ be i.i.d uniform random points in $[0,1]^2$. For $r\in \mathbb R$ consider the (random) geometric graph $\mathcal G _r(X)$ with vertices $X=\{X_i\}$ and ...
Alex's user avatar
  • 759
3 votes
1 answer
251 views

Expected graph edit distance between two random graphs

Consider Erdos-Renyi random graphs $G(n,p)$. Let us independently sample two graphs $G_1$ and $G_2$ following $G(n,p)$. What is the expected graph edit distance (GED) between $G_1$ and $G_2$? Since ...
Vezen BU's user avatar
  • 1,812
0 votes
0 answers
33 views

Bounding the Degrees of Very Sparse Graphs (Vershynin 2.4.3)

I think I might've solved Exercise 2.4.3 in Vershynin's High Dimensional Probability, although I am suspicious of my solution. The problem: Consider a random graph $G\sim G(n, p)$ with expected ...
user806050's user avatar
0 votes
0 answers
20 views

Asymptotic number of loops in random assignment [duplicate]

Given N nodes I randomly pick a permutation of the nodes and use this permutation to define an assignment: I associate one and only one node to each node. This procedure naturally defines a graph made ...
jimifiki's user avatar
  • 101
0 votes
0 answers
39 views

upper bound the number of 5-cycles in a random graph

Let $k$ be the number of edges of a graph $G$, I’d want to show that $G$ can contain at most $(2k)^\frac{5}{2}$ cycles of length $5$. I thought about showing this for the Erdös-Renyi graph model $G(2k,...
whatisaring's user avatar
2 votes
0 answers
29 views

Are there existing random graph models that allow controlling assortativity?

Here, we are talking about degree assortativity (https://en.wikipedia.org/wiki/Assortativity). We know that the expected assortativity of graphs generated by Erdos-Renyi or Chung-Lu asymptotically ...
Vezen BU's user avatar
  • 1,812
0 votes
1 answer
55 views

Determine if each of the following graphs is connected and/or super-connected. Briefly justify your responses. [closed]

I am struggling to answer this question, and I was hoping for some assistance and/or help, it would be greatly appreciated. This link is a screenshot of the question because it does include diagrams: ...
Ella's user avatar
  • 31
2 votes
1 answer
53 views

Algorithm for constructing a component with linear number of vertices.

I see an algorithm from the lecture course for constructing components with a linear number of vertices. The algorithm is stated as follows: $G_0$ be the empty graph on $n$ vertices; For $i = 1, \...
香结丁's user avatar
  • 419
1 vote
1 answer
87 views

Understand big O-notation for random graphs?

I was reading a bit in the book High-dimensional probability theory by Roman Vershynin and I was trying to do Exercise 2.4.2 and I do think I still have some misunderstandings regarding the statement ...
tor's user avatar
  • 79
1 vote
1 answer
70 views

How to apply the probablistic method in a random graph?

The following is meant to be solved with the Probabalistic Method: For $n \in \mathbb{N}_0$, let $S_n$ be the set of all $0$-$1$ sequences of length $n$; in particular $S_0$ has the empty sequence $\...
3nondatur's user avatar
  • 4,128
1 vote
1 answer
132 views

Albert-Barabasi model

According to Remco Hofstad's book on Random graphs, for the Albert Barabasi model, the degree of the i^{th} node diverges almost surely (Exercise 8.8 of the first volume). But isn't this counter-...
Math_1410's user avatar
3 votes
1 answer
245 views

Very Sparse Graphs are Far from Regular

I am trying to prove the following statement: Consider a random graph $G \sim G(n, p)$ with expected degrees $d = O(1)$. Show that with high probability, (say, $0.9$), $G$ has a vertex with degree $$ ...
Partial T's user avatar
  • 483
1 vote
0 answers
69 views

What is the expected number of walks with length 𝑘 in Erdős–Rényi random graph?

Let $G(N, p)$ be a directed Erdős–Rényi random graph with edge probability $p$. Let $W_k$ denote the number of walks (potentially with repeated vertices, or repeated edges) of length $k$ beginning at ...
c_lienk's user avatar
  • 58
1 vote
1 answer
71 views

Typical mixing in random walks on the random graph

I'm trying to understand two things in Theorem 1 in the Random Walks on the Random Graph journal paper. Theorem 1 is about mixing time of a simple random walk on a Erdos-Renyi graph (i.e. a random ...
trickymaverick's user avatar
0 votes
0 answers
73 views

Configuration model for weighted graphs for use in modularity formula

I cannot wrap my head around how the configuration model works if we have a degree sequence that has non-integers in it, i.e. we have edge weights $w\in \mathbb{Q}$ and nost just $w\in \mathbb{N}$ (...
Splines's user avatar
  • 101
1 vote
0 answers
26 views

understanding random graphs with specified degree distribution

I was self-reading this note Random Graphs as models of networks by Newman; Could anyone explain briefly what is happening in section $2$? I did not get the algorithm he described too. This may be due ...
Myshkin's user avatar
  • 35.9k
1 vote
0 answers
46 views

Average Finite Component Sizes of Random Graph under Stochastic Dominance

Let $X$ and $Y$ be two $\mathbb{N}$-valued random variables. We say $Y$ stochastically dominates $X$ in the first order, written $X\le Y,$ if and only if $\mathbb{P}(Y>k) \ge \mathbb{P}(X>k)$ ...
deej's user avatar
  • 117
1 vote
1 answer
105 views

Determining if a given graph is a Word Graph

I started to read the book "A First Course in Graph Theory" to refresh some concepts about Graphs. In the first chapter, the author gives a definition of a word graph (something I didn't ...
James's user avatar
  • 121
1 vote
1 answer
129 views

Expected number of cycles in a random tournament

What is the expected number of cycles (of each length, if you like) in a tournament of order $n$ where the direction of each edge is decided uniformly at random? The case $n = 3$ is trivial to ...
jdonland's user avatar
  • 197
1 vote
0 answers
90 views

Modified Erdos-Renyi Random Graph with Self-Loops and Maximum Allowed Degree of Nodes

Let $G(n, p, k)\ (n, k \in \mathbb{N}^+, p \in \mathbb{R}, 0<p<1)$ be a graph with $n$ nodes constructed with the following rules: The degree of any node does not exceed $k$. Each edge is ...
THU_Arte's user avatar
4 votes
0 answers
211 views

Probability of a survivor

In a room stand n armed and angry people. At each chime of a clock, everyone simultaneously spins around and shoots a random other person. The persons shot fall dead and the survivors spin and shoot ...
Transcendental's user avatar
1 vote
0 answers
45 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 ...
Harry Vinall-Smeeth's user avatar
2 votes
1 answer
76 views

Let $H$ be a graph. Prove that almost every graph $G \in \mathcal{G}_{n,p}$ has $H$ as an induced subgraph

Let $H$ be a graph. Prove that almost every graph $G \in \mathcal{G}_{n,p}$ has $H$ as an induced subgraph. Couldn't reach far on this one... My naive approach was to use Markov's inequality with the ...
Bruno Reis's user avatar
  • 2,306
0 votes
1 answer
29 views

why is this equation involving landau symbols true?

I am not understanding the following "equation": $$\left(N\left(1-O\left(\frac{kt}{n}\right)\right)\right)^{m-(k-1)t}=N^{m-(k-1)t}\left(1-O\left(\frac{mkt}{n}\right)\right)$$ $k$ and $t$ are ...
algebruh's user avatar
3 votes
1 answer
121 views

Domination Number of Random Graphs

I am investigating the domination number of a random graph $G(n,1/2)$ on $n$ vertices. The edges are formed with probability $1/2$. I know that the domination number of a complete graph $K_n = 1$. I ...
Mr. Nobody's user avatar
2 votes
1 answer
33 views

Is there any literature on union of random mappings?

I have studied the landmark papers of Rubin et al, Harris, Flajolet on Random mapping statistics. I have also read some follow up papers. They provided analysis of the structure of random maps. My ...
Bishwajit Chakraborty's user avatar
0 votes
0 answers
30 views

Finding the first vertex in a recursively growing graph

I have an undirected graph which grew according to a recursive algorithm, i.e., it started with a single vertex and then, one after another, new vertices arrived and connected to existing ones. Now, I'...
Bob Aiden Scott's user avatar
1 vote
1 answer
103 views

A uniform random graph

I am reading the article Rainbow trees in uniformly edge-colored graphs. But I encountered some difficulties and was puzzled. There is a random graph $G(n,\omega(1)/n))$ and a color set $\mathcal{A}...
zhukui bai's user avatar
0 votes
0 answers
71 views

the distribution of triangles in a general $G(n,p)$ graph

let $Y$ be the random variable of the amount of triangles in a given graph. what is the distribution of $Y$? I tried looking at the probability of $I_{i,j,k}$ the indicator of 3 given nodes having a ...
Roy Dahan's user avatar
1 vote
1 answer
64 views

About the regularity of a pair of vertex subset when the density between them is less than epsilon

Given a graph $G=(V,E)$. Let $X, Y\subset V$. Recall that the density of a pair of vertex subsets $(X, Y)$ is defined as $$ d(X,Y)=\frac{e(X,Y)}{|X|Y|}, $$ where $e(X,Y)$ counts the number of edges ...
Thinkpad's user avatar
  • 383
1 vote
0 answers
22 views

Deriving an ODE for a modified Greedy Algorithm on 3-Regular Random Graphs

I'm currently working on a research project that involves the analysis of a modified greedy algorithm on 3-regular random graphs. The algorithm works as follows: at time t = 0, any node is selected ...
Drill_zoo's user avatar
  • 321

1
2 3 4 5
18