The study of probability distributions over graphs. For example, the Erdős–Rényi model where each edge occurs independently with equal probability.

learn more… | top users | synonyms

0
votes
0answers
25 views

Critical probability, bond percolation on triangular lattice

Let G a graph and $p_c(G)$ the critical probability of bond percolation. Let G be a triangular lattice then $p_c(G) = 2\sin(\frac{\pi}{18})$ (Grimmett, Percolation p.65). Ramanujan find this formula : ...
0
votes
0answers
100 views

Ramanujan graphs and stable real polynomials

I have a problem with the lemma 6.5 and the theorems 5.1, 6.6 in the paper of Adam Marcus, Daniel Spielman and Nikhil Srivastava. http://arxiv.org/pdf/1304.4132.pdf I do not understand how they use ...
-1
votes
0answers
41 views

Graph theory - degree distribution

What is the relation (if there is one), between the probability to have an edge, to the degree distribution of a graph. For example: A graph that was created by Waxman model, the probability for an ...
4
votes
2answers
139 views

first order languages over graphs (and other discrete models)

A lot of research has been devoted to the study of first order language of graphs (FO). Formulas in this language are constructed using variables $x, y,\dots$ ranging over the vertices of a graph, the ...
2
votes
1answer
146 views

Proofs of inequalities used by Erdos-Renyi in their Random Graphs Paper 1

Please refer to this, it is Erdos-Renyi 1959 paper 1 on Random Graphs. I am currently working on this, but I am stuck on the fifth page, where they use two estimates. More specifically, here's the ...
4
votes
3answers
114 views

Repository of graph classes that are tough to test non-isomorphic pairs from isomorphic pairs

(1) Which graph classes are extremely tough to test for graph non-isomorphic pairs from isomorphic pairs? (2) Is there a repository of adjacencies from such classes?
3
votes
2answers
87 views

Database of adjacency matrices on cospectral non-isomorphic graph pairs

Is there a repository of cospectral non-isomorphic graphs available somewhere? I am looking for list of $0/1$ adjacency matrix pairs that can be input data in tools such as MATLAB.
3
votes
0answers
120 views

In a random graph which one is more probable, $k$-clique or $k$-core?

Recall that the $k$-core of a graph $G$ is the unique maximal subgraph of $G$ with minimum degree at least $k$. In an Erdos-Renyi random graph, where the edge selection is independent with ...
2
votes
0answers
56 views

What is the gap between the two defined distances from node to node in a random graph?

Give a sparse random graph $G=(V,E)$, every edge $(u,v)\in E$ is associated with a weight $w(u,v)$. We assume each $w(u,v)$ is geometrically distributed with parameter $p_{u,v}$. The weight of a path ...
3
votes
0answers
119 views

Edit distance vs. canonical adjacency matrix distance

