Navigation menu menu

Minimum Target Set in Social Networks: An Algorithmic Approach

External Member

Ahad N. Zehmakan

Description

 
 
If we can try to convince a subset of individuals to adopt a new product or innovation, and the goal is to trigger a large cascade of further adoptions, which set of individuals should we target? Motivated by the design of viral marketing strategies, this question has attracted tremendous attention in different areas of computer science, especially a branch of artificial intelligence called computational social choice.
 
Consider a graph G=(V,E) and an initial profile where each node is active or inactive. The graph G represents a social network, where a node is an individual and an edge between two nodes corresponds to a relation between the respective individuals, e.g. friendship or common interests. The state of a node indicates whether it is positive/negative about a product or it is aware/unaware of a piece of information. Consider a threshold function T which assigns an integer value between 1 and d(v) to each node v in V, where d(v) is the degree of v. The threshold of node v is the number of nodes which must be active in the neighborhood of v to change its state from inactive to active.
 
Consider the following iterative process. In each time step, the states of inactive nodes (if any) are updated according to the following rule: each inactive node becomes active if the number of active nodes in its neighborhood is not smaller than its threshold (and the active nodes remain active). The process runs until no more node can switch from inactive to active.
 
Target Set Selection Problem. A node set S is called a target set whenever the following holds: If all nodes in S are initially active, then all nodes become active by the end of the process. What is the minimum size of a target set for a given graph G?
 

Goals

The Target Set Selection Problem is known to be NP-Complete and hard to approximate. However, several approximation and randomized algorithms have been proposed for different variants of the problem.

Task 1. Enrich the model by introducing different parameters, such as stubbornness (the resistance against accepting novel products/ideas) or cost (convincing some nodes might be more costly than others).

Task 2. Propose approximation/randomized algorithms (potentially based on improvement or combination of the previous algorithms). 

Task 3. Evaluate the performance of the proposed algorithm(s) against the previous algorithms by conducting experiments on real-world social networks such as Facebook and Twitter. 

 Note. The goal of the project can be adjusted to match the student's background and interests. The project can be taken as a 6, 12, or 24 unit course.

 

Contact Information

 
 

Requirements

  • A good understanding of algorithm design techniques, complexity classes, graph theory, and probability theory.
  • Good programming skills.
  • Have taken/taking COMP3600 and ideally COMP4600 and MATH2301.

Keywords

Social Networks, Influence Propagation, Information Dissemination, Graph Theory, Complexity Theory, Graph/Approximation/Randomized Algorithms.

 

Updated:  10 August 2021/Responsible Officer:  Dean, CECS/Page Contact:  CECS Marketing