Consider a graph (undirected, simple) G=(V,E) representing a social network with each node corresponding to a potential customer, and edges representing connections in the social network. Moreover, for each node v \in V a number t_v is given, called the threshold, that specifies the number of neighbors of v that need to adopt the product before node v is going to adopt the product. Given the graph G and the thresholds, the problem is to identify the smallest possible set of nodes (the target set) such that when each node of the target set adopts the product, every node in the network will eventually adopt the product. Of course, one may also aim for a less ambitious goal, and find a smallest target set such that, for instance, at least 90% of the nodes will adopt the product.
Goals of the bachelor project:
*) Find scientific literature on this subject
*) Design mathematical programming models for this problem
*) Solve instances of this problem that come from practice