5
votes
1answer
37 views

Probability of finding a Hamilton circuit in a graph

In short, I would like to know either/both the probability that there exists a Hamiltonian circuit within a graph, or the number of circuits expected to exist. (Without actually finding all the ...
0
votes
0answers
27 views

Erdos-Renyi Model Intuition

I was reading the Wikipedia article on the Erdos-Renyi model and I was wondering how they came up with the probability for each connection. I see that there are $n \choose 2 $ nodes to check out, but ...
0
votes
2answers
40 views

Expected Value with graph theory

A group of $n\geq 3$ people is sitting at a round table, so that each person has two neighbors,one clockwise neighbour and one counter clockwise neighbour. Each person flips a fair and independent ...
0
votes
0answers
20 views

probability in graphs - degree distribution

I am reading this paper on networks which employs probability in analyzing graphs. Suppose that a graph has $n$ vertices. Furthermore, if each vertex has a probability $p_k$ of having $k$ neighbors, ...
1
vote
1answer
38 views

Probability that exists at least an edge in the configuration model

In this period, I am studying some topics on random networks to understand the modularity optimization used in community detection. In particular, I am trying to understand a model called ...
0
votes
0answers
34 views

Expected number of steps in a random graph walk

Suppose I have a directed graph $D(V, A)$ where the edges have weights on them. Let's notate the weight function $w: A \rightarrow [0, 1]$. If $f, t \in V$ and $a \in A$ such that $a = (f, t)$ then ...
0
votes
1answer
44 views

Probability of random walk traversal

Consider a random walk on an connected, non-bipartite, undirected graph G. Show that, in the long run, the walk will traverse each edge with equal probability. Note: The walk can traverse each edge ...
10
votes
1answer
135 views

Probability that a random graph is planar

I've been attempting to solve the following challenge problem from a combinatorics class but am getting absolutely nowhere. Prove: For sufficiently large $n$, the probability a random graph ...
1
vote
0answers
19 views

Conditional covariance in gaussian graphical models

I have a hypothesis, but I'm not sure if its true. The Wikipedia page states that if the covariance matrix is given by $$\Sigma=\left[\begin{matrix} A & B \\ B^T & C \end{matrix}\right]$$ ...
4
votes
0answers
47 views

Random embedding of $K_4$ in the unit square

Suppose I embed $K_4$ (the complete graph on 4 vertices) randomly in the unit square (using the uniform distribution for the positioning of the vertices). $K_4$ is planar, but not any embedding of it ...
4
votes
0answers
60 views

Spectral gap of mixture of Markov chains

Context Let $P$ be the transition matrix of an irreducible, aperiodic, discrete-time Markov chain. The spectral gap is given by $$\xi = 1 - \lambda_\max$$ where $\lambda_\max = \max\{\lambda_2, ...
1
vote
0answers
33 views

A question regarding a prefix code

Let $C=\{ c_1, c_2, \dots, c_m \}$ be a set of sequences over an alphabet $\Sigma$ and $|\Sigma|=\sigma$. Assume that $C$ is a prefix-free code, in the sense that no codeword in $C$ is a prefix of ...
1
vote
0answers
36 views

Probability that the network is connected in an unstructured p2p network

Suppose that three nodes form an unstructured p2p network (a network where each node has a list of neighbors node, in which there are addresses of c live neighbors) and each selects to cache the IP ...
1
vote
0answers
25 views

Number of Isolated Edges in G(n,p)

I am attempting to find the number of isolated edges in the Erdos - Renyi graph G(n,p). I need to find the formula for the expected number of isolated edges. I've broken the equation down into ...
0
votes
0answers
21 views

uniform spanning tree of $2 \times n$ graph

In Probability on Trees and Networks Chapter 1 study the uniform spanning tree on the ladder graph: _ |_| |_| |_| ... |_| |_| The probability the bottom rung ...
1
vote
0answers
23 views

Probability of inter-group links in a network with maximum degree 1

In an undirected network, there are two groups of nodes. Group 1 has N1 nodes, and group 2 has N2 nodes. The links in the network are generated following such rules: (1) The maximum degree is 1, ...
2
votes
0answers
74 views

Expected size of intersection in a scale-free directed graph

Let $W$ be the Wikipedia graph, in which every page $p_i$ is represented by a vertex $v_i$, and there is a directed edge between two vertices $v_i$ and $v_j$ if page $p_i$ links page $p_j$. This ...
0
votes
0answers
38 views

How to formalise a probabilistic model for graph with nodes and edges attributes

Let $G = (V, E)$ be a graph with $V$ being events and $E$ connecting events with participants in common. Each node $V_i$ have two discrete attributes: size $S_i$ (the number of participant) and time ...
0
votes
1answer
29 views

probability of embeddings in graph

Setup: Let G be a graph on n vertices. Between each pair of vertices, with probability p there is a blue edge, and with probability 1 − p a red edge. Question: Triangle distributions Let T be a ...
0
votes
0answers
34 views

count embeddings in graph

Setup: Let G be a graph on n vertices. Between each pair of vertices, with probability p there is a blue edge, and with probability 1−p a red edge. Expected number of embeddings: Let H be a graph on ...
8
votes
0answers
192 views

Expected value of the distance square

Given two points $X,Y$ on two sides of square $[0,1]\times [0,1]$ ($X:(0,1/2),Y:(1,1/2)$ (PS: My original question is $X,Y$ on opposite of a square, but I think that's not the real case) )and $n$ ...
0
votes
1answer
33 views

Probability of having a complete random graph

What is the probability that a random graph G(n,p) with n nodes and probability p = c some constant value is complete? By complete I mean that every pair of nodes ...
1
vote
1answer
41 views

Number of vertices of degree 1 - Expectation and Variance

Let $G\in G(n,p),0\le p\le \binom n 2=N$ where $G(n,p)$ consists of all $\binom N p$ subgraphs of $K_n$ with $p$ edges. Now let $X$ be the number of vertices of degree $1$ in $G\in G(n,p)$. Why is ...
1
vote
0answers
48 views

zarankiewicz problem lower bound

I was just reading through the following article: http://page.mi.fu-berlin.de/szabo/PDF/stoc96.pdf On page 2 they give an explicit formula for the lower bound of the size of the graph. Summary: We ...
0
votes
1answer
36 views

If almost all random graphs $G \in g(n,p)$ have property $P_1$ and $P_2$ then almost all graphs have property $P_1 \cap P_2$

If almost all graphs $G \in g(n,p)$ have a graph property $P_1$ and almost all graphs $G \in g(n,p)$ have a graph property $P_2$ then almost all $G \in g(n,p)$ have the property $P_1 \cap P_2$. ...
1
vote
0answers
46 views

what are the advantages and disadvantages of Belief propagation

Belief Propagation cannot solve the graphical model which has cycles. For undirected graphical model for example MRF and CRF in computer vision area, in which cases the model has no cycle ? As far as ...
1
vote
1answer
48 views

A probabilistic problem in graphs

Let $G$ be a (simple) graph. Each edge will be deleted or will be reminded with probability $\frac 12$ (independent from the other edges). Let $P_{AB}$ be the probability that (after this process) the ...
0
votes
1answer
21 views

Find out the probability of a path break for an eight-hop path given that the probability of a link break is p?

Can we apply Binomial distribution here? How do I approach it? How the method will change when topology change from linear to ring topology?
1
vote
0answers
45 views

Proof of the Surfer Model Pagerank formula

How do you prove this formula for the Surfer Pagerank algorithm mathematically? ...
1
vote
1answer
80 views

Given G an Undirected Graph with > 3 Vertices(V). Prove that V Can Always be of 3 Colors Such that at Least 2/3 Edges don't Connect V of Same Color

Let $G$ be an undirected graph with $n>3$ vertices and $m$ edges. $\text{Edges} = \{ (i_{i} < j_{i}), \dots, (i_{m} < j_{m}) \}.$ Prove that we can always color vertices in 3 colors such that ...
0
votes
1answer
43 views

Degree distribution of a graph

Given a graph, what is the degree distribution of the same? Is degree distribution the same as a histogram of the degrees? As in, is the degree distribution a plot of the number of nodes that have a ...
0
votes
1answer
98 views

Probability of a node being connected to another

I am a newbie tinkering around with graph theory. Please pardon me for asking something very basic. Let us say I have a graph with n number of nodes. I have a binary adjacency matrix that specifies ...
3
votes
0answers
71 views

How many edges does an Erdős-Rényi graph have to have, to almost surely have a component with multiple cycles?

An Erdős-Rényi graph is a random graph, selected according to the distribution obtained one where we have some number $n$ of nodes, and some probability $p$ of each potential edge being ...
8
votes
2answers
272 views

Exact probability of random graph being connected

The problem: I'm trying to find the probability of a random undirected graph being connected. I'm using the model $G(n,p)$, where there are at most $n(n-1) \over 2$ edges (no self-loops or duplicate ...
7
votes
2answers
239 views

Probability that a vertex in the spanning tree of an $N$ x $N$ grid graph is a leaf

Suppose we have an $N$ x $N$ grid graph $G(V,E)$ and we construct a spanning tree of this graph in the following way. Start with a set $S$ which contains only the vertex at the top left corner of the ...
11
votes
1answer
266 views

What am I getting for Christmas? Secret Santa and Graph theory

I live with four people, who thankfully don't spend much time on maths.se. We decided this year that we'd do a Secret Santa. We can represent the arrangement of who's buying for whom using a directed ...
0
votes
1answer
101 views

Distribution of connected components in a Random Graph with fixed number of edges

Given $N$ vertices, I am interested in the distribution of the size of connected components of the random graph formed by assigning $M$ edges to randomly chosen pairs of vertices so as to form a ...
1
vote
0answers
100 views

Probability of having a path of a given length in a random graph

Suppose $G=\langle V,E \rangle$ is a directed graph consisting of $n\in \mathbb{N}$ vertices. Vertex $v_i \in V$ has an edge to vertex $v_j \in V$ with a probability of $P(i, j) = f(|i-j|)$ where $f$ ...
1
vote
1answer
387 views

Expected number of simple, unordered cycles in a random graph

Consider an undirected random graph of $n$ vertices. The probability that there is an edge between a pair of vertices is $\frac{1}{2}$. What is the expected number of simple (no vertex more than ...
2
votes
0answers
94 views

Building Bayesian Networks, Causality and Cyclic Reasoning

I am studying Bayesian Statistics and I am trying to get a good understanding on Bayesian Networks, which seems to be vital in order to make something useful in Machine Learning. Most of the texts I ...
1
vote
0answers
66 views

Expected distance traversed between 2 vertices on probabilistic graph

Let $V = \{1,2,3,...,N\}$ be the vertex set of a graph. Let $d(i,j)>=0$ represent the $(i,j)$ vertex distance between vertices $i$ and $j$, $i \in V, j \in V$. Now, define a non-negative number ...
0
votes
0answers
45 views

Expected size of the largest cycle

Assume that given $n$, a graph $G$ is created randomly, so that each point is directed to any of the $n$ points (including itself) at random. (So self loop is possible.) Then $G$ is graph of $n$ ...
0
votes
2answers
114 views

Mathematical formula to find adjacent items in a grid

I have a 3x3 grid of dots. Selecting any one of the 9 dots, I need to find out which of the remaining dots are adjacent to the first dot. So, if for example we chose the first dot in the first row ...
2
votes
1answer
99 views

Square of the expectation of number of edges not in a triangle in random graph

The following question is from page 27 in the book Graphical Evolution, An introduction to Theory of Random Graphs by Edgar M. Palmer. I feel that my argument is correct (who doesn't?), but the answer ...
1
vote
1answer
79 views

Length of longest path in Erdos Renyi graph

Is it possible to compute the expected length of the longest simple path in an Erdos-Renyi graph or even the probability density function of this length?
6
votes
1answer
132 views

Probability that a random edge coloring of the complete graph is proper

Suppose we color the edges $\{1,\ldots, {n \choose 2}\}$ of the complete graph on $n$ vertices with $m$ colors each edge being assigned a color picked uniformly at random from $\{1,\ldots, m\}.$ I ...
-1
votes
2answers
82 views

Simple Paths Along Vertices

Let $v$ and $w$ be distinct vertices in $K_n$, $n\geq 2$. Show that the number of simple paths from $v$ to $w$ is $$(n-2)!\sum_{k=0}^{n-2}\frac{1}{k!}.$$ A path with no repeated vertices is called a ...
2
votes
2answers
93 views

How to pick a random node from a tree?

How can I pick a random node from a tree, given the following constraints? We are given the root of the tree, and at every node we are given its children nodes. But we do not know what its children ...
3
votes
1answer
75 views

Probability that one random graph is contained in another

Let $G_{n,p}, n\in \mathbb{N}, p\in(0,1)$ be the binomial random graph, i.e. a graph on $n$ vertices where an edge is in $G_{n,p}$ with probability $p$. For some $q\in(0,1)$, what is the probability ...
3
votes
1answer
91 views

Randomly adding nodes to a connected graph

Assume you have an n node connected graph. Repeat the following m times: choose a random set of nodes by selecting each existing node with probability p, then add a new node to the graph and join ...