Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/113790
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Journal article |
Title: | Dissimilarity-constrained node attribute coverage diversification for novelty-enhanced top-k search in large attributed networks |
Author: | Meng, Z. Shen, H. |
Citation: | Knowledge-Based Systems, 2018; 150:85-94 |
Publisher: | Elsevier BV |
Issue Date: | 2018 |
ISSN: | 0950-7051 1872-7409 |
Statement of Responsibility: | Zaiqiao Meng , Hong Shen |
Abstract: | Query diversification as an effective way to reduce query ambiguity and enhance result novelty has received much attention in top-k search applications on large networks. A major drawback of the existing diversification models is that they do not consider redundancy elimination during the course of search, resulting in unassured novelty in the search result. In this paper, to improve the novelty of the search result, we propose a new method of diversified top-k similarity search by combining diversification of node attribute coverage with a dissimilarity constraint. Due to the non-monotonicity implied by the dissimilarity constraint, existing techniques based on monotonicity assumptions cannot be applied. Our model requires solving a new problem of Dissimilarity Constrained Non-monotone Submodular Maximization (DCNSM). Based on constructing a dissimilarity-based graph, we solve this problem by a greedy algorithm achieving an approximation ratio of 1/Δ where Δ is the maximum node degree of the dissimilarity-based graph, in time linear to the number of edges of the graph. We show that DCNSM cannot be approximated in ratio |V|1−ϵ, indicating that our solution achieves an optimal ratio. We conduct extensive experiments on both synthetic and real-world attributed network datasets. The results show that our diversification model significantly outperforms the baseline methods, and confirm that combining dissimilarity constraint in diversification can significantly improve the novelty of search result. |
Keywords: | Information retrieval; query diversification; top-k search; submodular maximization |
Description: | Available online 17 March 2018 |
Rights: | © 2018 Elsevier B.V. All rights reserved. |
DOI: | 10.1016/j.knosys.2018.03.008 |
Grant ID: | http://purl.org/au-research/grants/arc/DP150104871 |
Published version: | http://dx.doi.org/10.1016/j.knosys.2018.03.008 |
Appears in Collections: | Aurora harvest 8 Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.