Show simple item record

dc.contributor.advisorNarahari, Y
dc.contributor.authorNarayanam, Ramasuri
dc.date.accessioned2014-08-01T05:27:24Z
dc.date.accessioned2018-07-31T04:38:28Z
dc.date.available2014-08-01T05:27:24Z
dc.date.available2018-07-31T04:38:28Z
dc.date.issued2014-08-01
dc.date.submitted2011
dc.identifier.urihttps://etd.iisc.ac.in/handle/2005/2350
dc.identifier.abstracthttp://etd.iisc.ac.in/static/etd/abstracts/3023/G24703-Abs.pdfen_US
dc.description.abstractWith 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.en_US
dc.language.isoen_USen_US
dc.relation.ispartofseriesG24703en_US
dc.subjectGame Theoryen_US
dc.subjectSocial Networksen_US
dc.subjectSocial Network Analysisen_US
dc.subjectSocial Networks - Influential Nodesen_US
dc.subjectSocial Networks - Community Detectionen_US
dc.subjectSocial Network Formationen_US
dc.subjectSocial Networks - Game Theoretic Modelen_US
dc.subjectShapley Valueen_US
dc.subject.classificationComputer Scienceen_US
dc.titleGame Theoretic Models For Social Network Analysisen_US
dc.typeThesisen_US
dc.degree.namePhDen_US
dc.degree.levelDoctoralen_US
dc.degree.disciplineFaculty of Engineeringen_US


Files in this item

This item appears in the following Collection(s)

Show simple item record