Publication Type

Journal Article

Version

acceptedVersion

Publication Date

1-2013

Abstract

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.

Keywords

Data Mining and Knowledge Discovery, Complex Networks

Discipline

Communication Technology and New Media | Databases and Information Systems | Numerical Analysis and Scientific Computing

Publication

Social Network Analysis and Mining

Volume

3

Issue

4

First Page

813

Last Page

828

ISSN

1869-5450

Identifier

10.1007/s13278-013-0095-y

Publisher

Springer

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1007/s13278-013-0095-y

Download

Share

COinS