Game Theoretic Models For Social Network Analysis

Autor: Narayanam, Ramasuri
Rok vydání: 2014
Předmět:
Druh dokumentu: Diplomová práce
Popis: With increasing demand for social network based activities, it is very important to understand not only the structural properties of social networks but also how social networks form, to better exploit their promise and potential. We believe the existing methods and tools for social network analysis have a major inadequacy: they do not capture the behavior (such as rationality and intelligence) of individuals nor do they model the strategic interactions that occur among these individuals. Game theory is a natural tool to overcome this inadequacy since it provides rigorous mathematical models of strategic interaction among autonomous, intelligent, and rational agents. This thesis brings out how a game theoretic approach helps analyze social networks better. In particular, we study three contemporary and pertinent problems in social networks using a game theoretic approach: determining influential individuals for viral marketing, community detection, and social network formation. The first problem deals with determining influential nodes in social networks for diffusion of information. We present an efficient heuristic algorithm (SPIN) to this problem based on cooperative game theoretic techniques. The running time of SPIN is independent of the number of influential nodes to be determined. Moreover, unlike the popular benchmark algorithms, the proposed method works well with both submodular and non-submodular objective functions for diffusion of information. In the second problem, we design a novel game theoretic approach to partition a given undirected, unweighted graph into dense subgraphs (or communities). The approach is based on determining a Nash stable partition which is a pure strategy Nash equilibrium of an appropriately defined strategic form game. In the proposed graph partitioning game, the nodes of the graph are the players and the strategy of a node is to decide to which community it ought to belong. The utility of each node is defined to depend entirely on the node’s local neighborhood. A Nash stable partition (NSP) of this game is a partition consisting of communities such that no node has incentive to defect from its community to any other community. Given any graph, we prove that an NSP always exists and we also derive a lower bound on the fraction of intra-community edges in any NSP. Our approach leads to an efficient heuristic algorithm to detect communities in social networks with the additional feature of automatically determining the number of communities. The focus of the third problem is to understand the patterns behind the evolution of social networks that helps in predicting the likely topologies of social networks. The topology of social networks plays a crucial role in determining the outcomes in several social and economic situations such as trading networks, recommendation networks. We approach the problem of topology prediction in networks by defining a game theoretic model, which we call value function -allocation rule model, that considers four determinants of network formation. This model uses techniques from both cooperative game theory and non-cooperative game theory. We characterize the topologies of networks that are in equilibrium and/or socially efficient. Finally, we study the tradeoffs between equilibrium networks and efficient networks.
Databáze: Networked Digital Library of Theses & Dissertations
Externí odkaz: