Computer Science – Social and Information Networks
Scientific paper
2011-01-31
Computer Science
Social and Information Networks
Scientific paper
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.
Brunetti Sara
Lodi Elena
Quattrociocchi Walter
No associations
LandOfFree
Dynamic Monopolies in Colored Tori does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Dynamic Monopolies in Colored Tori, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic Monopolies in Colored Tori will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-647552