Influence maximization on dynamic graphs

• Main Author: Lim, Zi Xiang
• Other Authors: Arijit Khan
• Format: Final Year Project
• Language: English
• Published: 2017
• Subjects: DRNTU::Engineering::Computer science and engineering
• Online Access: http://hdl.handle.net/10356/70093
• Institution: Nanyang Technological University

In the real world, there are many applications of the stream such as social networks and telecommunication networks. Due to the great potential in targeted recommendations and viral marketing, there is a tremendous incentive to find the top k influencers. However, due to the nature of the dynamic graph, we will tackle the inherent problem of finding the top k influencers as the dynamic graph is constantly changing. We model the stream as slip shots of the static graph that changes over the time. From there, we take note of the incoming changes to the edges and attempt in handling those mutually exclusive cases. Under the popular use of the independent cascade model, we develop an algorithm that performs an update to the top k nodes based on the mutually exclusive cases of edge addition, edge deletion and edge modification. Using up to date research by other paper and the DBLP collaboration network dataset, we validate the use of our method on the network and present a timeline of the most influential authors in the network.