Probability that a node loses an edge in the Barabási-Albert (BA) model with removal of edges

134 Views Asked by At

I'm following the book Networks by Mark Newman. He considers an extension to the BA model where edges are removed uniformly at random. He computes the probability that a particular node $i$ loses an edge when a single edge is removed from the network to be $$ p_i = \frac{2k_i}{\sum_j k_j}, $$ where $k_i$ is the degree of node $i$ and he says the factor two coming from the two ends of the edge.

I understand why the probability is proportional to the node degree, because the number of edges attached to a node is the degree (in the case there are no self-loops). What I don't understand is why there is a factor $2$. It seems to me this probability is not properly normalized, as $\sum_i p_i = 2$.

1

There are 1 best solutions below

1
On BEST ANSWER

That is because the events "Node $i$ loses an edge" are not disjoint - whenever an edge is removed, two nodes will lose an edge, so it makes sense that the probabilities will sum to 2.
Regarding the factor of $2$ in the $p_i$ formula, there are $\frac{\sum_{j} {k_j}}{2}$ edges, and there are $k_i$ edges with an end at node $i$, so the probability that such an edge will be chosen is $$\frac{k_i}{\frac{\sum_j {k_i}}{2}} = \frac{2k_i}{\sum_j {k_j}}$$