演講訊息 TALKS

摘要 Consider the following hypothetical scenario as a motivating example. A company wish to market a new product. The company has at hand a description of the social network G formed among a sample of potential customers, where the vertices represent customers and edges connect people to their friends. The company wants to target key potential customers S of the social network and persuade them into adopting the new product by handing out free samples. We assume that individuals in S will be convinced to adopt the new product after they receive a free sample, and the friends of customers in S would be persuaded into buying the new product, which in turn will recommend the product to other friends. The company hopes that by word-of-mouth effects, convinced vertices in S can trigger a cascade of further adoptions, and finally all potential customers will be persuaded to buy the product. A social network (G,θ) is usually modeled by a graph G together with a threshold function θ: V(G) →N such that 1≦θ(v)≦ d(v) for each vertex v in G. Given a vertex subset S of a connected social network (G,θ). Consider the following repetitive process played on (G,θ). At round 0 (the beginning of the game), the vertices of S are colored black and the other vertices are colored white. After that, at each round t > 0, all white vertices v that have at least θ(v) black neighbors at the previous round t-1 are colored black. The colors of the other vertices do not change. The process runs until no more white vertices can update colors from white to black. The set S is called a target set for (G,θ). We are interested in the following optimization problem: finding a target set S of smallest possible size such that all vertices of V(G) \ S are black in the end.