Rumor Spread Simulation

For the discussion of math. Duh.

Moderators: gmalivuk, Prelates, Moderators General

Rumor Spread Simulation

Postby megabnx » Wed Nov 19, 2008 2:58 am UTC

In my statistics class we just finished going over methods of simulating a study and we used one example that really caught my attention. The point of our simulation was to depict how a rumor/disease spreads throughout a population. We started with the entire class being uninformed and randomly selected one poor fool to start the rumor. Each turn, the people who knew get a chance to spread the information on the class by randomly choosing someone else to inform. If they target a clean person, the target starts spreading the rumor as well. If they target another person who knows the information (even themselves) both target and the person who picked the target get switched to a new state where they can't spread the rumor anymore but they can still stop other people from spreading by stopping people who tell them from telling any more. For clarification you cannot start spreading the instant you are infected, you must wait until the turn you were infected ends. As well, multpile people can target the same person randomly with no adverse effect.

I instantly set to work trying to mathematically describe the probability of each outcome, but after just creating a formula for some of the smaller cases my answers became quite daunting in size. On top of this I failed at discerning any pattern I could use to extend any formula out to generalize to all numbers. I might have just given up, but my teacher claims that in something he read a while ago he found a relatively simple equation to model this scenarios outcome. Anyone here think they can take a swing at finding this magic equation?

Just as a quick side note, I made a (not so small) java program to run a couple million simulations to see what happens and there seems to be some distribution such that the average amount of survivors is around one fourth the starting number and the most common result is slightly less than this mean value dropping off quicker with less survivors than more. If wanted I'll share the program so you can see the results for yourself.
megabnx
 
Posts: 50
Joined: Tue Aug 19, 2008 1:30 am UTC

Re: Rumor Spread Simulation

Postby quintopia » Wed Nov 19, 2008 8:46 am UTC

This sounds interesting. Please post a graph.
User avatar
quintopia
 
Posts: 2790
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Rumor Spread Simulation

Postby snails » Wed Nov 19, 2008 3:34 pm UTC

For a sufficiently large population, you can model the situation fairly well with a deterministic model.

A=Proportion infected and active
B=Proportion infected and inactive

at each timestep, simultaneously:
A-> A+ A*(1-3A-2B)
B-> B+ A*(2A+B)

A(0)=1/population
B(0)=0

Using this model and large values of N, I'm getting a final result of 76% infected and 24% uninfected.

Graph for A = 1/100000000000000000000000000
Image
User avatar
snails
 
Posts: 124
Joined: Sun Mar 23, 2008 11:58 am UTC

Re: Rumor Spread Simulation

Postby quintopia » Wed Nov 19, 2008 10:26 pm UTC

Edit: I figured out the problem.

Also, what do you get when you fit a generalized logistic to it?
Last edited by quintopia on Wed Nov 19, 2008 10:45 pm UTC, edited 1 time in total.
User avatar
quintopia
 
Posts: 2790
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Rumor Spread Simulation

Postby Token » Wed Nov 19, 2008 10:40 pm UTC

quintopia wrote:B=B+(1-2B)(2((1-2B)/3)+B)/3
0=(1-2B)(2-B)/9

What the fuck is happening there?

Surely common sense says "A=0, B=anything" is a stationary state.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.
Token
 
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: Rumor Spread Simulation

Postby nahkh » Sat Nov 22, 2008 3:05 pm UTC

Ran a simulation with N = 20000.
Here's the graph, as requested.
Image
And here's the code.
Spoiler:
Code: Select all
% FILE rumors.m begins

clear;
N = 20000;
count_a = 1;
count_b = 0;
ncount_a = count_a(end);
ncount_b = count_b(end);
while(count_a > 0)
    for i=1:count_a(end);
        target = ceil(rand(1)*N);
        if(target > count_a(end)+count_b(end)) % Hit uninfected
            ncount_a = ncount_a + 1;
        else
            if(target > count_b(end)) % hit active infected
                if(target > count_b(end) + 1) % hit someone else
                    ncount_a = ncount_a - 2;
                    ncount_b = ncount_b + 2;
                else    % hit ourselves.
                    ncount_a = ncount_a - 1;
                    ncount_b = ncount_b - 1;
                end
            else % hit inactive infected
                ncount_a = ncount_a - 1;
                ncount_b = ncount_b + 1;
            end
        end
    end
    count_a = [count_a ncount_a];
    count_b = [count_b ncount_b];
end
figure(1);
subplot(1,1,1),
plot((1:length(count_a)),count_a/N,(1:length(count_b)),count_b/N);
legend('Active','Inactive');

% EOF


EDIT: As a sidenote, the average percentage of infected was 71.5% after twenty simulations. Someone else can strive for statistical rigor, it's daddy's B5 time now.
EDIT: EDIT:
I'd like a small clarification. When selecting a victim, is it possible to select yourself? The OP isn't entirely clear on that. Specifically "If they target another person who knows the information (even themselves)" seems to contradict "by randomly choosing someone else to inform." Until I hear anything else I (and the above code) will just assume it's possible to target yourself.
I'd like to independently confirm snail's result, I get the same result with a similar probability model. Snails did have a minor inaccuracy there but the effect becomes insignificant as sample size is increased (The chance of targeting yourself needs to be addressed, however the above is corrected.)
The percentage of total infections seems to approach 75.98% as the sample size is increased. (Even N = 200 gets over 75.5%)

I expect there's a bug in my above program though. The rate of infections should be close to 2^n with small enough n, so why am I seeing a rate of n? Needs checking.

EDIT: EDIT: EDIT:
Found the bug. Corrected the above code (The line or i=1:count_a(end); lacked the (end) which caused it to do just one infection attempt per round). Replaced the image too. Now the result seems much more in line with the probabilistic estimate. Also, the simulation ran significantly faster now that it is bug free, so this time I ran it with a population of 2000000. And the percentage of infectees is 76.03% in simulation.
Maturity is knowing you were an idiot in the past.
Wisdom is knowing that you will be an idiot in the future.
Common sense is trying not to be an idiot now.
nahkh
 
Posts: 14
Joined: Tue Apr 08, 2008 5:48 am UTC


Return to Mathematics

Who is online

Users browsing this forum: Bing [Bot] and 5 guests