Archive for the ‘Uncategorized’ Category

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

Facebook Fellowship Program

January 7, 2011 Leave a comment

Facebook has stated graduate (Ph.D.) student fellowship program in the academic year 2010-2011. Now its time for applications for Facebook Graduate (Ph.D.) Students Fellowship Program for the academic year 2011-2012. The amazing issue for the academic year 2011-2012 is that Facebook is accepting applications from Ph.D. students studying at international universities in addition to applications from Ph.D. students studying in the United States. The following is the formal description of this fellowship as per Facebook website:

Every day Facebook confronts the most complex technical problems and we believe that close relationships with the academy will enable us to address many of these problems at a fundamental level and solve them. As part of our ongoing commitment to academic relations, we are pleased to announce the continuation of the Facebook Fellowship program to support graduate students in the 2011-2012 school year..

Each Facebook Fellowship includes:
· Tuition and fees will be paid for the academic year.
· $30K stipend (paid over 9 months of the academic year).
· $5K per year toward conference attendance and travel.
· $2.5K toward a personal computer.
· Opportunity to apply for a paid summer internship.
· Recipients are responsible for the taxation on any funds.

Topical Areas: Facebook is interested in a wide range of academic topics, including the following topical areas:

* Computational Advertising
* Computer Vision
* Compiler Technology
* Computer Architecture
* Computer Networking
* Computer Security
* Databases
* Data Mining
* Distributed Computing
* Fault Tolerance
* Human-Computer Interaction
* Internet Economics
* Machine Learning
* Machine Translation
* Natural Language Processing
* Search
* Smart Datacenters
* Social Computing

Application Timeline:
* December 20, 2010: Launch of Fellowship for 2011-2012 academic year
* February 28, 2011: Applications for fellowships must be submitted in full
* April 8, 2011: Award recipients will be notified by email of their acceptance

For more information, please visit Facebook Fellowship Program.

2010 in review

January 3, 2011 Leave a comment

The stats helper monkeys at mulled over how this blog did in 2010, and here’s a high level summary of its overall blog health:

Healthy blog!

The Blog-Health-o-Meter™ reads This blog is doing awesome!.

Crunchy numbers

Featured image

A helper monkey made this abstract painting, inspired by your stats.

A Boeing 747-400 passenger jet can hold 416 passengers. This blog was viewed about 1,400 times in 2010. That’s about 3 full 747s.

In 2010, there were 21 new posts, not bad for the first year! There were 6 pictures uploaded, taking up a total of 927kb.

The busiest day of the year was September 23rd with 26 views. The most popular post that day was Yahoo! Research Head Dr. Prabhakar Raghavan’s Interview Highlights on Social Influencers .

Where did they come from?

The top referring sites in 2010 were,,,, and

Some visitors came searching, mostly for ramasuri narayanam, leading researchers in social networks, innovations in computer science 2011, ramasuri blog, and sdm 2010 accepted papers.

Attractions in 2010

These are the posts and pages that got the most views in 2010.


Yahoo! Research Head Dr. Prabhakar Raghavan’s Interview Highlights on Social Influencers August 2010


WINE 2010 Papers on Social Networks September 2010


Innovations in Computer Science – ICS 2011 July 2010


About June 2010
1 comment


Leading Researchers and Groups in Social Networks with Computer Science Flavour July 2010

Categories: Uncategorized