Research Paper Topics
Here are a few starting points for your explorations on finding a research paper topic.
UNDER CONSTRUCTION
- Link prediction: You have observed a network, but due to limitations in your methods of observation (or due to other reasons) you believe that
your network is missing some edges. How do you "predict" the missing edges based on domain knowledge and the structure of the partially observed network?
Alternately, you've observed a network at time t and want to "predict" new edges the network may acquire at a later time.
An early influential paper on this topic is "The Link Prediction Problem for Social Networks" by Liben-Nowell and Kleinberg in 2004. Since then the area
has taken off with a variety of machine learning techniques being applied to the problem.
Here is a nice presentation that surveys the current state of "link prediction."
Nitesh Chawla from Notre Dame, who is the colloquium speaker for Feb 10th, knows a lot about this topic.
- Community detection: Detecting clusters or communities in large real-world graphs such
as social or information networks is a problem of considerable interest. The problem of finding dense clusters
has been studied in the algorithmic community for a while now, but in the context of social networks the difficulty
is often in formalizing an intuitive notion one might have about what appropriate communities are in
the context of the application.
See the paper "Empirical Comparison of Algorithms for Network Community Detection" by
Leskovec, Lang, and Mahoney (WWW 2010) for a survey of different well-known techniques for
community detection.
Lately there has also been work on a very simple (and highly parallelizable) technique for community detection called
label propogation.
- The vaccination policy problem: This is the problem of finding a small number of people to vaccinate so as to minimize the spread
of disease. One way to model this is to assume a contact network via which disease spreads in a stochastic manner and then find a small subset
of vertices to remove from the network so as to limit disease-spread on the network that remains.
Superfically, this problem seems related to the viral marketing problem (see "Maximizing the Spread of Influence through a Social Network" by
Kempe, Kleinberg, and Tardos in KDD 2003), but the vaccination policy problem seems much harder than the viral marketing problem from an algorithmic
point of view.
What are "good" algorithms for this problem? Under what circumstances do they work?
See the dissertation of Donald Curtis for further discussion of this problem.
- Efficiently computing node "importance" in dynamic graphs:
For a variety of applications, it is useful to identify "important" nodes in a social network.
Measures such as page rank or betweenness are used to do this.
Often this problem appears in a dynamic context: you want to find an "important" node, delete it and
then find another "important" node and so on. In other words, you want to repeatedly find "important"
nodes in a dynamic network that is changing in a specific manner.
However, measures such as page rank or betweenness are not very cheap to compute and this computation becomes a bottle-neck when
we need to do this repeatedly.
Are there approximate notions of these importance measures that can be computed cheaply in an amortized
sense, over many repititions?
There are papers on "approximate" betweenness centrality (e.g., see this paper for a
technique based on adaptive sampling), but are the algorithms
in these papers fast enough?
- Optimization problems on models of social networks:
Many graph-theoretic optmization problems such as minimum dominating set (MDS) are NP-complete in general.
However, these problems may have efficient algorithms if the input network has properties
associated with social networks.
For example, MDS is easily solved on Erdos-Renyi random graphs.
Is it possible that MDS or other optimization problems such as maximum coverage can be easily solved on more complicated random graph models?
In general, can we identify models of social networks and optimization problems that are relatively easy on
these models, even though these problems are hard in general.
The paper "Structural and Algorithmic aspects of massive social networks" by S. Eubank et al. (SODA 2004) presents
one example of this phenomenon.
- Vaccination policy games on networks:
In SODA 2004, Aspnes et al. presented a paper "Inoculation strategies for victims of viruses and the sum-of-squares partition problem"
that models the vaccination problem in a game-theoretic setting. Nodes (individuals) are self-interested rational actors who
are weighing the cost of getting vaccinated versus the cost of free riding on vaccinated neighbors. Of course, if a node is
not vaccinated, then there is a positive probability of contracting the disease and nodes have to take the expected cost
of this into account. The results in this paper
are very interesting, but the model is highly stylized and it would be interesting to see if there are more realistic
extensions to this model in which clean and interesting results can still be obtained.
Chris Bauch, from the University of Guelph has done a lot of work on
the applications of game theory to the design of vaccination policies.
He is a speaker in our colloquium series later this semester.
- Efficiently generating random graph models of social networks:
An important strand in social network research is figuring out which structural aspects of a social network
are critical to an application and then developing random graph models that capture this aspect.
This is typically followed by the design of algorithms for generating random graphs with particular structural
features fixed.
For example, one might want to generate random graphs with specific clustering coefficient or specific assortativity or
some combination of specified properties.
For example, there was a recent paper byN .Khanh and D.A.Tran titled
"On generating power-law networks with assortative mixing.".
There are many open problems of interest to computer science students in the area of algorithms for random graph generation.
Target Conferences and Journals: