dimacs logo

General InformationProject DescriptionProject LogLinks

General Information

Jing Li
lijing [at] mit [dot] edu
CoRE 336
Massachusetts Institute of Technology
Faculty Advisor:
Liviu Iftode, Computer Science
S. Muthukrishnan, Computer Science
Game-theoretic analysis of climbing social ladders in social networks

Project Description

In social networks (say Facebook), there are rules for how people discover each other and become friends. For example, say person A desires to become friends with B. The rules constraint A's ability to become B's friend outright and induces a game-theoretic component. A has to judiciously make other intermediate friends in order to eventually become B's friend. The project will involve modeling this situation, studying the game theory and dynamics of various parties, and understanding the price of anarchy and stability of the game. The situation above is an example of a more general phenomenon in networks where people learn and gain trust of others incrementally for nefarious (in DHS settings) or potentially harmless (in social networks) purposes.

Presentation 1 (pdf)

Project Log

Week 1: Explored literature on social capital and link formation in social networks.

Week 2: Developed preliminary model of strategic network formation and prepared for Friday's presentation.

Week 3-4: Met with Muthu and REU participant from 2009, formalized the friendship formation problem as an optimization problem.

Week 5:
Met with Liviu, Mangesh and Pravin, brainstormed ideas on social ranking, specifically, in aggregating local preferences into a global ranking.

Week 6:
Met with one of Muthu's students to explore other ideas for social networks research, and to bounce ideas for our social ranking idea. Began implementing preliminary algorithm for finding rankings that minimize mental agony. Conducted literature search on social rankings/hierarchies.

Week 7 -8:
Met with everyone and brainstormed even more about what we can do with our ranking procedure. I finished the implementation, we sampled two datasets from the Twitter graph, and tested the algorithm on those datasets.

After the program:
I've continued working on the implementation of the algorithm, fixing bugs, changing around the labeling algorithm, and trying it on various graphs like football team rankings or wiki-votes datasets. I'll post more updates as our project and paper progresses. - 7/27/2010

Links and References (Added as the summer progresses)

Rutgers DIMACS

Top of Page