0
votes
1answer
40 views

How would you incorporate probability into this graph theory problem?

A non-closed path is chosen at random on the complete graph K9. All paths are equally likely. What is the probability that the path contains the edges {23} and {34} given that it is length 6? Given ...
0
votes
0answers
18 views

Q: Finding probability of connection based on distance?

So, I am new to graph theory and statistics but have encountered a problem that I am not exactly sure how to solve. I have a graph with n nodes and am trying to determine the probability of connection ...
3
votes
0answers
68 views

Minimal number of edges removed to make a graph triangle free

I'm interested in finding an upper bound on the expected value of the minimal number of edges one needs to remove from a random graph $G_{n,p}$ (where each edge appears with probability $p$) in order ...
0
votes
1answer
30 views

How to compute a marginal probability

Given a weighted graph, using the Kirchhoff's matrix tree theorem, how can I compute the marginal edge presence probability: $$P_\beta(ij)=Z_\beta^{-1}\sum_{\text{T spanning tree:$(i,j)\in ...
22
votes
1answer
393 views

Zombie outbreak on a $k$-regular graph

Suppose we have a zombie outbreak on a connected $k$-regular graph of order $n$. There are $n_0$ initially infected zombie nodes, and each turn, each zombie infects its neighbors with probability ...
2
votes
0answers
31 views

Probability that half the nodes has more than half out-degree

This is something I just wondered about, and I don't know whether there is a closed-form answer or not. I've tried but without making progress, so any idea would be helpful. Consider a complete graph ...
0
votes
0answers
34 views

Proving properties of Random Graphs

I am asking the question on a slightly abstract level and it may depend on the specifics but it would be great to have related references or ideas. Consider the random graph model $G_{n,p}$ where its ...
3
votes
1answer
36 views

Is this perfect matching probability game really open?

A friend of mine heard from a friend of his of the following problem that my friend's friend claims remains open? The game is as follows: There are 100 persons with different names, their names are ...
1
vote
1answer
28 views

Random graphs question regarding exponents

On page 19 http://www.iecn.u-nancy.fr/~chassain/GDT/documents/SpencerStFlour.pdf All in the first Paragraph. it gives an estimate of (they use equal instead of approximation) ...
0
votes
1answer
38 views

Identity in the 9 lectures in random graphs

In the 9 lecures in random graphs on pages 16/17 http://www.iecn.u-nancy.fr/~chassain/GDT/documents/SpencerStFlour.pdf they say let $n_{0}(k)$ be the minimum $n$ for which $\binom{n}{k} ...
5
votes
0answers
69 views

Probability of transmission between two nodes in a neural network at exactly d timesteps

I have a network which is an Erdős–Rényi graph. It is a simple neural network with degree 0.7N where N is the number of nodes. Each weight between neurons is 1/N, meaning that if node n has fired the ...
0
votes
0answers
11 views

Appearance of small subgraphs

I had a quick question regarding top of page 16 in the '9 lectures in random graphs' http://www.iecn.u-nancy.fr/~chassain/GDT/documents/SpencerStFlour.pdf It says there are $O(n^{2v-j})$ choices of ...
0
votes
1answer
37 views

Random Graphs correlation inequalities

Is there anywhere i can find a proof of the first inequality that $$P(B_{i}| \cap_{j \in J} \bar B_{j}) \leq P(B_{i})$$ It is on page 13 and is the first inequality presented at the start of section 2 ...
0
votes
0answers
35 views

Average Degree of a Random Geometric Graph

A set of $N$ points are distributed randomly on a unit square with uniform distribution. Two points $\mathbf{p}_i$ and $\mathbf{p}_j$ are said to be connected if $\|\mathbf{p}_i - \mathbf{p}_j\| \leq ...
1
vote
2answers
30 views

Random (Union Find) Spanning Tree, probability of resulting with two unconnected halves before the last step?

Let N be a large even positive integer. We start with a set of singletons from {1}, {2} ... to {N}. In each step we randomly pick two integers and merge the sets that contain them. We continue until ...
2
votes
2answers
69 views

Random walk on tree

You begin at a root node that has 2 children. Each of those two children have two more children, and each of those children have two final children (i.e., there are 15 nodes in the graph). How do I ...
1
vote
1answer
29 views

Threshold for apperance of quite short paths/cycles in random graphs

We say that a graph $G$ is distributed with $\mathcal{G}_{n,p}$ if it is a graph on $n$ vertices, and for which each of the ${n\choose 2}$ possible edges is chosen independently of the other edges and ...
1
vote
1answer
51 views

Confusion about an algorithm making a choice between two options, with probabilities.

I am totally puzzled at grasping the meaning of "we move to B with probability P1 OR we move to C with probability P2" in the following scenario. A,B,C are points in a 64-dimensional space. Reading ...
1
vote
1answer
56 views

Predicting the number of simple circuits in a graph

If I have a directed graph with $n$ vertices, and the mean number of out-edges per vertex is $x$, what is the expected number of simple circuits that will be found in the graph? What happens to the ...
5
votes
1answer
64 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
2answers
57 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
23 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
50 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
40 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
50 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
157 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
27 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
1answer
67 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 ...
5
votes
0answers
77 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
38 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
47 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
31 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 ...
2
votes
1answer
32 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
24 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
78 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
40 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
30 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
35 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 ...
9
votes
0answers
261 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
59 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
45 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
54 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
45 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
77 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
49 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
34 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
48 views

Proof of the Surfer Model Pagerank formula

How do you prove this formula for the Surfer Pagerank algorithm mathematically? ...
1
vote
1answer
89 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
56 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
131 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 ...