DIMACS
DIMACS REU 2023

General Information

me
Student: Jordan Chong
Office: CoRE 450
School: New York University
E-mail: jordan.chong@nyu.edu
Mentor: Dr. Jie Gao

Project Description

Truth Learning in a Social Setting:

Individuals gather information by both independent observations and communication with others in a social environment. Social Learning studies how dispersed and self-interested agents aggregate information. In this project we study whether social learning can enable truth learning. It is well known that learning can fail due to herding, where agents collectively focus on an early false consensus and ignore subsequent observations. Therefore a general goal in social learning is to characterize when truth learning is guaranteed. In this project we study the computational problem of social learning with different observation models, the environment of learning and social processes such as peer pressure, social influence and network effect. (From DIMACS REU Website)

Weekly Log

Week 1:
Week 2:
  • We built a basic simulation of social networks and information cascades and ran a few test cases using some graphs (Bipartite "Celebrity," n-cliques, Watts-Strogatz small world, trees, etc) on a random ordering of agents. We were able to reproduce some expected results that aligned with previous work in the field
  • I continued to do literature review reading select chapters from "Networks, Crowds, and Markets" by Easley and Kleinberg and "Algorithm Design" by Kleinberg et al.
  • I also read more papers relating to social networks including "Multi Issue Social Learning" by Bahar et al.
  • We are beginning to formulate more focused research questions on finding the best ordering of agents and local learning requirements as defined by Arieli et al.
Week 3:
  • Attended a few talks in the Modern Techniques in Graph Algorithms Workshop hosted by DIMACS
  • Read "Maximizing the Spread of Influence through a Social Network" by Kleinberg et al which prompted some ideas about algorithms for optimal ordering and proving the hardness of our problem
  • Read about oriented graphs and the Gallai-Hasse-Roy-Vitaver Theorem which proves equality between the minimal longest path of all orientations of a graph and valid coloring of a graph
  • We continued to update our simulation model to reflect our new ideas and began to see positive results with preferential attachment networks
Week 4:
Week 5:
  • Attended a workshop on Ramsey Theory which covered the basic results of Erdos and Szekeres
  • Attended a workshop on proof by example which discussed a way of using computers to help prove theorems related to sequences, series, and patterns
  • Read "How to Schedule a Cascade in an Arbitrary Graph" by Kleinberg et al and "Optimizing Information in the Herd: Guinea Pigs, Profits, and Welfare" by Daniel Sgroi
  • Continued to work on our simulation model algorithm on preferential attachment networks and also in more general cases
  • We are beginning to shift our focus towards learning more about the way graph topology affects learning rate, specifically focusing on graphs in which all ordering of agents will fail to reach asymptotic learning and ones in which random ordering performs poorly but a forced ordering leads to successful learning
    • We began to see some interesting observations regarding clustering, the Watts-Strogatz model, and the Connected Cave Man model
  • We are also interesed in looking into the importance of high value nodes in starting positive or negative cascades to reach successful learning
Week 6:
  • I continued to look more closely into the Connected Cave Man model. It has interesting properties with its variance compared to a complete graph on the same number of nodes
  • We are beginning to try to look into bounds of learning rates given a specific graph or family of graphs and private signal rates. We want to bound the learning rate using a random ordering and the learning rate given an optimal ordering of agents
  • I calculated an upper bound for a sequential ordering of the Connected Cave Man graph which can serve as a lower bound of the optimal ordering
  • I attended a graduate school panel where we had the chance to ask some graduate students and heads of departments about graduate school applications and what we can do to prepare for them
Week 7:
  • I was able to calculate an expected network learning rate of the Connected Cave Man graph on my ordering
  • I am trying to prove the success rate of the Connected Cave Man graph is monotonically increasing learning rate in our ordering in order to bound the optimal and random ordering on it
  • In showing monotonicity within CCM, I believe I will be able to show that I have optimal ordering for CCM
  • We visited the IBM Watson Research Labs and got to see some quantum computers and hear from researchers about their work at IBM
Week 8:
  • We were able to prove the success rate of the Connected Cave Man graph is monotonically increasing and converges, bounded away from 1
  • We continued to work on proving optimality for our ordering in CCM
  • We created our final presentation showcasing our work and results from the summer and presented it to DIMACS
Week 9:
  • We wrote up our final report, summarizing our findings and work from the summer

Presentations

Additional Information