Let $G$ and $G'$ be two simple random graphs on the same set of nodes. Let $d_{edit}$ be the edit distance between $G$ and $G'$. Let $\mathbf{A}$ and $\mathbf{A'}$ be the adjacency matrices of the ...
5
votes
0answers
49 views

Full distribution of FPTs in random walks on graphs

There is a lot of published research on the mean passage passage time (FPT) for random walks on various types of graphs. How about the variance of the FPT and higher momenta? In fact, I would be ...
3
votes
1answer
156 views

Number of nodes in a given distance in (random) regular graph

Given a d-regular graph $G=<V,E>$ (connected, unweighted & simple), and a node $v$. denote all nodes with distance $k$ from $v$ $$L_k=\{u\in V : dis(v,u) = k\}$$ Let's call it "the k-th ...
1
vote
1answer
87 views

Probability of having no cycles of fixed length in $d$-regular graphs

According to this paper, the probability that a random $d$-regular graph of order $n$ has no cycles of length $c_1,c_2,\ldots,c_t$ is $$P=\exp\left(-\sum_{i=1}^t\mu_i+o(1)\right)$$ as ...
11
votes
2answers
208 views

What are some useful invariants for distinguishing between random graph models?

Quite a few probabilistic algorithms for generating random graphs exist in the literature, such as: The Erdős-Rényi model The Stochastic Block model The Watts-Strogatz model The Barabasi-Albert ...
3
votes
1answer
112 views

Good broad review of agent-based modeling? [closed]

Trying to find some good review of agent-based models and networks, specifically models that are defined by a graph of interacting nodes, that covers analysis of collective behavior based on model of ...
1
vote
1answer
206 views

Can we estimate the probability $\mathbf{P}(a-k|a - b) $ on a random graph?

Let $G=(V,E)$ be an undirected random graph such that $V$ is the set of nodes, and $E$ is the set of edges Assume the ground graph $G$ is sparse enough, for example, $\frac{|E|}{|V|}= c \in [10, ...
2
votes
0answers
51 views

Modularity in a graph - definition of the random component

This question concerns the definition of modularity in a graph. Consider a simple, undirected, unweighted graph $G$ with vertices in set $V$ and edges in set $E$ . Between any two vertices there is ...
5
votes
0answers
105 views

Does squaring a directed random graph more than double its out-degree?

As far as I know, it is an unsolved question whether or not this is true: If $G$ is a directed an oriented graph, $G^2$ always has some node whose outdegree is at least double that of its ...
1
vote
0answers
40 views

Weak law for component count of Erdos-Renyi random graphs

Penrose and Yukich derive a weak law for functionals of binomial point processes, which implies a law of large numbers for the component count of random geometric graphs. Do similar results exist for ...
5
votes
1answer
155 views

Modification of matching

Suppose i have an $n \times n$ random bipartite graph and suppose that i repeat the following process $n$ times. At the start (stage 1) each edge is selected independently with probability $p(n)$, and ...
0
votes
0answers
223 views

Gromov-Hausdorff distance measure between minimum spanning trees

I am trying to compare minimum spanning trees through time. I have two questions: 1-Is it possible to measure the similarity between two minimum spanning trees with Gromov-Hausdorff distance measure ...
0
votes
0answers
46 views

Cardinality of maximum independent set for a given degree distribution

Consider an undirected graph $G(V,E)$. Let $f_n(k)$ be the probability mass function of the degree of a vertex in $G$. Further, assume that $f_n(k)$ is a strictly decreasing function of $k$ with very ...
2
votes
2answers
165 views

Probability of relations in network

Imagine, i have a predicate $\text{friends}(x_1, x_2)$ and I know that $p(\text{friends}(x_1, x_2)) = p_2$. If I generate a world of $n$ people ($x_1$ to $x_n$), I expect there to be $\binom{n}{2}p_2$ ...
1
vote
1answer
182 views

Random graphs with boundary in a game (Tsuro)

Suppose we have an $n \times n$ board and we have $n^2 - 1$ square tiles. These tiles consist of a 8 vertices, two on each edge, and every vertex is connected to precisely one other vertex. These ...
7
votes
2answers
780 views

random category theory

This question is in some sense dual to the one asked in Is there an introduction to probability theory from a structuralist/categorical perspective? since contrary to the OP who asks for references ...
3
votes
1answer
243 views

Expected number of leaf nodes in some theoretical graph models

If a leaf node of a graph refers to a node having the degree of 1, how can one compute the expected number of leaf nodes of: (A) a random graph (e.g., Erdos-Renyi graph), (B) a small-world graph ...
7
votes
1answer
224 views

Probability of a graph procedure

We are going to build $K_n$ one edge at a time. Begin with the empty graph on $n$ vertices. Take a random permutation of the edges of $K_n$ and, one at a time, place the edges onto the graph (so, ...
4
votes
2answers
317 views

Statistics of strongly connected components in random directed graphs

I'm interested in the statistics of strongly connected components in random directed graphs. However, I'm unable to find any results on this, partly because I don't know the terminology to search for. ...
5
votes
1answer
90 views

Probability of a giant component existing in a $G(n,p)$ random graph with $p=\omega(\frac 1n)$

Consider a random $G(n,p)$ graph where $p=\omega(\frac 1n)$, and let $x$ denote the probability that the graph has a connected component of size linear in $n$. It is well known that $x$ tends to $1$ ...
1
vote
0answers
120 views

Multiple Bipartite graphs and matchings

I've been told recently that it's better i just for help regarding my 'specific' problem rather than lots of little questions around the same topic which appear somewhat unclear. I would first like to ...
1
vote
2answers
319 views

Expected matching in a bipartite graph

Consider a random bipartite graph constructed on vertex classes of size $n$ with each edge present independently with probability $p$. How could I go about calculating the size of the expected ...
1
vote
1answer
223 views

Threshold for perfect Matchings in Bipartite graph

Consider the random bipartite graph with vertex classes of size $n$ and each edge being present independently with probability $p(n)$. I know one way to prove the threshold of a perfect matching is ...
1
vote
2answers
248 views

Proving a random bipartite graph contains a perfect matching

I have the following problem consider a random bipartite with vertex classes $A$ and $B$ of size $|A|=|B|=\mathrm{log}^{2}(n)$ graph in which every possible edge is chosen independently with ...
0
votes
0answers
66 views

Computation on Random Bipartite graphs

I'm looking at a random bipartite graph $K_{\omega(n)}*K_{\omega(n)}$ where $\mathrm{log}(n)\leq \omega(n) \leq n^{1/2}$, in which each of the $\omega(n)^{2}$ edges is placed randomly with probability ...
1
vote
0answers
73 views

Matchings in random bipartite graphs

I was wondering if anyone could point me in the direction of a text or paper which would help deal with the following problem Suppose i am given a $K_{\mathrm{log}(n)} \times K_{\mathrm{log}(n)}$ ...
1
vote
1answer
166 views

Probability of each edge in K-clique [closed]

For $c \in R$ and $k \in N$, $k \geq 3$ let $p_{k,c} := n^{\frac{−2}{k+1}}log^c(n)$. I would like to prove that exists $c\in R$ such that every edge in the random graph $G(n,p_{k,c})$ lies in a copy ...
4
votes
0answers
200 views

Navigation in a graph

The problem Let $G=(V,E)$ be a graph. $k = O\left(\log(|V|)\right)$ distinct vertices are picked randomly from $V$. We call the set of chosen $k$ vertices $T$. Assumptions about the graph: You may ...
0
votes
1answer
361 views

Poisson approximation of random sub-graphs

I add the edges of $G(n)$ the complete graph on $n$ vertices one by one, at random and without replacement, and denote by $G(n,m)$ the resulting Erdos Renyi random graph process. At step $m$ in the ...
9
votes
5answers
381 views

Do there exist sparse graphs with large crossing number?

Does there exist a sequence of graphs $\{ G_n \}$ such that $G_n$ has $n$ vertices, the number of edges of $G_n$ is $O(n)$, and the crossing number of $G_n$ is $\Omega(n)$? In particular, do ...
5
votes
1answer
370 views

Expectation of ratio of functions of i.i.d. Bernoullis: a concentration question

Consider the following $n \times n$ symmetric matrix of i.i.d. Bernoulli random variables, $X_{ij}$. For $i=1,...,n$ and $i<j\le n$. Let $X_{ij} \sim \text{Bernoulli}(p)$ when $i \ne j$ ($p$ ...
2
votes
0answers
50 views

“drift” of a random graph $G(n,p)$ with $p=\alpha\ln{n}/n$

Suppose $G\sim G(n,p)$ with $p=\alpha\ln{n}/n$ for some large constant $\alpha$. I wish to show a certain "drift" property of $G$, which can roughly be phrased as follows: if $u$ is "not that far" ...
3
votes
2answers
196 views

Independent Sets in random geometric graphs

I was wondering if a lot is known about independent sets in Random Geometric graphs? Most google searches don't bring up much. In addition I'm interested in any algorithms used for finding independent ...
2
votes
1answer
224 views

Finding loops and double edges ASAP in configuration model random graph

A common approach (at least in theory) to generating a random $n$ vertex graph uniformly subject to having a given (feasible) degree sequence $(d_i)_{i = 1}^n$ is to use the configuration model, i.e. ...
3
votes
1answer
84 views

Hamiltonicity of random graphs with high girth

We say that $G\sim G_{n,f}$ (for $f=f(n)$) if $G$ is chosen uniformly at random from all graphs on $n$ vertices with girth $g(G)\ge f(n)$. Is there any threshold function $F(n)$ such that when $f\ll ...
11
votes
0answers
370 views

First passage percolation on a random geometric graph in the large connectivity limit

Let $V_\rho\subset\mathbb{R}^2$ be a point set in the plane obtained from a Poisson process of density $\rho$. The random geometric graph $G_\rho$ is obtained from $V_\rho$ by connecting points that ...
3
votes
1answer
150 views

limiting empirical spectral distribution of the Laplacian matrix on an Erdos-Renyi graph?

Let $G$ be an Erdos-Renyi random graph (i.e. an edge ($ij$) exists with probability $0 < p < 1$ and all edges are independent). Let $L$ be the Laplacian matrix of this graph (i.e $L=D-A$, where ...
3
votes
0answers
98 views

Node covering in a random graph

Given $N$ nodes randomly placed in a $D\times D$ area, i.e., the position of each node is randomly chosen. Assume that both $N$ and $D$ are sufficiantly large. An agent can move in the area at ...
0
votes
2answers
97 views

different way of selecting a random graph

Consider having a 'base' graph $G=(V,E)$ and selecting each vertex with independent probability $p$ and having the induced subgraph of $G$ with all 'selected' points as your random graph. Has this ...
6
votes
2answers
158 views

Convergence on a random graph

Assume a directed graph $G = (V,E)$ is drawn from a random graph distribution, for instance Erdős–Rényi's $G(n,p)$ (but with directed edges). Let $S:V\rightarrow\mathcal{P}(V)$ be the direct ...
5
votes
1answer
406 views

Expected number of connected components in a random graph

For a random graph G(n,p) what is the expected number of connected components? What is the probability distribution of this value? I'm specially interested in what happens for small values of p, ...