Game Theoretic Models for Social Network Science

August 28, 2017 Leave a comment

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.

Categories: Uncategorized

Cognitive Computing Approach for Commodity Price Prediction

August 10, 2017 Leave a comment

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:

Categories: Uncategorized

ACM EC 2012 and AAMAS 2012 Accepted Papers

April 27, 2012 Leave a comment

Here is the list of accepted paper of ACM EC 2012 .
Here is the list of accepted paper of AAMAS 2012 .

The following are a few papers from AAMAS 2012 that are relevant to Social Networks:

  • Identifying Influential Agents for Advertising in Multi-agent Markets
    Mahsa Maghami, Gita Sukthankar
  • Fair Allocation Without Trade
    Avital Gutman, Noam Nisan
  • Optimal Incentive Timing Strategies for Product Marketing on Social Networks
    Pankaj Dayama, Aditya Karnik, Yadati Narahari
  • Sustaining Cooperation on Networks: An Analytical Study based on Evolutionary Game Theory
    Raghunandan Ananthasayanam, Subramanian Chandrasekarapuram
  • Agents of Influence in Social Networks
    Amer Ghanem, Srinivasa Vedanarayanan, Ali Minai
  • The Emergence of Commitments and Cooperation
    The Anh Han , Luis Moniz Pereira , Francisco C. Santos
  • A Decision-Theoretic Characterization of Organizational Influences
    Jason Sleight, Ed Durfee
  • A Scoring Rule-based Mechanism for Aggregate Demand Prediction in the Smart Grid
    Harry Rose, Alex Rogers, Enrico Gerding
  • A New Approach to Betweenness Centrality Based on the Shapley Value
    Piotr Szczepanski, Tomasz Michalak, Talal Rahwan
  • Modeling and Learning Synergy for Team Formation with Heterogeneous Agents
    Somchaya Liemhetcharat, Manuela Veloso


The following are a few papers related to social networks from ACM EC 2012.

  • Thanh Nguyen. Coalitional Bargaining in Networks
  • Sharad Goel, Duncan Watts, Daniel Goldstein. The Structure of Online Diffusion Networks
  • Michael Kearns, Stephen Judd and Yevgeniy Vorobeychik. Behavioral Experiments on a Network Formation Game
  • Fabio Drucker and Lisa Fleischer. Simple Sybil-Proof Mechanisms for Multi-Level Marketing
  • Flavio Chierichetti, Jon Kleinberg and Alessandro Panconesi. How to Schedule a Cascade in an Arbitrary Graph
  • Moshe Babaioff, Shahar Dobzinski, Sigal Oren and Aviv Zohar. On Bitcoin and Red Balloons
  • Sanjeev Arora, Rong Ge, Grant Schoenebeck and Sushant Sachdeva. Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach
  • Jens Witkowski and David Parkes. Peer Prediction Without Common Prior
  • Nicole Immorlica, Rachel Kranton and Greg Stoddard. Striving for Social Status
  • Eytan Bakshy and Dean Eckles. Effects of Social Cues and Tie Strength in Social Advertising: Evidence from Field Experiments

WSDM 2012 Accepted on Social Networks

December 5, 2011 Leave a comment

Please find the list of accepted papers of WSDM 2012 here. Among those accepted papers, the following papers are related to social networks:

  • Multi-Relational Bayesian Probabilistic Ranking leveraging Social Network Data
    Artus Krohn-Grimberghe, Lucas Drumond, Christoph Freudenthaler and Lars Schmidt-Thieme
  • Maximizing Product Adoption in Social Networks
    Smriti Bhagat, Amit Goyal and Laks V. S. Lakshmanan
  • The Life and Death of Online Groups: Predicting Group Growth and Longevity
    Sanjay Kairam, Dan Wang and Jure Leskovec
  • When Will It Happen? — Relationship Prediction in Heterogeneous Information Networks
    Yizhou Sun, Jiawei Han, Charu Aggarwal and Nitesh Chawla
  • Understanding Cyclic Trends in Social Choices
    Anish Das Sarma, Sreenivas Gollapudi, Rina Panigrahy and Li Zhang
  • What’s in a Hashtag? Content based Prediction of the Spread of Ideas in Microblogging Communities
    Oren Tsur and Ari Rappoport
  • Daily Deals: Prediction, Social Diffusion, and Reputational Ramifications
    John Byers, Michael Mitzenmacher and Georgios Zervas
  • Effects of User Similarity in Social Media
    Ashton Anderson, Dan Huttenlocher, Jon Kleinberg and Jure Leskovec
  • Finding Your Friends and Following Them to Where You Are
    Adam Sadilek and Henry Kautz
  • How to Win Friends and Influence People, Truthfully: Influence Maximization Mechanisms for Social Networks
    Yaron Singer
  • Inferring Social Ties across Heterogenous Networks
    Jie Tang, Tiancheng Lou and Jon Kleinberg
  • How User Behavior is Related to Social Affinity
    Rina Panigrahy, Marc Najork and Yinglian Xie
  • Object Matching in Tweets with Spatial Models
    Nilesh Dalvi, Ravi Kumar and Bo Pang
  • Exploring Social Influence via Posterior Effect of Word-of-Mouth Recommendations
    Junming Huang, Xue-Qi Cheng, Hua-Wei Shen, Xiaolong Jin and Tao Zhou
  • Collaborative Ranking
    Suhrid Balakrishnan and Sumit Chopra

ICTS: School-cum-Workshop on Network Science in EE and CS

October 31, 2011 Leave a comment

Mathematics and its applications permeate a significant amount of research currently being carried out at the Indian Institute of Science (IISc). Recognizing this, an “IISc Mathematics Initiative (IMI)” was setup to foster interdisciplinary collaborations between different research areas with mathematics as the common theme. Such collaborations would help scientists and engineers solve research problems requiring inputs from mathematicians.
As part of IMI yearly activities, it maintains a theme for all those events that happen in a given year. Following this trend, for this academic year 2011-2012, the theme is “Mathematics of Networks”. As part of this, the following events are planned by the organizing committee:

  • Workshop on Introduction to Network Science
    (August 29 – September 02, 2011)

  • Workshop on Networks: Structure and Function
    (November 04 – 05, 2011)

  • Associated Workshop on Mathematics in Network Science: Implications for Socially-Coupled Systems
    (One week in November, 2011)

  • ICTS School on Network Science in Electrical Engineering and Computer Science
    (January 02 – 07, 2012)

  • ICTS Workshop on Network Science in Electrical Engineering and Computer Science
    (January 09 – 14, 2012)

  • Workshop on Social Networks
    (February 14 – 18, 2012)

  • Workshop on Network Science in Biology
    (One Week in March/April 2012)

  • School on Networks in Biology, Social Science and Engineering
    (July 02 – 13, 2012)

  • International Conference on Networks in Biology, Social Science and Engineering
    (July 16 – 20, 2012)

The following is the email from Indian Institute of Science (IISc) Mathematics Initiative “Networks Year” Organizing Committee
to call for the up-coming ICTS Workshop on Network Science in Electrical Engineering and Computer Science
(January 09 – 14, 2012)


Dear All,

School-cum-Workshop on Network Science in Electrical Engineering and
Computer Science

Dates: School: January 02 – 07, 2012
Workshop: January 09 – 14, 2012

Venue: Indian Institute of Science, Bangalore

We are pleased to announce ICTS School-cum-Workshop on Network Science in
Electrical Engineering and Computer Science, organized as part of IISc
Mathematics Initiative (IMI) Thematic year on Network Science (2011-12).

The new and emerging field of Network Science is based on the simple
observation that large human engineered systems (e.g., communication
networks, information networks, social networks, etc.) and natural systems
can be modeled as networks of entities. Hence, it is possible that common
principles can be brought to bear on the analysis, design and control of
such systems. In addition, insights gained from networks in one domain
could be brought to bear on understanding networks in other domains.

For the past few years, Network Science has been an exploding research
area transcending disciplinary boundaries, receiving the attention and
inputs from leading figures in mathematics, physics, biology, engineering,
and many other disciplines.

The purpose of this event is to take stock of the current developments and
trends, to build bridges across disciplines in the Indian research
community interested in networks research, and to alert and expose young
students and faculty to the potentialities begging for their attention and
efforts. While “Network Science” can be very broadly defined, the scope of
this event will be limited to the domains arising in Electrical
Engineering and Computer Science, and various related tools from

Registration is mandatory for all participants. If you are interested in
attending the school and workshop, please follow the steps below:

Step 1: Click on the link

Step 2: Click on Application form

Step 3: First register as an ICTS User you will receive the registration
link to your e-mail ID

Step 4: Click on the registration link and fill in your Profile details
and save.

Step 5: Click on the program link :

Step 6: Click on Apply on top

Step 7: Fill in your Current Research and other fields and save.

Step 8: Log out

Deadline for registration: November 15,2011

To know more details of the programme visit

IISc Mathematics Initiative “Networks Year” Organizing Committee


SAGT 2011 Accepted Papers on Social Networks

October 30, 2011 Leave a comment

Here is the list of accepted papers in SAGT 2011 (4th Symposium on Algorithmic Game Theory). The following are a few papers from SAGT 2011 on social networks:

  • Diffusion in Social Networks with Competing Products
    Krzysztof Apt and Evangelos Markakis

  • A Clustering Coefficient Network Formation Game
    Michael Brautbar and Michael Kearns

  • On Dynamics in Basic Network Creation Games
    Pascal Lenzner

WINE 2011 Accepted Papers on Social Networks

October 30, 2011 Leave a comment

Here is the list of accepted papers in WINE 2011 (7th Workshop on Internet & Network Economics) . The following are a few papers from WINE 2011 that are related to social networks:

  • Optimal Pricing in Social Networks with Incomplete Information
    Wei Chen, Pinyan Lu, Xiaorui Sun, Bo Tang, Yajun Wang and Zeyuan Allen Zhu

  • Natural Models for Evolution on Networks
    George Mertzios, Sotiris Nikoletseas, Christoforos Raptopoulos and Paul Spirakis

  • Behavioral Conflict and Fairness in Social Networks
    Michael Kearns, Stephen Judd and Yevgeniy Vorobeychik

  • Social Learning in a Changing World
    Rafael Frongillo, Grant Schoenebeck and Omer Tamuz