Less Wrong is a community blog devoted to refining the art of human rationality. Please visit our About page for more information.

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

2 Post author: Gunnar_Zarncke 01 September 2014 10:03AM

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

Comments (11)

Comment author: Gurkenglas 01 September 2014 01:36:45PM 5 points [-]

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.

Comment author: V_V 03 September 2014 03:03:09PM *  3 points [-]

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.

Comment author: Stefan_Schubert 01 September 2014 10:34:20AM 4 points [-]

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

Comment author: solipsist 02 September 2014 01:50:49AM 4 points [-]

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

Comment author: Mizue 03 September 2014 07:11:46PM 1 point [-]

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

Comment author: Luke_A_Somers 04 September 2014 04:33:53PM 1 point [-]

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

Comment author: MattG 02 September 2014 08:25:50PM 1 point [-]

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

Comment author: Lumifer 03 September 2014 07:47:24PM 1 point [-]

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.

Comment author: Gunnar_Zarncke 03 September 2014 09:37:27PM 2 points [-]

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:

Comment author: Lumifer 04 September 2014 12:43:31AM 3 points [-]

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.

Comment author: Gunnar_Zarncke 04 September 2014 06:42:19AM 1 point [-]

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.