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.
Best Answer
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.