Hypergraph index: an index for context-aware nearest neighbor query on social networks

Social network has been touted as the No. 2 innovation in a recent IEEE Spectrum Special Report on “Top 11 Technologies of the Decade”, and it has cemented its status as a bona fide Internet phenomenon. With more and more people starting using social networks to share ideas, activities, events, and interests with other members within the network, social networks contain a huge amount of content. However, it might not be easy to navigate social networks to find specific information. In this paper, we define a new type of queries, namely context-aware nearest neighbor (CANN) search over social network to retrieve the nearest node to the query node that matches the textual context specified. The textual context of a node is defined as a set of keywords that describe the important aspects of the nodes. CANN considers both the network structure and the textual context of the nodes, and it has a very broad application base. Two existing searching strategies can be applied to support CANN search. The first one performs the search based on the network distance, and the other one conducts the search based on the node context information. Each of these methods operates according to only one factor but ignores the other one. They can be very inefficient for large social networks, where one factor alone normally has a very limited pruning power. In this paper, we design a hypergraph based method to support efficient approximated CANN search via considering the network structure and nodes’ textual contexts simultaneously. Experimental results show that the hypergraph-based method provides approximated results efficiently with low preprocessing and storage costs, and is scalable to large social networks. The approximation quality of our method is demonstrated based on both theoretical proofs and experimental results.