Login | Register




Wu, Kangkang (2015) INFLUENCE MAXIMIZATION IN SOCIAL NETWORKS. Masters thesis, Concordia University.

[thumbnail of Wu_MSc_S2016.pdf]
Text (application/pdf)
Wu_MSc_S2016.pdf - Accepted Version


In the social network era, every decision an individual makes, whether it is watching a movie or purchasing a book, is influenced by his or her personal network to a certain degree. This thesis investigates the power of the “word-of-mouth” effect within social networks.
Given a network G = (V, E, t) where t(v) denotes the threshold of node v, we model the spread of influence as follows. Influence propagates deterministically in discrete steps. An influenced node u exerts a fixed amount of influence bu,w on any neighbor w. For any uninfluenced node v, if the total amount of influence it receives from all its already influenced neighbors at time step t− 1 is at least t(v), node v will be influenced in step t.
Given a social network G, we study the problem of introducing an already activated external influencer v into the network, and choosing links from v to nodes in G that can maximize the spread of influence in G. We study two problems: the Minimum Links problem, which is to choose the minimum number of links that can activate the entire network, and the Maximum Influence problem, which is to choose k neighbors that will maximize the size of the influenced set. We prove that the Maximum Influence problem is NP-hard, even for bipartite graphs in which thresholds of all nodes are either one or two. We also study both problems in paths, rings, trees and cliques, and we give polynomial time algorithms that find optimal solutions to both problems for all these topologies.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Wu, Kangkang
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science and Software Engineering
Date:20 November 2015
Thesis Supervisor(s):Narayanan, Lata
ID Code:980698
Deposited By: KANGKANG WU
Deposited On:16 Jun 2016 14:45
Last Modified:18 Jan 2018 17:51
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top