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.
- 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.
Social Networks, Influence Propagation, Information Dissemination, Graph Theory, Complexity Theory, Graph/Approximation/Randomized Algorithms.