Large Social Networks can be Targeted for Viral Marketing with Small Seed Sets

It shows how easy a population can be influenced if control over a small sub-set exists.  

A key problem for viral marketers is to determine an initial "seed" set [<1% of total size] in a network such that if given a property then the entire network adopts the behavior. Here we introduce a method for quickly finding seed sets that scales to very large networks. Our approach finds a set of nodes that guarantees spreading to the entire network under the tipping model. After experimentally evaluating 31 real-world networks, we found that our approach often finds such sets that are several orders of magnitude smaller than the population size. Our approach also scales well - on a Friendster social network consisting of 5.6 million nodes and 28 million edges we found a seed sets in under 3.6 hours. We also find that highly clustered local neighborhoods and dense network-wide community structure together suppress the ability of a trend to spread under the tipping model.

This is relevant for LW because

a) Rational agents should hedge against this.

b) An UFAI could exploit this.

c) It gives hints to proof systems against this 'exploit'.

New Comment
12 comments, sorted by Click to highlight new comments since: Today at 11:32 PM

You don't beat an UFAI by enumerating the exploits it could use. That kind of argument is found by trying to find arguments for your particular cause.

Disagree. This line of thinking leads to the fragile "provably safe" design strategy.

History of engineering tells us that provably safe, provably secure systems aren't, because even if your proof is mathematically correct, you most likely forgot to include some relevant aspect in your model, which leads to an exploit.
In real-world safety and security engineering, you don't want to rely on a single-point-of-failure design, you want to think about exploits and faults, both to provide defence in depth and to use them to stimulate your intuition about the mathematical models you use, reducing the chances that you miss something important.

It could be used for good purposes also. For instance, you could spread rationality or EA memes using this method.

True, but if marketing is your aim you are probably better off familiarizing yourself with standard best practices than with cutting-edge research.

Wouldn't a lot of either standard best practices or cutting edge research fall under what is considered "dark arts" here? So this really becomes "you can use Dark Arts for good purposes". Whether you should do so seems at least questionable, although I can see some arguments for it (such as when you need to use it to get rid of the effect of biases or to oppose someone else's dark arts).

This doesn't seem like 'dark arts' as knowing who to talk to, which seems more to fall under general effectiveness.

[-][anonymous]10y10

There's a happy medium... a lot of the standard best practices become white noise because people see them all the time.

[-][anonymous]8y00

One more application is exploiting these networks to promote rationality.

It shows how easy a population can be influenced if control over a small sub-set exists.

Do note that "population" here refers to a set of nodes in a network, not to any actual humans.

The paper is about an algorithm for finding an "small" seed set which will take over the entire network of tipping nodes (where "tipping" means that once a certain percent of neighbors of a node become X, the node necessarily becomes X itself).

Human social networks don't exactly work like that.

Human social networks don't exactly work like that.

Apparently they do. The study references e.g. “The Spread of Behavior in an Online Social Network Experiment,” which is an controlled social network of real humans exhibiting basically this behavior:

First, it's an artificial, experimental network of real humans. Second, the adoption rates in that study top out at 50-60%. The paper in the OP concerned itself with finding a seed set which will produce a 100% adoption.

For real human of course you need a more detailed model than the simple linear threadshold one which was amenable to optimization by their algorithm. With a more detailed model they probably wouldn't have been able to reach 100% but wouldn't have tried to (e.g. if there is a non-adaption term I'd have strived for 100% divided by the non-adaption rate or something). But that doesn't mean that you can tipp tippable populations.