Questions tagged [random-graphs]
The study of probability distributions over graphs. For example, the Erdős–Rényi model where each edge occurs independently with equal probability.
235
questions
-2
votes
1answer
36 views
Ensemble averaging in a random graph (or network) in the large $N$ limit [closed]
I have a random graph/network described by the adjacency matrix $(a_{ij})_{N\times N}$ where $a_{ij}=1$ with probability $p$. Each node in the graph is associated with a continuous quantity $\eta_i=\...
0
votes
0answers
34 views
Average number of edges of an induced graph by using the edge-based node selection technique on a graph with arbitrary degree distribution
Let $G(U,V,E)$ be a simple, undirected, bipartite graph and $U=\{u_1,u_2,{\cdots},u_n\}$ and $V=\{ v_{1},v_{2},\cdots,v_{n}\}$. Let $d_k^l$ be the number of vertex with degree $k$ in $l$, where $l \in ...
2
votes
1answer
61 views
Critical probability for Erdos-Renyi digraphs to be strongly connected
Given $p \in [0,1]$, an Erdos-Renyi graph ${ER}(n,p)$ on $n$ vertices is constructed by defining, for each unordered couple of distinct vertices ${i,j}$ an edge between $i$ and $j$ with probability $p$...
3
votes
0answers
162 views
Probability that a random multigraph is simple
Question.
Consider a given sequence of $n$ integers $d_1$, $d_2$, $\cdots$, $d_n$ with $\sum_i d_i$ even and $d_i\le n$ for all $i$. One may sample a random multi-graph having this degree sequence ...
7
votes
0answers
252 views
Graph with path of length $\geq n$ along grid diagonals - a known result in graph theory?
Is the following lemma a well known result in graph theory?
I am studying a basic existence result that appears to be simple yet powerful. I have not seen it stated as an important result in graph ...
1
vote
1answer
48 views
Relation between expected values of eigenvalues of Laplacian matrix of a graph and eigenvalues of expected Laplacian matrix of that graph?
Particularly, I am dealing with Erdős–Rényi random 𝐺(𝑛,𝑝), so the expected Laplacian matrix of 𝐺(𝑛,𝑝) is 𝑝(𝐽𝑛−𝐼𝑛), where 𝐽𝑛 and 𝐼𝑛 are one and identity matrices, respectively.
In ...
1
vote
0answers
24 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
0answers
38 views
Count shortest path with different lengths in random graph
Let $G(n,p)$ be an Erdos-Renyi random graph on $n$ vertices with probability $p$, i.e. for each pair of vertices, they are connected directly by an undirected edge with probability $p$. Suppose we are ...
1
vote
1answer
26 views
An attempt to find expected value of clique number of special random graph
Let $G(n)=(V,\mathcal{E})$ be a random graph definded as follows:
$V=[n]=\{1,2, ... ,n\}$ and for all $i,j\in V$ so that $i\ne j$ we have $\{i,j\}\in\mathcal{E}$ with probability $p$. Where $p\in[0,1]...
1
vote
0answers
38 views
4-cycles vs eigenvalue information on quasi-random graphs
My (philosophical) question arises from reading the wonderful paper of Chung-Graham-Wilson where the authors introduces the notion of quasi-random graphs.
The main purpose of the paper is to show ...
12
votes
1answer
313 views
Distribution of degree in graphs: when is the friendship paradox the paradox it wants to be?
$\DeclareMathOperator\deg{deg}\DeclareMathOperator\ndeg{ndeg}\newcommand\abs[1]{\lvert#1\rvert}$The friendship paradox goes most people have fewer friends than their friends have on average. The ...
5
votes
1answer
95 views
Attacking a network at minimum cost
A target system is modelled as a giant, undirected, simple graph $G$ (simple meaning no hyperedge) that can be scrutinized in adequate detail to budget and plan the attack: its topology changes slowly ...
1
vote
1answer
97 views
Asymptotically tight concentration of norms of subgaussian random vectors with independent coordinates, as the dimension $n \to \infty?$
Let $X=(X_1 \dots X_n)\in \mathbb{R}^n,$ be a subgaussian random vector so that $X_i$'s are independent, $\mathbb{E}X_i = 0, \mathbb{E}X_i^2=1.$ Before we pose our question, let's state the following:
...
0
votes
0answers
38 views
Concentration of $2$-norms of random variables whose co-ordinates are not independent?
Let us consider the random vector $X=[X_1 \dots X_d] \in \mathbb{R}^d, E[X]= 0, cov[X]= \Sigma.$ Then the random vector $Z:= \Sigma^{-1/2} X=[Z_1 \dots Z_d]$ has $E[Z]=0, cov[Z]=I_d.$ I'm looking for ...
4
votes
0answers
54 views
Expected number of bridges in a random subgraph
I am researching connectivity in random subgraphs and have come across the following problem.
A bridge between two vertices $a$ and $b$ of a graph $G$ is an edge $e$ such that removing $e$ from $G$ ...
3
votes
1answer
90 views
Unique maximum degree in tournament
Consider a uniform random tournament with $n$ vertices. (Between any two vertices $x,y$, with probability $0.5$ draw an edge from $x$ to $y$; otherwise draw an edge from $y$ to $x$.) Let $p(n)$ denote ...
1
vote
1answer
72 views
Size of minimum cut in random graph
Consider a uniform random tournament with $n$ vertices. (Between any two vertices $x,y$, with probability $0.5$ draw an edge from $x$ to $y$; otherwise draw an edge from $y$ to $x$.) The score of each ...
0
votes
0answers
39 views
Giant bounded degree subgraph in supercritical Erdos-Renyi graph
We are studying an epidemic model and find ourselves needing criteria for when a giant component of bounded degree vertices is contained in the giant component.
Let $G\sim G(n, \mu/n)$ with $\mu >...
2
votes
2answers
100 views
Difference between two largest degrees
Consider a uniform random tournament with $n$ vertices. (Between any two vertices $x,y$, with probability $0.5$ draw an edge from $x$ to $y$; otherwise draw an edge from $y$ to $x$.) Let $S$ be the ...
1
vote
1answer
78 views
Limit of normalized sum of Dirac measures at first $\lfloor p/2\rfloor$ eigenvalues of the sample covariance matrix, with Marcenko-Pastur assumptions?
Let $\lfloor{*}\rfloor$ denotes the nearest integer $\le *$. I'm asking myself the question what's the limit of the part of the empirical spectral distribution corresponding to the first $\lfloor{p/2}...
1
vote
0answers
16 views
Bound on the number of bridges between vertices in a sampled subgraph
I am researching connectivity in sampled subgraphs and have come across the following problem.
A bridge between two vertices $a$ and $b$ of a graph $G$ is an edge $e$ such that removing $e$ from $G$ ...
10
votes
4answers
296 views
When is a large graph with a given degree sequence likely to be connected?
Are there any results on whether a large random graph with a given degree distribution is likely to be connected?
In Erdős-Rényi graphs with $n$ vertices and $m$ edges, we have two sudden transitions ...
1
vote
1answer
95 views
Continuum percolation in 1d
What is known about continuum percolation in 1d?
By this, I mean, for $d \in \mathbb{N}$, the Poisson-Boolean model of disks of radius $r_0 \in \mathbb{R}$ with centres arranged randomly in $[0,1]^{d}...
7
votes
1answer
181 views
Graphons and Graphs
The situation is as follows: assume we have a sequence of simple weighted graphs $(G_n)_{n\in\Bbb{N}}$. For the terminology that follows I refer to Limits of dense graph sequences by László Lovász and ...
0
votes
1answer
52 views
Small subgraphs of the random graph
If I look at the distribution of the number of small subgraphs in the random graph isomorphic to a connected graph $H$, this is asymptotically Poisson.
What proportion of these small subgraphs ...
4
votes
1answer
161 views
Probability of a vertex being a “degree-celebrity” in a random graph
If $G(n,p)$ is a random graph of the Erdös-Rényi model,
what is the probability that $\mathrm{deg}(v)\gt\mathrm{deg}(u)\ \forall u\in\mathrm{adj}(v)$
Please feel free to relate answers to other ...
3
votes
0answers
48 views
Largest component and number of components of random mappings with bounded in-degree
Let $S$ be a finite set of size $n$ and consider all functions $f$ from $S$ to itself, such that the preimage $f^{-1} (k)$ obeys $0 \leq |f^{-1} (k)| \leq m$.
Let $F$ be chosen uniformly at random ...
2
votes
1answer
111 views
Electrode assignment problem in resistive networks
Main question
In the context of resistor networks, and particularly purely from a graph theory point of view, is there a consistent way of assigning the two electrode nodes in order to compare the ...
4
votes
1answer
223 views
Probability of a subset of Bernoulli's being all 1's
Suppose we have $n$ iid Bernoulli's $X_1,\ldots,X_n$ with mean $p$, and a family $\mathcal{F}$ of subsets of $[n]$. The question is how to lower bound the probability that there is a set in the family ...
2
votes
0answers
68 views
Zero-One law for Hamiltonian path subgraphs of Hamming Distance Graphs?
$(\alpha,\beta,d)$-Hamming Distance Graph $G_d(\alpha,\beta)$ for $\alpha,\beta\in(0,1]$ is a graph on $2^d$ vertices $v_0,\dots,v_{2^d-1}$ with edges $(v_i,v_j)\in\mathcal E(G_d)$ iff $0<\sum_{t=1}...
2
votes
2answers
159 views
Model for random graphs where clique number remains bounded
In the Erdös-Rényi model for random graphs,the clique number is seen to go to infinity as the number of vertices grows. Is anyone aware of models for random graphs with bounded clique number?
1
vote
1answer
77 views
Behaviour of global clustering for common random graph models
In order to develop some intuition for some of the commonly used random graph models, I've been looking at the global clustering coefficient as a means of comparing them. In particular, for the ...
6
votes
0answers
99 views
The properties of almost all directed graphs
A mathematician on the forum previously requested a reference on human brains modelled as directed graphs. This makes sense as neurons are mostly unidirectional and I have been thinking about similar ...
4
votes
1answer
111 views
Almost all simple graphs are small world networks
Two days ago it occurred to me that almost all simple graphs are small world networks in the sense that if $G_N$ is a simple graph with $N$ nodes sampled from the Erdös-Rényi random graph distribution ...
2
votes
1answer
180 views
Eigenvalues of random graphs
At time $t=0$, let $G_n(V,E)$ be a graph with $n$ vertices and $m < n$ edges. Then there exists a unique symmetric adjacency matrix $A_n$ associated with $G_n(V,E)$, defined as follows: $a_{ij} = 1$...
0
votes
0answers
34 views
Giant component in continuum random graph
Is there some similar statement to Giant component theorem for the infinite graph (particularly with continuum vertices)?
0
votes
0answers
76 views
Random graphs - multiple giant components
For a given random graph, a connected component that contains a finite fraction of the entire graph’s vertices is called giant.
A well known result in random graphs is the existence and uniqueness of ...
2
votes
2answers
73 views
Is there a way to generate a graph of specified treewidth
The treewidth is a parameter of the graph that describes its similarity to a tree. Treewidth is NP-hard to find. For the introduction please see wikipedia
The question is how to generate interesting ...
3
votes
1answer
63 views
Difference of pseudoinverse bound under assumptions
This seems like a standard problem, but unable to find a solution online.
Suppose we have two singular PSD matrices A and B with the following assumptions:
$ 0 < x \leq ||A|| \leq y$
$ 0 < ||...
3
votes
1answer
290 views
Asymptotic formula for the number of connected graphs
It can be shown that the set of graphs with $N$ vertices $G_N$ has cardinality:
\begin{equation}
\lvert G_N \rvert = 2^{N \choose 2} \tag{1}
\end{equation}
Recently, I wondered how much bigger $\...
2
votes
0answers
17 views
Edgeweight-Conditions for “Statistically Self-similar” Complete Weighted Graphs
Given a complete symmetric weighted graph with $n$ vertices, for such a graph there always exists a minimum spanning tree and, under the assumption of the uniqueness of that tree, the vertex degrees ...
1
vote
2answers
104 views
How to use probability to find a matching in a family of graphs?
In a conference, I heard that we can use some probabilistic methods to find a matching in some kind of graphs. I would like to see some examples of such technics. Can someone provide some references ...
2
votes
2answers
161 views
Modularity in a graph — derivation of modularity score
Background
I am currently reading "Modularity and community structure in networks" (2006) by Newman [1].
In it, he derives a score for the modularity of a graph ...
2
votes
0answers
36 views
Transversal deviation in first passage percolation
Take the lattice $\mathbb{L}^{2}=(\mathbb{Z}^{2},\mathbb{E}^{2})$ with i.i.d. $\text{U}[0,1]$ weights on the edges, and the random variable $D$ giving the maximal transversal deviation of the geodesic ...
3
votes
1answer
88 views
Expected size of matchings in a cubic graph
Let $G$ be a random cubic graph on $n$ vertices. Let $M$ be the set of (not necessarily maximum) matchings of $G$. What is the expected size (i.e. number of edges) of an element of $M$?
In other ...
1
vote
1answer
89 views
Figuring out a consistent definition for the percolation backbone
In the context of percolation, e.g., bond/site percolation, random graph connectivity in 2-3 dimensions, etc., once the percolation threshold is reached, that is the system is spanned by an infinite ...
5
votes
1answer
202 views
Switching oriented paths in a graph
Consider an oriented graph (e.g. a finite part of the standard grid with some random orientations).
Each minute the following operation takes place: we choose uniformly randomly an ordered pair $(A,B)...
1
vote
1answer
56 views
What is the expected distance between the sides of a random subgraph of the grid?
Let $G$ be the $n \times n$ grid, in which each vertex is connected to the vertices above it, below it and on either side. Let $G_p$ be the random subgraph of $G$ obtained by keeping each edge with ...
4
votes
1answer
350 views
Open Problems in Random Graphs [closed]
I am a PhD student in mathematics. I'm interested in probabilistic methods in combinatorics and especially random graphs. I am looking for an open problem in this area for my PhD proposal. I know that ...
0
votes
2answers
131 views
Random Optimization on Graphs: Minimum Cut
Consider a complete graph on $n$ vertices. To each edge, $(i,j)$, we assign a weight, $W_{ij}$, which comes from some known distribution iid. Then, we ask the following question. Among all (weighted) ...
