2
$\begingroup$

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 how these nodes are connected to each other (a 1 if node i is connected to node j and 0 if the connection does not exist).

Now, I would like to calculate the probability of a node being connected to another. What do we exactly mean when we say the probability of a node being connected to another and how can I calculate the same? How can we say that an edge connecting i and j nodes has a probability p?

The question came when I was trying to generate a random graph. Given a number of nodes n, I was supposed to also specify the "wiring probability", which I could not make sense of.

$\endgroup$
  • $\begingroup$ Are you talking about en.wikipedia.org/wiki/Watts_and_Strogatz_model ? $\endgroup$ – Xoff Dec 10 '13 at 9:07
  • $\begingroup$ Hi @Xoff! The question stands irrespective of the type of graph being considered. "For any graph, what is the probability of a node being connected to another" would be the base line question. P.S: I was trying to generate an ER random graph when the question came up $\endgroup$ – Pravesh Parekh Dec 11 '13 at 12:17
  • $\begingroup$ When you ask, "what is the probability ?", you need to explain how you obtain a graph, or what is your measure. $\endgroup$ – Xoff Dec 11 '13 at 14:48
  • $\begingroup$ Hi @Xoff. Apologies for the missing details. From a time series data, I have created an adjacency matrix of partial correlations. Thus, the measures are partial correlation values between various time series variables. What about the case of unweighted matrix (having ones and zeros only)? $\endgroup$ – Pravesh Parekh Dec 12 '13 at 10:12
  • $\begingroup$ in your matrices, how do you choose if there is a $0$ or a $1$ ? $\endgroup$ – Xoff Dec 12 '13 at 10:33
1
$\begingroup$

A simple way to generate a random graph $G$ with (deterministic) vertex set $V(G)=\{1,2,\ldots,n\}$ and random edge set $E(G)$ is to decide randomly whether each $(i,j)$ in $V(G)\times V(G)$ belongs to $E(G)$ or not. In a familiar model for the undirected case, one decides independently and with the same probability $p$ that $\{i,j\}$ belongs to $E(G)$, for each $i\ne j$ in $V(G)$ (and usually no $\{i,i\}$ is in $E(G)$). Thus, the adjacency matrix is symmetrix, each diagonal entry is zero, each off-diagonal entry is $1$ with probability $p$ and $0$ with probability $1-p$, and the off-diagonal entries above the diagonal are independent. This is called the Erdős–Rényi model and is a work-horse of the domain.

$\endgroup$
  • $\begingroup$ The probability p is chosen arbitrarily? $\endgroup$ – Pravesh Parekh Dec 18 '13 at 7:05
  • 1
    $\begingroup$ Yes. As explained on the WP page. $\endgroup$ – Did Dec 18 '13 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.