In an application, I have to create a graph with $n$ specific types of nodes. A node of type $i$ has at most $e_i$ edges. Also, a stochastic matrix $P\in\mathbb{R}^{n\times n}$ is given. Now I construct the graph as follows:

First I start with some node $x_1$ of type $i$ with $e_i >0$ and I add another node $x_2$ on a free edge of $x_1$ of type $j$ with probability $p_{ij}$. Then, I randomly choose a node $x_v$ of my graph (at this stage $v=1$ or $v=2$) which has a free edge. Then I add a node of type $k$ to node $x_v$ with probability $p_{vk}$. I continue this process until I have added $m$ nodes or if no node has a free edge anymore.

Is it possible to answer for this model questions like: What is the expected percentage of nodes from type $i$ in a constructed graph?


Your Answer

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

Browse other questions tagged or ask your own question.