Well, here I am at my third and final shot at making an REU worthwhile. My first one was a great learning experience, but I really didn’t know enough at that point to really take advantage of the “research” opportunity. I think I was ready to do some serious stuff for the second one, but it turned out to be a terrible experience in almost all facets. This one is starting strong. We have 13 students so far (we have one more to come) and we seem to have a good social dynamic going on. Im excited to see where the summer leads us around LA.
My project this year is infinitely better than what it was last year. My chief complaint from last summer is that my advisor treated me like a small child with minimal knowledge of what programming was; my advisor this year says he’s going to treat me like a 5th year PhD student who has passed all exams and has read all the literature unless I tell him to slow down and explain something. From our early meetings, its pretty clear that I will be taking advantage of the “slow down and explain something” option quite frequently.
So I’m getting my start in CS theory research this summer. We are considering the problem of maximizing the spread of your influence on a graph. We have a model where at each time step, a node will choose one of its neighbors at random and change to whatever color that node is in the next time step. Before this process begins, you are given an amount of money M that you can spend on nodes to color them your color, assuming that each node has its own activation cost. We would like to find a set of nodes S, such that the total initial cost of those nodes < M that will maximize the expected number of nodes that will be your color after T timesteps. This problem is motivated by the case where a company is looking to pay some people to initially adopt their product in order to spread the adoption of their product throughout the network. Two natural examples of this would be publishers giving out free textbooks to professors in hopes that they will adopt the textbook for their class and other professors will do the same after seeing the original professor use that textbook or paying certain people to start using a social networking site (like Twitter) in hopes that others will join because of the influence of those people.
When we are done researching that simple version, we will explore what happens when there are two companies, A and B, with the same finite amount of resources and nodes will adopt technology A or B with probability proportional to how much money each company has spent on them. In this scenario, I have already looked at a simple probability function where A has already made all of its moves and found an optimal algorithm for B (of course, it is not a polynomial time algorithm, but its better than the “try everything” approach). In the future, we are going to look at equilibria in the game. That is, if A knows how B will react given a strategy for A, what can player A do to preempt B and choose a strategy that will be worse for B when B reacts to it.
There is a fair bit more technical detail to what is going on and I have much more to learn, but I am really enjoying what I have done so far. Hopefully, it will remain that way.
