Probability & Network Theory

Hey Everyone,

new to this forum and studying network/graph theory on my own. Math has never been my strong point, and I need help with how the author came to this equation:

Imagine a network of people. Suppose that for some small probability p, each common friend that two people have gives them an independent probability p of forming a link each day. So if two people have k friends in common, the probability they fail to form a link on any given day is (1 - p)^k: this is because each common friend fails to cause the link to form with probability 1 - p, and these k trials are independent. Since (1 - p)^k is the probability the link fails to form on a given day, the probability that it does form, according to our simple baseline model, is : Tbaseline(k) = 1 - (1 - p)^k.

Why isn't it p^k if p is the probability of a link forming and k is # common friends?


TS Contributor
p^k is the probability that a link is created with all of the k common friends. The probability of k equally probable independent events to occur is \(p_1p_2p_3...p_k\), and the probability of the occurance of none of these events are therefore \((1-p_1)(1-p_2)(1-p_3)...(1-p_k)=(1-p)^k\). And now to the probability of forming at least one link, well thats just the complement to the probability of not forming a link at all: \(1-(1-p)^k\).

I don't know if this made it any clearer, but I hope so :)
Englund: I think I was able to work it out. Let's say p of a link forming is .3 and 1-p is .7. Number of common friends k =3.

Using the at least one rule: 1 - (1 - .3)^3 = .6570

If I do this the long way it should be:

.3(.7)(.7) = .1470 * 3 = .4410
.3(.3)(.7) = .0630 * 3 = .1890
(.3)(.3)(.3) = .0270
.0270 + .4410 + .1890 = .6570

Can you verify if my math and logic is correct? Just wanted to understand more about the 'at least one' rule