Image and video hosting by TinyPic

General InformationProject DescriptionProject LogLinks

General Information

Ajay Mattappallil
CoRE 634
Rutgers University
Faculty Advisor:
Midge Cozzens, Mathematics, Rutgers University
A Game Theory Approach to Cascading Behavior in Networks

Project Description

This project will study the rapid flow of information in large social networks. This is important in "viral marketing" and comes out of early work done on the spread of epidemics and social network theory. A graph is built with nodes representing individuals in a population and an edge between two nodes if they have some form of communication. Each node has a choice of two behaviors, an old behavior and a new behavior, and an incentive (payoff) for matching behaviors. Each node plays the coordinated game with each neighbor and the payoff for a node is the sum of the individual game payoffs. A sample problem is to determine the k most influential people in the network, an NP-hard problem. We seek variations on the model, such as weighting the edges with other payoffs (e.g., with marketing strategies of price reductions) to better determine the most influential players (often those to start marketing to).

Presentation 1 (ppt)

Presentation 2 (ppt)

Project Log

Week 1: This week I met with Professor Cozzens and my group members to review over the problem(s) that we would be reseraching this summer. She also provided us with supplementary readings.

Week 2: The papers that we were given were quite technical in nature, but I eventually understood the background of the problem. The readings mainly focused on viewing the interactions that occur in viral behavior. I was still slightly unclear on where to take this project, so Professor Cozzens provided us with more readings.

Week 3: After going through these new readings, I had a firm grasp on the beginnings of my project. Many of the literature I went through repeated the same concepts more or less. They viewed the node to node interactions with the same model. No one quite delved into either the game or graph theoretic portions. I began to work on the game theory part.

Week 4: By the end of this week, I had put together the first draft of my game theory model for the incentives that companies should use to entice a primary customer base. I showed it to Professor Cozzens, and she revised it and pointed me in the right direction to improve it.

Week 5: My game theoretic incentive model had finally come together. I decided now to move towards the graph theory.

Week 6: With the help of Doctor Cozzens, I put together a few different approaches to improving marketing through graph theory. These approaches included using dominating sets, clique partitioning, and Eulerian paths.

Week 7: I moved back towards the game theory and created some more models, so I could simulate a game and a payoff matrix.

Week 8: I put together my findings in a paper.

Links and Resources


Influential Nodes in a Diffusion Model for Social Networks (David Kempe, Jon Kleinberg, Eva Tardos)

Diffusion on Social Networks (Matthew O. Jackson)

The Diffusion of Innovations in Social Networks (H. Peyton Young)

Information Diffusion in Online Social Networks (Lada Adamic)

Diffusion in Complex Social Networks (Dunia Lopez-Pintado)

Social Networks and the Diffusion of Economic Behavior