Edge color constrained influence maximization in social networks

• Main Author: Chandra, Bhavya
• 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/70421
• Institution: Nanyang Technological University

In this Final Year Project, we analyze the novel problem for jointly finding the top-k seed nodes and top-r most relevant topics that maximize the influence within a given target set in a social network. Our problem has direct application in viral marketing because social networks are the wide and fast medium of information-spread. A brand can maximize its promotion on social media by choosing the most influential people in a social network (seed nodes) to begin its marketing. However, simply selecting the most influential people does not maximize the spread as the content of a post dictates how likely a user will ‘share’ it. Thus, we show that it is not only imperative to select the top-k seed nodes but also the top-r most relevant topics in the network. Previous research for influence maximization largely models social networks as a graph with fixed edge probabilities of association between two users. However, real-world graphs are uncertain and the edge probabilities depends on external conditions e.g. the presence of a hashtag or keyword in a post dictates the probability of a user sharing a post rather than simply the association between two users. The problem under this model is shown to be NP-hard. Thus, we develop a system TINTO that provides an iterative algorithm targeting both efficiency and accuracy. We first solve the problem for finding the most relevant topics between a source set and target set in a social network through our maximum reliability algorithm, and then integrate it with existing algorithms to find the most influential seed nodes- thereby, forming our TINTO system. The efficiency and accuracy of the TINTO system is also demonstrated through a case study in real-world dataset.