A couple months ago someone posted an interesting programming homework problem on reddit, asking for help. Help had already been provided before I got there, but I thought the problem was an interesting one.
Write a program that simulates the spreading of a rumor among a group of people. At any given time, each person in the group is in one of three categories:
- IGNORANT - the person has not yet heard the rumor
- SPREADER - the person has heard the rumor and is eager to spread it
- STIFLER - the person has heard the rumor but considers it old news and will not spread it
At the very beginning, there is one spreader; everyone else is ignorant. Then people begin to encounter each other.
So the encounters go like this:
- If a SPREADER and an IGNORANT meet, IGNORANT becomes a SPREADER.
- If a SPREADER and a STIFLER meet, the SPREADER becomes a STIFLER.
- If a SPREADER and a SPREADER meet, they both become STIFLERS.
- In all other encounters nothing changes.
Your program should simulate this by repeatedly selecting two people randomly and having them "meet."
There are three questions we want to answer:
- Will everyone eventually hear the rumor, or will it die out before everyone hears it?
- If it does die out, what percentage of the population hears it?
- How long does it take? i.e. How many encounters occur before the rumor dies out?
I wrote a very thorough version to produce videos of the simulation in action.
git clone git://github.com/skeeto/rumor-sim.git
It accepts some command line arguments, so you don't need to edit any code just to try out some simple things.
And here are a couple of videos. Each individual is a cell in a 2D grid. IGNORANT is black, SPREADER is red, and STIFLER is white. Note that this is not a cellular automata, because cell neighborship does not come into play.
And a larger one with a population of 10,000.
Here's are the statistics for ten different rumors.
Rumor(n=10000, meetups=132380, knowing=0.789) Rumor(n=10000, meetups=123944, knowing=0.7911) Rumor(n=10000, meetups=117459, knowing=0.7985) Rumor(n=10000, meetups=127063, knowing=0.79) Rumor(n=10000, meetups=124116, knowing=0.8025) Rumor(n=10000, meetups=115903, knowing=0.7952) Rumor(n=10000, meetups=137222, knowing=0.7927) Rumor(n=10000, meetups=134354, knowing=0.797) Rumor(n=10000, meetups=113887, knowing=0.8025) Rumor(n=10000, meetups=139534, knowing=0.7938)
Except for very small populations, the simulation always terminates very close to 80% rumor coverage. I don't understand (yet) why this is, but I find it very interesting.blog comments powered by Disqus