Network Effect

Arrangements, sorting, packing, partitions, critical path analysis, networks, graphs, ...
Post Reply
jer-bear
Posts: 2
Joined: Mon Sep 09, 2013 7:22 pm

Network Effect

Post by jer-bear » Tue Aug 05, 2014 11:26 pm

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?

User avatar
mpiotte
Administrator
Posts: 1914
Joined: Tue May 08, 2012 4:40 pm
Location: Montréal, Canada

Re: Network Effect

Post by mpiotte » Wed Aug 06, 2014 2:34 am

I find 81.424033.
Image

thundre
Posts: 356
Joined: Sun Mar 27, 2011 9:01 am

Re: Network Effect

Post by thundre » Wed Aug 06, 2014 9:18 pm

I get 81.4243077, but to save time and memory, my algorithm only considers 0.9999942 of all cases.
Image

jer-bear
Posts: 2
Joined: Mon Sep 09, 2013 7:22 pm

Re: Network Effect

Post by jer-bear » Thu Aug 07, 2014 5:11 pm

Wow, that was fast :o

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...

User avatar
mpiotte
Administrator
Posts: 1914
Joined: Tue May 08, 2012 4:40 pm
Location: Montréal, Canada

Re: Network Effect

Post by mpiotte » Thu Aug 07, 2014 6: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.
Image

thundre
Posts: 356
Joined: Sun Mar 27, 2011 9:01 am

Re: Network Effect

Post by thundre » Sun Aug 10, 2014 7: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
Image

Post Reply