Material Detail

This video was recorded at 27th International Conference on Machine Learning (ICML), Haifa 2010. Consider the task of clustering university web pages based on the graph of links between these pages. Can clusters of "functionally similar" pages be detected from just this link structure? Note that this is a clustering task in which one starts without any prior knowledge of any similarity or distance measure between the domain elements. All the information in the input comes as objective, observed, binary relations among the objects. These relations are not similarity links. For example, the cluster of professors pages have very internal links, whereas the cluster of service pages have lots of internal links. What we are looking for are clusters whose members share similar link patterns with respect to the other clusters. We propose a formal model for such clustering tasks. Our model is based on an objective function that measures the homogeneity of between-clusters links. I shall discuss the computational complexity of finding a clustering with minimal objective cost and describe some hardness results as well as efficient approximation algorithms. The talk is (partly) based on work with Sharon Wulff.

Disciplines:

• Science and Technology  / Computer Science  / Programming & Programming Languages