Ramasuri Narayanam  Ramasuri Narayanam photo       

contact information

Research Scientist
IBM Research, India
  +91dash80dash670dash43817

links



Tutorial: "Strategic, Online Learning, and Computational Aspects of Social Network Science"

Authors:Ramasuri Narayanam, Y. Narahari
Email: Email: ramasurn@in.ibm.com and hari@csa.iisc.ernet.in

 

Abstract:

This tutorial provides the conceptual underpinnings of the use of game theoretic models as well as online multi-agent learning models in social network analysis and brings out how these models supplement and complement existing approaches for social network analysis. In the first part of the tutorial, we provide rigorous foundations of relevant concepts in game theory, mechanism design, network science, and online learning in multi-agent network systems. In the second part of the tutorial, we bring out how game theoretic approach and online multi-agent learning approach help analyze key problems in network science better and also how to apply these technical concepts to problem solving in a rigorous way. In particular, we present a comprehensive study of a few contemporary and pertinent problems in social networks such as social network formation games, social network monetization, design of incentive mechanisms, and economics of networks.

 

Contents:

  1. Social Networks: A Quick Primer (20 Minutes)
    • Definitions and Examples
    • Different Approaches for Social Network Analysis
    • Key Tasks in Social Network Analysis
  2. Foundational Concepts in Game Theory (40 Minutes)
    • Strategic Form Games
    • Nash equilibrium
    • Cooperative Games with Transferable Utilities
    • The Core, Shapley value
    • Introduction to Mechanism Design
  3. Strategic Aspects of Social Network Science (30 Minutes)
    • Motivation for Game Theoretic Models
    • Key Topics in Strategic Aspects of Network Science
      • Network Formation Games
      • Game Theoretic Centrality Measures
      • Social Network Monetization
      • Multi-Armed Bandit Mechanisms
  4. Network Formation Games (35 Minutes)
    • Determinants of Network Formation
    • State-of-the-art Models for Network Formation
    • Stability and Efficiency
    • Network Formation Games with Local Information
  5. Game Theoretic Centrality Measures (35 Minutes)
    • Motivation
    • General Methodology to Design Game Theoretic Centrality Measures
    • Connectivity Games
    • Computational Aspects and Efficient Algorithms
    • Application to Real World Problems
  6. Online Learning Aspects on Networks (35 Minutes)
    • Online Influence Maximization Problem (or Viral Marketing)
    • Models of Information Diffusion
    • Efficient Algorithms for Off-line Viral Marketing
    • Efficient Algorithms for Online Viral Marketing
    • Mechanisms for Stochastic Multi-armed Bandit Problems
  7. Conclusions and Discussion (15 Minutes)
    • Summary of the Tutorial
    • Key Resources
    • Exciting New Problems in the Area

 

Slide Materials:

Click here for AAAI 2018 Relevant Slide Materials