انتشار تاثير در شبكه هاي اجتماعي

چكيده انگليسي :

Influence Of Propagation In Social Networks Niloufar Kalanat November 2020 Master of Science Thesis in Farsi Departement of Mathematical Sciences Isfahan University of Technology Isfahan 84156 8311 IranSupervisor Dr Ramin Javadi rjavadi@cc iut ac ir 2000 MSC Keywords Target set selection Social networks Viral Marketing Computational Complexity Approxi mation AlgorithmsAbstract This thesis examines a publishing process in graphs In this process first a number of vertices became active and during the process according to the law of a threshold function the rest of the vertices become activated Opti mal target set in graph G is smallest subset of vertices of G wich activating them make other vertices active Thisconcept was first introduced in 2008 by Chen After that many researchers studied this issue in which Tardoushand a group of colleagues presented the formulation problem So far many researches have been done in this field the result of which are approximate and parametric algorithms in general or for graphs with specific properties Inthis dissertation we review these algorithms and the obtained boundaries To make the issue more tangible a fewexamples are given Consider the following scenario You are the marketer of a clothing company that is responsiblefor marketing a new summer clothing product and has a description of the communication network formed betweena sample group of teenagers in the area Finally the idea that comes to mind is to identify and target key charactersand persuade them to accept a new summer product transform a number of free examples and hope that by usingthe peer pressure law people will be targeted Convince your friends to buy a new product which in turn encouragestheir friends and thus creates a domino like effect on the network But now the question is how to find a good set ofpeople to target To solve the problem we first try to model and provide a standard formulation Consider a social network made upof a number of companies or individuals Corresponding to each member of the network we consider a vertex andaccording to the relationship between the members between the corresponding vertices we also put an edge In thisway a graph corresponding to the members and communications in the community is obtained Whenever a person accepts a new product or idea we say that the corresponding vertex is activated every mem ber of the community needs the approval and acceptance of a number of trusted friends and acquaintances to accepta new product or idea in order to be convinced of accepting a new product Corresponding to this property amongindividuals we introduce a function in the graph and call it a threshold function The threshold function assigns toeach vertex of the graph a number that corresponds to the number of people who if convinced will be convinced Inother words the threshold function at the vertex v represents the minimum number of active neighbors v that activatethe vertex v What is of particular concern in all matters is the selection of the initial set to be activated in such a way that themaximum profit is obtained at the lowest cost In other words we activate a subset of graph vertices in the first stepand look for the maximum number of active vertices in the last execution On the one hand reducing the size of theinitial set and on the other hand enlarging the final active set is the optimal mode This issue selects the target set Orcalled TSS for short ۴

كلنات، نيلوفر

انتشار تاثير در شبكه هاي اجتماعي

انتخاب مجموعه هدف , مجموعه هدف بهينه , الگوريتم هاي تقريبي , الگوريتم هاي پارامتري , شبكه اجتماعي , بازاريابي ويروسي , انتشار در شبكه هاي اجتماعي