On Perspective-Aware Top-k Similarity Search in Multi-relational Networks

It is fundamental to compute the most “

similar

”

k

nodes w.r.t. a given query node in networks; it serves as primitive operator for tasks such as social recommendation, link prediction, and web searching. Existing approaches to this problem do not consider types of relationships (edges) between two nodes. However, in real networks there exist different kinds of relationships. These kinds of network are called multi-relational networks, in which, different relationships can be modeled by different graphs. From different perspectives, the relationships of the objects are reflected by these different graphs. Since the link-based similarity measure is determined by the structure of the corresponding graph, similarity scores among nodes of the same network are different w.r.t. different perspectives. In this paper, we propose a new type of query,

perspective-aware top-k similarity query

, to provide more insightful results for users. We efficiently obtain all top-

k

similar nodes to a given node simultaneously from all perspectives of the network. To accelerate the query processing, several optimization strategies are proposed. Our solutions are validated by performing extensive experiments.