چكيده به لاتين
Finding the most influential nodes in social networks is one of the most important optimization problem in social network analysis literature. This problem (which is known as Influence maximization problem) is trying to find a small set of initial adopters who will lead to most number of adoptions. The problem has been investigated from an algorithmic point of view in non-competitive and competitive points of view. There have been proposed heuristic, meta-heuristic and approximation algorithms to cope this problem. In this thesis, three mathematical programming models and a game theoretic model based on different sets of assumption in non-competitive and competitive situations have been proposed. In the proposed models, the effect of different factors such as personality traits of the nodes, diffusing message’s content, nodes’ taste and … on the diffusion process has been considered.
So, based of different sets of assumption, “determinist diffusion optimization model”, “opinion optimization model” and “non-deterministic diffusion optimization model” in non-competitive situation have been developed. On the other hand, beside proposing a novel competitive influence model, “competitive deterministic optimization model” has been developed as a static and complete information game to cope the problem in competitive situation.
All the developed model, implemented on Abrar University dataset and the efficiency of the obtained solutions have been shown through comparing them with some of the well-known existing heuristic algorithm.
It should be noted, since the effect of personality traits of the nodes in the diffusion process considered in the models, a new centrality named as “sociability centrality” has been developed too.
