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.

  • $\begingroup$ Are you talking about en.wikipedia.org/wiki/Watts_and_Strogatz_model ? $\endgroup$
    – Xoff
    Commented Dec 10, 2013 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$ Commented Dec 11, 2013 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
    Commented Dec 11, 2013 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$ Commented Dec 12, 2013 at 10:12
  • $\begingroup$ in your matrices, how do you choose if there is a $0$ or a $1$ ? $\endgroup$
    – Xoff
    Commented Dec 12, 2013 at 10:33

1 Answer 1


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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .