Page 1 of 1

### Network Effect

Posted: Wed Aug 06, 2014 12:26 am
Some time last year I thought of this problem and posted it on a wall at my workplace, but nobody wanted to solve it... and then I remembered this forum. So here I am with this problem. Enjoy! (Later I find out there are papers written about this problem, but I couldn't find one which gave an exact formula.)
Some people attend a networking event, which is a fancy way of saying "a place where people shake hands." Oddly enough, each person initiates a handshake with exactly one other person over the course of the event; this other person is randomly chosen with uniform probability -- and of course can not be himself.

We consider two people to have shaken hands if either or both of them initiated a handshake with the other. Thus many people could have shaken hands with the same person, and two people may have shaken hands with each other twice. We consider two people A and B to belong to the same network if they have shaken hands, or if A has shaken hands with someone belonging to the same network as B.

For example, suppose 7 people attend. We denote each person using a number. The handshakes may be as follows:

1 shakes hands with 2
2 shakes hands with 1
3 shakes hands with 7
4 shakes hands with 5
5 shakes hands with 1
6 shakes hands with 5
7 shakes hands with 3

This results in the networks {1, 2, 4, 5, 6} and {3, 7}.

Suppose 100 people attend the event. To 6 decimal places, what is the expected number of people in the largest network?

### Re: Network Effect

Posted: Wed Aug 06, 2014 3:34 am
I find 81.424033.

### Re: Network Effect

Posted: Wed Aug 06, 2014 10:18 pm
I get 81.4243077, but to save time and memory, my algorithm only considers 0.9999942 of all cases.

### Re: Network Effect

Posted: Thu Aug 07, 2014 6:11 pm
Wow, that was fast I am solving this with a recurrence relation. Could there be a closed-form expression?

My answer for 200 people is 159.6319208462766, computed in about 12 seconds and using lots of memory with Java BigInteger. Maybe there is a way to compute without using BigInteger...

### Re: Network Effect

Posted: Thu Aug 07, 2014 7:00 pm
jer-bear wrote:...I am solving this with a recurrence relation. Could there be a closed-form expression?

My answer for 200 people is 159.6319208462766, computed in about 12 seconds and using lots of memory with Java BigInteger. Maybe there is a way to compute without using BigInteger...
I get the same answer for 200. My approach must be similar, using a recurrence and Java BigInteger, but only 25Mb and 0.13s for 200. I have not found a closed form formula.

### Re: Network Effect

Posted: Sun Aug 10, 2014 8:11 am
More results, from an exact algorithm (which also uses Java and BigInteger).
E(100) = 81.4240329218325
E(200) = 159.63192084627659
E(300) = 237.27431487414844
E(400) = 314.62439473407545
E(500) = 391.7877747430619
E(600) = 468.8185771837519
E(700) = 545.7489380680325
E(800) = 622.5997897966862
E(900) = 699.3856692454125
E(1000) = 776.1171588474358
E(1100) = 852.8022465908942
E(1200) = 929.4471378503679
E(1300) = 1006.0567669823678
E(1400) = 1082.63513451001
E(1500) = 1159.1855373082542
E(1600) = 1235.7107304959954
E(1700) = 1312.213044479208
E(1800) = 1388.6944713453727