The problem of influence maximization has been studied extensively with applications that include viral marketing, recommendations, and feed ranking. The optimization problem, first formulated by Kempe, Kleinberg and Tardos, is known to be NP-hard. Thus, several heuristics have been proposed to solve this problem. This thesis studies the problem of influence maximization under the deterministic linear threshold model and presents a novel heuristic for finding influential nodes in a graph with the goal of maximizing contagion spread that emanates from these influential nodes. Inputs to our algorithm include edge weights and vertex thresholds. The threshold difference greedy algorithm presented in this thesis takes into account both the edge weights as well as vertex thresholds in computing influence of a node. The threshold difference greedy algorithm is evaluated on 14 real-world networks. Results demonstrate that the new algorithm performs consistently better than the seven other heuristics that we evaluated in terms of final spread size. The threshold difference greedy algorithm has tuneable parameters which can make the algorithm run faster. As a part of the approach, the algorithm also computes the infected nodes in the graph. This eliminates the need for running simulations to determine the spread size from the influential nodes. We also study the target set selection problem with our algorithm. In this problem, the final spread size is specified and a seed (or influential) set is computed that will generate the required spread size. / Master of Science

The adoptation of environmentally friendly behaviour is rather slow, although the climate crisis is pressing. This thesis aims to understand the slow adoption of environmentally friendly behaviour, specifically focusing on vegetarianism and veganism, by employing social network analysis. By simulating interactions within an agent-based model, the study explores different mechanisms that hinder the diffusion of these behaviours. The research findings highlight the significance of the complexity of the contagion in shaping the speed and extent of the diffusion process. While minimally complex contagions are able to infect half of the network on average, vegetarianism and veganism do not spread, due to their complexity. Additionally, the initial number of vegetarians/ vegans was found to be the main driver of infection speed, besides inter-connectedness. The study also explores the possibility of a social tipping point, a critical threshold at which the diffusion process accelerates or reaches a critical mass. However, the research did not observe a tipping point in the adoption of vegetarianism and veganism. By examining the slow adoption of vegetarianism and veganism as a complex contagion, this research contributes to the comprehension of concrete network effect. The findings provide valuable insights for designing interventions and strategies to promote the widespread adoption of vegetarianism, veganism, and other environmentally friendly practices.