Name
Abstract | ||
|---|---|---|
The {em information diffusion} has been modeled as the spread of an information within a group through a process of social influence, where the diffusion is driven by the so called {em influential network}. Such a process, which has been intensively studied under the name of {em viral marketing}, has the goal to select an initial good set of individuals that will promote a new idea (or message) by spreading the "rumor" within the entire social network through the word-of-mouth. Several studies used the {em linear threshold model} where the group is represented by a graph, nodes have two possible states (active, non-active), and the threshold triggering the adoption (activation) of a new idea to a node is given by the number of the active neighbors. The problem of detecting in a graph the presence of the minimal number of nodes that will be able to activate the entire network is called {em target set selection} (TSS). In this paper we extend TSS by allowing nodes to have more than two colors. The multicolored version of the TSS can be described as follows: let $G$ be a torus where every node is assigned a color from a finite set of colors. At each local time step, each node can recolor itself, depending on the local configurations, with the color held by the majority of its neighbors. We study the initial distributions of colors leading the system to a monochromatic configuration of color $k$, focusing on the minimum number of initial $k$-colored nodes. We conclude the paper by providing the time complexity to achieve the monochromatic configuration. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/IPDPS.2011.194 | IPDPSW '11 Proceedings of the 2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and PhD Forum |
Keywords | DocType | Volume |
entire social network,em viral marketing,em linear threshold model,em target set selection,em influential network,finite set,monochromatic configuration,entire network,new idea,dynamic monopolies,em information diffusion,colored tori,social sciences,threshold model,cluster computing,social network,viral marketing,time complexity,computational complexity,protocols,generators,marketing,word of mouth,local time,topology,data structure,graph representation,social influence,color,upper bound | Conference | abs/1101.5915 |
Citations | PageRank | References |
8 | 0.63 | 23 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sara Brunetti | 1 | 122 | 16.23 |
| Elena Lodi | 2 | 154 | 16.21 |
| Walter Quattrociocchi | 3 | 582 | 42.16 |