Thesis Defense - Doruk Eşki (MSIE)

Doruk Eşki – M.Sc. Industrial Engineering

Asst. Prof. Dilek Günneç Danış – Advisor

Date: 11.06.2021

Time: 15:00 – 16:30

Location: This meeting will be held ONLINE. Please send an e-mail to gizem.bakir@ozyegin.edu.tr in order to participate in this defense.

Two-Level Influence Maximization Problem Under Deterministic Threshold Model

Thesis Committee:

Asst. Prof. Dilek Günneç Danış, Özyeğin University

Asst.  Prof.  Erinç Albey, Özyeğin University

Asst.  Prof.  Evren Güney, MEF University

Abstract:

Data-driven decision-making strategies can make online marketing more efficient and help companies reach a larger number of customers using limited resources. In this respect, the Influence Maximization Problem searches for a certain number of influential individuals on a social network so that the information/product spread initiated from such individuals is maximized.

We introduce a novel problem, the Two-Level Influence Maximization Problem, which allows influencing neighbors without eventually adopting the product. To solve this problem, we develop a Greedy Algorithm and two variants, namely Modified Greedy Algorithm and Update Limited Algorithm. Same objective function value is provided with a much lower runtime in Modified Greedy Algorithm. In Update Limited Greedy Algorithm, convergence to objective function of Greedy Algorithm is no longer guaranteed but runtime is further reduced improved. We also introduce a Simulated Annealing-based metaheuristic with a tabu strategy that exploits the problem-specific neighborhood moves. We apply this algorithm with proposed Greedy Algorithm variants on small scale random networks and with well-known link analysis algorithms from literature on large scale real social networks. We also show that following alternative strategies such as maximizing number of individuals that influence their neighbors without adopting the product can also return an effective starting solution for Simulated Annealing algorithm.

The computational results on simulated and real social networks show that our heuristics can provide high-quality solutions.

Bio: 

Doruk Eşki was born in İstanbul/Turkey on June 14, 1996. He received his B.Sc. degree in Industrial Engineering from Özyeğin University in 2019. He worked as a graduate teaching assistant and conducted research on combinatorial optimization on social networks under the supervision of Assistant Professor Dr. Dilek Günneç Danış. He currently works as a part-time data scientist at KoçDigital.