1
$\begingroup$

Assuming one has a directed weighted graph with n nodes and let us denote the weight going from node $i$ to node $j$ by $e_{ij}$. Then one can simply just sum all weights $e_{ij}$ up.

But if we are now in the set-up of a directed weighted random Erdos-Renyi graph $G(N,p)$ where $N$ stands for the number of nodes and $p$ for the probability having a link between two edges (just pick for simplicity one direction by probability $1/2$, as we are in a directed graph), how can I calculate the expected value of $\sum_{i=1}^N e_{ij}$ assuming that the weights $e_{ij}$ follow a given distribution? (constant/uniform/normal ect)

Improve this question
$\endgroup$
  • $\begingroup$ Do you mean the expected value of the sum of the weights? Otherwise, I don't understand why you can't just add up the weights. $\endgroup$ – saulspatz Sep 28 '18 at 16:18
  • $\begingroup$ @saulspatz yes, exactly! sorry I was not clear enough... $\endgroup$ – Alisat Sep 28 '18 at 16:47
  • $\begingroup$ Please correct your question to reflect your comment. The goal of this site is to establish a body of questions and answers that people can consult when they have math problems, so it's important that the questions be accurate, as well as the answers. $\endgroup$ – saulspatz Sep 28 '18 at 19:22
  • $\begingroup$ @saulspatz I edited it :) Thank you very much for your comments & your answer! $\endgroup$ – Alisat Sep 28 '18 at 19:39
1
$\begingroup$

Given a vertex $i,$ let $K_i$ be a random variable whose value is the number of edges incident from $i.$ By linearity of expectation, the expected value of the sum the weights on these edges is just $K_i\mu,$ where $\mu$ is the mean of the distribution of the weights. Therefore, if $p_k=\Pr(K_i=k),$ then the expected value of the sum of the weights is $$\sum_{k=1}^{n-1}kp_k\mu=\mu E(K_i)={\mu(n-1)p\over2}$$

Improve this answer
$\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.