1
$\begingroup$

Assuming we have a random directed weighted graph with $n$ nodes. Furthermore let us assume the nodes are divided into two categories:

  1. A node $i$ is of category C if there are only outgoing edges or only ingoing edges from/to $i$
  2. Otherwise a node $i$ is of category D

Let the number of nodes in category C be $c$,then the number of nodes in category D is simply $n-c$.
Let $p_1$ be the probability that there is an edge between two nodes of category $C$ (and we pick each direction with $p_1/2$) and let $p_2$ be the probability of an edge between two nodes $i$ and $j$ for all other cases (again picking each direction with probability $p_2/2$). We denote the weight going from a node $i$ to a node $j$ by $e_{ij}$, where the $e_{ij}$'s follow three different distributions (with means $\mu_1, \mu_2, \mu_3$ respectively) depending on following cases:

  • $(i,j)\in D\times D$
  • $(i,j)\in D\times C$ or $(i,j)\in C\times D$
  • $(i,j)\in C\times C$

I am interested in calculating the expected value of $\sum_{j=1}^{n-1} e_{ij}-e_{ji}$. For the cases where $i$, $j$ are both in the same category, the values will simply be zero by symmetry. But how can I calculate the other cases?

My idea was to first calculate the expected value of $\sum_{j=1}^{n-1} e_{ij}$ for the two cases of $i$:

i.e. if $i \in C$, then $$\sum_{j=1}^{n-1} e_{ij}=\sum_{j\in C} e_{ij} +\sum_{j\in D} e_{ij}=\frac{ \mu_3(c-1)p_1}{2} +\frac{ \mu_2(n-c)p_2}{2}$$ And if if $i \in D$, then $$\sum_{j=1}^{n-1} e_{ij}=\sum_{j\in C} e_{ij} +\sum_{j\in D} e_{ij}=\frac{ \mu_2 c p_2}{2} +\frac{ \mu_1(n-c-1)p_2}{2}$$

Then since if a node $i$ is in C it only has arrows in one direction, the expected 'net position' would be $\frac{ \mu_3(c-1)p_1}{2} +\frac{ \mu_2(n-c)p_2}{2}$

And for the other case, if $i$ is in D the expected 'net position' would be simply $0$ by symmetry. Is this correct until now or am I missing something?

Thanks for any help!

$\endgroup$
1
$\begingroup$

Approved by my supervisor all calculations are correct and this is the solution to the expected net-positions:

  • if $i \in C$: $\quad \pm (\mu_3 (c-1)p_1/2 + \mu_2 (n-c) p_2/2)$
  • if $i \in D$: $\quad 0$
$\endgroup$

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.