The effect of antagonism on information propagation in social and technological networks (Master thesis)
The possession of massive digital records of human interactions (e.g., email or file exchanges, friendships or acquaintances, collaborations, phone calls, etc) in recent years provides a new system-wide perspective on social networks. In addition to observing and predicting patterns of collective human behavior, in many cases the dynamics of the network can be engineered. One such example is when attempting to initiate a large cascade by seeding it at certain ``influential'' nodes in the network to promote a novel idea or, a new product through word-of-mouth. The algorithmic challenge of selecting individuals who can serve as early adopters in a manner that will trigger a large cascade in the social network, is known as influence maximization. One might consider several metrics which estimate the ``importance'' of a node in a network. For example, it is well known that high-degree nodes are indeed quite influential in the network. Other popular metrics, such as Betweeness Centrality, Closeness Centrality, or Eigenvector Centrality, might also be considered as good candidates. Moreover, one might consider choosing seeds adaptively, e.g., by choosing the next seed given the subset of already chosen seeds so far. This thesis studies the effect of competition in influence maximization. We consider a scenario in which two competing firms try to advertise their own product within the same social network. The firms are assumed to assess the importance of the nodes in the network, as ``influencers'' of other nodes towards buying the same product. Each of them selfishly chooses an importance-assessment strategy, i.e., a metric (from a predetermined set of available metrics) to order the nodes in the network. Due to limitations of their advertising budget, each firm is assumed to be able to seed at most $k$ nodes. Therefore, given the importance-orders of the two firms, a seed-selection policy determines the k most important seeds per firm. We then consider two different information-propagation models (De Groot and Threshold) to simulate the dispersion of the new products in the entire network. The measure of success per firm is its own degree of penetration in the market, i.e., the fraction of nodes which will eventually adopt the firm's product. We have implemented algorithms for computing (exactly or in approximation, statically or adaptively) several quite popular importance-assessment metrics. We have also conducted extensive experimental evaluation of this scenario, in order to assess the validity of each importance assessment strategy, under the lens of competition between the two firms, in several benchmark data sets which are widely used in the literature.
|Institution and School/Department of submitter:||Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής|
|Keywords:||Ανταγωνισμός,Κοινωνικά Δίκτυα,Διάχυση Πληροφορίας,Antagonism,Competition,Information propagation|
|Appears in Collections:||Διατριβές Μεταπτυχιακής Έρευνας (Masters)|
Files in This Item:
|Μ.Ε. ΛΙΟΥΚΑ ΕΛΕΥΘΕΡΙΑ 2016.pdf||5.87 MB||Adobe PDF||View/Open|
Please use this identifier to cite or link to this item:This item is a favorite for 0 people.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.