Query-oriented Graph Clustering
There are many tasks focusing on the relationship between data as well as the relevance to the query. For instance, one can use the similarity between data in the ranking list to diversify the recommendation results. In addition, one can also categorize the friend list of a user to discover his/her social circles. These applications are actually related to query-oriented clustering. In this paper, we firstly formulate the problem, query-oriented clustering, in a general form and propose the two measures, query-oriented normalized cut (QNCut) and cluster balance to evaluate the results for query-oriented clustering. We develop a model, query-oriented graph clustering (QGC), that combines QNCut and the balance constraint based on cluster balance in a quadratic form. In the experiments, we show that QGC achieves promising results on improvement in diversified ranking and social circle discovery.