Abstract

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.