Game Theoretic Models for Social Network Science
Social networks are social structures made up of individuals (or autonomous entities) and connections among those individuals. These connections represent the patterns of communication among these individuals in networked systems. Social networks are usually modeled using graphs where nodes represent the individuals and the edges represent the relationship (such as friendship, co-authorship, citation, etc.) between these nodes. Recently, there has been a large surge of interest from the research community to study social networks (and in general network science) because of the following reasons:
(1)Such networks are fundamentally different from technological networks.
(1.a) It is observed that the degrees of adjacent vertices in networks are positively correlated in social networks unlike other networks;
(1.b) The level of clustering appears to be far greater than we expect by chance. And, the level of clustering in non-social networks is no greater than one would expect by chance.
(2) Networks are powerful primitives to model several real-world scenarios. A few such examples are friendship networks, co-authorship networks, world wide web, email networks, citation networks, trading networks, R&D networks, etc.
Social Network Analysis
The focus of a significant amount of research in Network Science is to understand the structural properties of social networks – for example degree distribution, average number of edges per node, density of edges, diameter of the network – and these studies are based on the tools and techniques from social network analysis (SNA). Essentially SNA helps for both studying the complex communication patterns among the individuals in the network and measuring the strength of relationships between the connected individuals. Apart from its extensive use in social sciences, SNA has been applied in areas ranging from biology, business organization, electronic communications, physics, psychology, etc. The existing research trends in SNA can be broadly classified into two major categories based on the granularity of information used in the specific approach:
(i) node/edge centric analysis, and
(ii) network centric analysis.
Below is a brief description of each of these two approaches:
Node/Edge Centric Analysis: Here the focus is on the design and analysis of metrics and measures targeted around the individual nodes/edges in the network. A few examples of this line of work include Centrality Measures, Link Prediction, and Anomaly Detection.
Network Centric Analysis: Here the focus is on modeling and analysis of the network as a whole. A few important examples of this class of research include Community Detection, Frequent Subgraph Discovery, Graph Visualization, and Graph Summarization.
Motivation for Game Theoretic Models
The field of social network analysis comprises a rich suite of measures and tools based on techniques from graph theory, spectral theory, optimization theory, sociology and all this machinery in Network Science is useful to measure the structural properties of social networks. In fact, generative models can reproduce networks having similar/same structural properties of certain observed graphs. However, the current approaches in network science are inadequate for the following reasons:
a) They do not satisfactorily capture the behavior of the individual nodes in social networks. For example, the individuals often tend to be strategic, as individuals in social networks are autonomous, intelligent, and rational.
b) They do not explicitly capture the dynamics of strategic interaction among these individuals in the networks.
c) Social contacts (i.e. links) form more often by choice than by chance.
Game theory is a natural tool to overcome this inadequacy since it provides rigorous mathematical models of strategic interaction among autonomous, intelligent, and rational individuals (or players). In this way, game theory helps to fill this fundamental research gap. In other words, game theoretic models supplement and complement existing approaches for social network analysis. Recently there have been a few efforts from research community towards this end. For example, the Ph.D. thesis of Siddharth Suri studies the effect of network topology on the strategic behavior of nodes when they could interact only with their neighbors. In what follows, a glimpse of the game theoretic models for certain important problems in social network analysis is presented:
Social Network Monetization: One of the most popular approaches to monetize user activities on social networks is Advertising. The success of any advertising campaign depends on the design of intelligent marketing strategies, rewards, and cash-backs. The more recent work (Arthur et. al., EC 2009; Dutting, Henzinger, Weber, WWW 2010; Hartline et. al., WWW 2008) focuses on designing efficient pricing strategies for viral marketing and optimal cash-backs. The primary tools and techniques in these models come from game theory and mechanism design.
Social Network Formation: This problem involves the design of the models for strategic interaction among rational and intelligent individuals in the network. These models should be able to capture the dynamics of interaction and could predict the topologies of networks with certain properties such as equilibrium and efficiency. For a comprehensive treatment of this line of work, please refer to Goyal, Connections: An Introduction to the Economics of Networks. Princeton University Press, 2007; Jackson, Social and Economic Networks, Princeton University Press, 2008.
Bargaining on Networks: This problem deals with bargaining on social networks, wherein the players are represented by vertices and the edges represent bilateral opportunities for deals between pairs of players. Each deal yields some fixed wealth if its two players can agree on how to divide it; otherwise it yields no wealth. The goal of each player is to maximize his/her own wealth given the various alternatives represented by the graph of the underlying social network. Several models in the literature identify that the application of the well-known Nash bargaining solution to the case of multiple agents interacting on a graph is effective.
The above settings clearly bring out that the game theoretic models help to analyze social networks better as well as how to apply the game theoretic concepts to problem solving in a rigorous way. The game theoretic models are appropriate for social network analysis from two perspectives:
(a) Game Theoretic Models are Essential for Social Science. A few representative problems in this category are Network formation games, Game theoretic centrality design, and bargaining on networks.
(b) Game Theoretic Models Complement the existing State-of-the-Art Algorithms. A few representative problems in this category are Target Node Selection (Viral Marketing), Decentralized Community Detection.
The topic of “Game Theoretic Models for Network Science” provides conceptual underpinnings of the use of game theoretic models for social network science and brings out how these models supplement and complement existing (CS and Sociology based) approaches for social network analysis.
Cognitive Computing Approach for Commodity Price Prediction
Here I want to share a post on “Cognitive Computing based Commodity Price Prediction”. This article is written One of my colleagues (Manish Kataria) at IBM Research – India:
https://www.linkedin.com/pulse/using-cognitive-computing-commodity-prediction-manish-kataria?lipi=urn%3Ali%3Apage%3Ad_flagship3_profile_view_base_post_details%3BC%2BI74BYWTj6J7YO01QxMvg%3D%3D
Ramasuri Narayanam's Blog 