Enhanced Heuristic Algorithms For Seed Set Selection In Influence Maximisation

The Hong Kong University of Science and Technology 
Department of Computer Science and Engineering 

Final Year Thesis Oral Presentation

Title: "Enhanced Heuristic Algorithms For Seed Set Selection In Influence 
        Maximisation"

by 

Mr. LEUNG Pui Kuen


Abstract: 

Using the cheapest cost to generate the largest influence have long been an 
important strategy to advertise products. With the help of social networks, 
information diffusion become more effective on the internet. The selection 
of seed users helps in maximizing the influence of product advertising in 
social networks. This study shows that using heuristic algorithms leads to 
a reasonable size of influence using the shortest time and the lowest 
memory consumption.

In this paper, we propose two new heuristic algorithms, Mixed Degree 
Influence Discount and Second Level Degree Influence Discount, in which 
each vertices' score was a combination of its degree and its out-going 
edge weight. Furthermore, we compared the performance achieved by carrying 
out experiments using datasets of different sizes. The expected influence 
of seeds, the running time and the memory consumption are considered in our 
experiments. Our results show that both Mixed Degree Influence Discount and 
Second Level Degree Influence Discount outperforms other evaluated 
algorithms and can thus give a better balance among the expected influence, 
the running time and the memory consumption.

  
Date                 : 27 April 2016 (Wednesday)

Time                 : 2:45pm to 3:30pm

Venue                : Room 4504 (lift 25/26)

Advisor              : Dr. Raymond WONG

2nd Reader           : Dr. Pan HUI