I have been trying to align myself with the science of "Online Social Network Analysis" as well. I strongly believe it should be part of OR, not only it deals with sophisticated algorithms but it is also related to many of IE topics, like Human Factors and Psychology

Here are some basic suggestions:

1- (Reputation Algorithms) Ask them to invent a new page rank algorithm for reputation of people in a social network like tweeter. The algorithm has to be robust (minorities cannot manipulate it) [and please let us know if they succeeded in solving it]

2- (Mutually Trusted Node) If I know somebody on LinkedIN what is the best way for me to send him my message?. I can obviously send him a message directly but he may not even answer, but I can ask somebody in our mutual network who knows me and him both and I may talk to that third person to send my message to that hotshot on LinkedIN. The question is how do you algorithmically find that node on your network?

3- (Numerical Techniques) How do you sample from a huge network, like a web-graph or members of tweeter, how do you inverse a large matrix that is generated from tweeter?

4- If they don't want to read about advanced algorithms you can give them a dataset and ask them to implement a simple recommendation algorithm (something like Daniel Lemire's SLOPE ONE)

We would definitely appreciate if you could please post their final project online

Bear with me, because this really isn't my area and I don't know the correct terminology. There's research on identifying and quantifying the influence of individuals in social networks (both digital and analog). Let's say I want to introduce a new service/application on Facebook. Let's further assume the underlying "friends" graph is somehow visible to me, and I have some measure of the influence of each node (and some function that describes how influence propagates across arcs, perhaps just an attenuation factor). I also have a function that tells me how much favorable opinion I can buy with each dollar spent marketing to a particular individual. I want to achieve the best overall penetration (so I probably a need something like a logistic regression model that predicts adoption based on the number and cumulative influence of friends who have adopted), and I have a budget and possibly other constraints (limits on how much I can spend on any one individual?).

There's clearly at least one estimation problem here, probably several, and ultimately an optimization problem (a MILP or MINLP, but maybe an LP would be "good enough for government work").

For an optimization problem I'd have to assume there's some sort of objective function. If you're a band on MySpace, you want to get people to listen to your music and come to your shows. If you're on LinkedIn and looking for a job, you want to attract the largest number of employers that whose needs match your skills. And maybe some users just want to maximize the number of views of their pages.

What is interesting about any of these, is how people's interest ebbs and flows over time. Even on sites like OR-Exchange or Stack Overflow, question and answer threads get hot and cold. I would suspect that any sort of analysis of social networking sites would have to take into account this 'lifecycle'. Where does this lifecycle come from? Is it a natural output of our attention span or is it a combination of the technology and some measurable behavior?

In the end, we all have sets of discrete choices: view/don't view, read/don't read, comment/don't comment, etc. Building up a model that describes this behavior might be the backbone to explore optimizing around the behavior. Discrete choice behavior to account for people's choices, markov processes to account for the stochastic nature of the changes in states, and some lifecycle growth and decline imposed on (or derived from) the overall process.

This is probably similar to Paul's approach above, but adds the phenomena of a lifecycle to the mix.

You blogged about Farmville.