Incremental building association link network

摘要

Association Link Network (ALN) is used to establish associated relations among various resources, aiming at extending the hyperlink network World Wide Web to an association-rich network. Unfortunately, given the scale of the Web, the challenge of incremental building ALN is on how to perform the association weight of the new coming Web resources efficiently and exactly. A naive way is to compare every pair of resources in the existing ALN, thus bearing a O(mn) time complexity with m new coming resources in a n mades ALN. In this paper, through the analysis of some candidate methods, two strategies are proposed. The first strategy converses the All-pairs algorithm from duplicate detection field, in which each resource is canonicalized by a global ordering to reduce the candidate size. The second strategy uses collaborative filtering technologies to achieve the incremental building ALN, in which the nodes of ALN with top degree are used to select candidate nodes to reduce the time complexity. Experiments and evaluations show that the second strategy performs a higher accuracy than the first strategy in the same candidate size. Moreover, the scale-independent property of the second strategy makes it to be used on the Web appropriately.