Abstract:Ranking is a fundamental task in information retrieval, data mining, and social network analysis. With the rapid proliferation of online social network and social media, a great deal of graph data has been accumulated. Graph data is made up of nodes, representing entities, and edges, characterizing relationships among entities. In graph data, nodes are connected through heterogeneous relationships, lacking explicit order among them. Therefore, graph ranking is particularly important for graph data analysis. Existing graph ranking algorithms could be roughly classified into two categories, respectively graph ranking based on centrality of nodes and graph ranking on diversity of a set of nodes. For centrality-based graph ranking, spectral analysis is main-stream technique, where nodes are ranked according to their magnitude in primary eigenvectors of certain matrix, like adjacency matrix, Google matrix, and modularity matrix. These methods are particularly useful at offering a global ranking of nodes. However, a global ranking is not sufficient in many scenarios, such as personalized recommendation, influence maximization, and ranking of search results. Hence, researchers begin to study the diversified ranking on graphs. Different from traditional ranking on graph, diversified graph ranking focuses on the interplay of ranking and clustering, capturing the intrinsic structure regularity of graph. In recent years, diversified ranking on graph attracts great attention, and several methods are proposed and successfully applied in many scenarios, including search results ranking, information recommendation system, document summarization, and influence maximization. In this paper, we summarize main research progress about diversified ranking on graph. We roughly classified existing methods into three categories, respectively based on marginal-benefit maximization, random walk with node competition, and reinforcement between clustering and ranking. For marginal-benefit maximization, a benefit function is generally defined for optimization. With such a benefit function, nodes are selected one by one according to their marginal benefit. Each time, the node with the maximum marginal benefit is selected. In this way, nodes are ranked in the decreasing order of marginal benefit. The performance of this kind of methods depends on the benefit function. The other kind of methods are based on random walk. Traditional random walk is essentially a kind of centrality-based method. To guarantee the diversity of ranking, researchers try to introduce competition among adjacent nodes into traditional random walk. Two typical examples are DivRank and Grasshopper. DivRank revises the transition probability among nodes to implement a rich-get-richer mechanism, forcing adjacent nodes to compete for scores and consequently form a diversified ranking. Grasshopper adopts a multi-step manner, selecting one node at each iteration and taking the selected nodes as sink point to penalize its adjacent nodes in following iterations. The third kind of diversified graph ranking exploits the reinforcement between ranking and clustering. Cluster-dependent ranking and ranking-based clustering are iteratively updated to form a diversified ranking. Finally, we introduce some potential research trends for diversified graph ranking. We point out the community lacks a commonly-available and widely-accepted benchmark for diversified ranking on graphs. A benchmark is particularly valuable for filtering out state-of-the-art methods. Meanwhile, we also need to design good evaluation metrics for diversified graph ranking. With the rapid increase of the scale of graph data, to offer an off-the-shelf method, scalability is another key issue for future research.