Graph Labeling

In applied algorithms, occasionally you strike gold --- formulation of a nice abstract problem: some of the times, people manage to solve it and it becomes a mini-industry (ex: packet classification in IP networks), other times, the problems haunt you.

About 10 years ago, I (and am sure many others before and since) struck a problem: Given a graph G=(V,E) with a subset of nodes labeled from label set L, determine a suitable labeling for the remaining nodes.

The nodes may be say telephone numbers, the edges the calls between them, the labels say the monthly bill on some of the customers, and the question is, what can you infer about the monthly bill of the others. As technology has evolved, the problem continues to matter. The nodes may be IP addresses, webpages, blog nodes, and others; the labels may be the age of the blogger, how spammy a page, etc.

10 years ago was the time of HITS and PageRank and I thought of simple iterative algorithms. Since then, the problem has been studied using techniques of machine learning (ex), stochastic relational labeling (ex), partitioning on random graph models (ex), decoding (ex), etc. No matter the approach, the problem is still fluttering, with lots to do.