Stochastic Diffusion Search Explination (basic)

Algorithmic Explination ofSDS

Mathmatical Proof

Stochastic Diffusion Search is a process which allows for the testing of a “hypothesis” or to acquire information from a social network. Individual “agents” are used to break down the problem and gather what has been labeled “partial evaluations” of the “hypothesis.” Through the process “agents” and their “evaluations” will converge on a result. We can use the concepts learned in class to develop a very basic understanding of this while analyzing the algorithm.

First we must assume that there are many numbers of behaviors that a node may adopt, and there are N nodes. All nodes begin with a randomly adopted behavior and begin their test. After each test the nodes then communicate via one-on-one interactions. If they receive a favorable result they will stay with that behavior. However, if a node does not receive a favorable result then two things may happen 1) the node will talk to one if its neighbors and will switch to the neighbors behavior if the neighbor received a favorable result or 2) the node will begin its process over again with a different randomized behavior. As the time progresses the nodes will converge to a single favorable behavior or what can be labeled as the socially optimizing behaviors.

As the process continues nodes begin to adopt behaviors based on the results of their neighbors and less and fewer behaviors are left as options. As the nodes begin to tend to a behavior the threshold of the network is reached since every node communicates with several if not all of its neighbors. As the nodes run through the algorithm their behavioral options become limited and soon each node is behaving based on the actions of their neighbors. Clusters can applied to explain why the process does not unravel through some false cascade. As the acceptance of a behavior grows the density of the network of nodes with this behavior increases, which decreases the likeliness of a cascade against this behavior. Once the density reaches the crucial value of 1-q then not only is it impossible to cascade through and change the results thus far, the behavior adopted by this cluster more likely than not is the favorable or socially optimizing behavior

It is important to keep in mind that in this very simple explanation behavior can be a Boolean, a piece of information, the result of a personal payoff to a node and many more. This is a very bare bones analysis. The mathematical article does a good job with the proof of convergence.