Context-based people search in labeled social networks

Cheng-Te Li, Man Kwan Shan, Shou De Lin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Citations (Scopus)

Abstract

In online social networking services, there are a range of scenarios in which users want to search a particular person given the targeted person one's name. The challenge of such people search is namesake, which means that there are many people possess the same names in the social network. In this paper, we propose to leverage the query contexts to tackle such problems. For example, given the information of one's graduation year and city, the last names of some individuals, one may wish to find classmates from his/her high school. We formulate such problem as the context-based people search. Given a social network in which each node is associated with a set of labels and given a query set of labels consisting of a targeted name label and other context labels, our goal is to return a ranking list of persons who possess the targeted name label and connects to other context labels with minimum communication costs through an effective subgraph in the social network. We consider the interactions among query labels to propose a grouping-based method to solve the context-based people search. Our method consists of three major parts. First, we model those nodes with query labels into a group graph which is able to reduce the search space to enhance the time efficiency. Second, we identify three different kinds of connectors which connecting different groups, and exploit connectors to find the corresponding detailed graph topology from the group graph. Third, we propose a Connector-Steiner Tree algorithm to retrieve a resulting ranked list of individuals who possess the targeted label. Experimental results on the DBLP bibliography data show that our grouping-based method can reach the good quality of returned persons as a greedy search algorithm at a considerable outperformance on the time efficiency.

Original languageEnglish
Title of host publicationCIKM'11 - Proceedings of the 2011 ACM International Conference on Information and Knowledge Management
Pages1607-1612
Number of pages6
DOIs
Publication statusPublished - 2011 Dec 13
Event20th ACM Conference on Information and Knowledge Management, CIKM'11 - Glasgow, United Kingdom
Duration: 2011 Oct 242011 Oct 28

Publication series

NameInternational Conference on Information and Knowledge Management, Proceedings

Other

Other20th ACM Conference on Information and Knowledge Management, CIKM'11
CountryUnited Kingdom
CityGlasgow
Period11-10-2411-10-28

Fingerprint

Social networks
Query
Graph
Grouping
Node
Topology
Scenarios
Graduation
Leverage
Social networking
Communication cost
Ranking
High school
Interaction

All Science Journal Classification (ASJC) codes

  • Decision Sciences(all)
  • Business, Management and Accounting(all)

Cite this

Li, C-T., Shan, M. K., & Lin, S. D. (2011). Context-based people search in labeled social networks. In CIKM'11 - Proceedings of the 2011 ACM International Conference on Information and Knowledge Management (pp. 1607-1612). (International Conference on Information and Knowledge Management, Proceedings). https://doi.org/10.1145/2063576.2063809
Li, Cheng-Te ; Shan, Man Kwan ; Lin, Shou De. / Context-based people search in labeled social networks. CIKM'11 - Proceedings of the 2011 ACM International Conference on Information and Knowledge Management. 2011. pp. 1607-1612 (International Conference on Information and Knowledge Management, Proceedings).
@inproceedings{7d5c1f6cc69248589c77d642153d51e8,
title = "Context-based people search in labeled social networks",
abstract = "In online social networking services, there are a range of scenarios in which users want to search a particular person given the targeted person one's name. The challenge of such people search is namesake, which means that there are many people possess the same names in the social network. In this paper, we propose to leverage the query contexts to tackle such problems. For example, given the information of one's graduation year and city, the last names of some individuals, one may wish to find classmates from his/her high school. We formulate such problem as the context-based people search. Given a social network in which each node is associated with a set of labels and given a query set of labels consisting of a targeted name label and other context labels, our goal is to return a ranking list of persons who possess the targeted name label and connects to other context labels with minimum communication costs through an effective subgraph in the social network. We consider the interactions among query labels to propose a grouping-based method to solve the context-based people search. Our method consists of three major parts. First, we model those nodes with query labels into a group graph which is able to reduce the search space to enhance the time efficiency. Second, we identify three different kinds of connectors which connecting different groups, and exploit connectors to find the corresponding detailed graph topology from the group graph. Third, we propose a Connector-Steiner Tree algorithm to retrieve a resulting ranked list of individuals who possess the targeted label. Experimental results on the DBLP bibliography data show that our grouping-based method can reach the good quality of returned persons as a greedy search algorithm at a considerable outperformance on the time efficiency.",
author = "Cheng-Te Li and Shan, {Man Kwan} and Lin, {Shou De}",
year = "2011",
month = "12",
day = "13",
doi = "10.1145/2063576.2063809",
language = "English",
isbn = "9781450307178",
series = "International Conference on Information and Knowledge Management, Proceedings",
pages = "1607--1612",
booktitle = "CIKM'11 - Proceedings of the 2011 ACM International Conference on Information and Knowledge Management",

}

Li, C-T, Shan, MK & Lin, SD 2011, Context-based people search in labeled social networks. in CIKM'11 - Proceedings of the 2011 ACM International Conference on Information and Knowledge Management. International Conference on Information and Knowledge Management, Proceedings, pp. 1607-1612, 20th ACM Conference on Information and Knowledge Management, CIKM'11, Glasgow, United Kingdom, 11-10-24. https://doi.org/10.1145/2063576.2063809

Context-based people search in labeled social networks. / Li, Cheng-Te; Shan, Man Kwan; Lin, Shou De.

CIKM'11 - Proceedings of the 2011 ACM International Conference on Information and Knowledge Management. 2011. p. 1607-1612 (International Conference on Information and Knowledge Management, Proceedings).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Context-based people search in labeled social networks

AU - Li, Cheng-Te

AU - Shan, Man Kwan

AU - Lin, Shou De

PY - 2011/12/13

Y1 - 2011/12/13

N2 - In online social networking services, there are a range of scenarios in which users want to search a particular person given the targeted person one's name. The challenge of such people search is namesake, which means that there are many people possess the same names in the social network. In this paper, we propose to leverage the query contexts to tackle such problems. For example, given the information of one's graduation year and city, the last names of some individuals, one may wish to find classmates from his/her high school. We formulate such problem as the context-based people search. Given a social network in which each node is associated with a set of labels and given a query set of labels consisting of a targeted name label and other context labels, our goal is to return a ranking list of persons who possess the targeted name label and connects to other context labels with minimum communication costs through an effective subgraph in the social network. We consider the interactions among query labels to propose a grouping-based method to solve the context-based people search. Our method consists of three major parts. First, we model those nodes with query labels into a group graph which is able to reduce the search space to enhance the time efficiency. Second, we identify three different kinds of connectors which connecting different groups, and exploit connectors to find the corresponding detailed graph topology from the group graph. Third, we propose a Connector-Steiner Tree algorithm to retrieve a resulting ranked list of individuals who possess the targeted label. Experimental results on the DBLP bibliography data show that our grouping-based method can reach the good quality of returned persons as a greedy search algorithm at a considerable outperformance on the time efficiency.

AB - In online social networking services, there are a range of scenarios in which users want to search a particular person given the targeted person one's name. The challenge of such people search is namesake, which means that there are many people possess the same names in the social network. In this paper, we propose to leverage the query contexts to tackle such problems. For example, given the information of one's graduation year and city, the last names of some individuals, one may wish to find classmates from his/her high school. We formulate such problem as the context-based people search. Given a social network in which each node is associated with a set of labels and given a query set of labels consisting of a targeted name label and other context labels, our goal is to return a ranking list of persons who possess the targeted name label and connects to other context labels with minimum communication costs through an effective subgraph in the social network. We consider the interactions among query labels to propose a grouping-based method to solve the context-based people search. Our method consists of three major parts. First, we model those nodes with query labels into a group graph which is able to reduce the search space to enhance the time efficiency. Second, we identify three different kinds of connectors which connecting different groups, and exploit connectors to find the corresponding detailed graph topology from the group graph. Third, we propose a Connector-Steiner Tree algorithm to retrieve a resulting ranked list of individuals who possess the targeted label. Experimental results on the DBLP bibliography data show that our grouping-based method can reach the good quality of returned persons as a greedy search algorithm at a considerable outperformance on the time efficiency.

UR - http://www.scopus.com/inward/record.url?scp=83055161623&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=83055161623&partnerID=8YFLogxK

U2 - 10.1145/2063576.2063809

DO - 10.1145/2063576.2063809

M3 - Conference contribution

SN - 9781450307178

T3 - International Conference on Information and Knowledge Management, Proceedings

SP - 1607

EP - 1612

BT - CIKM'11 - Proceedings of the 2011 ACM International Conference on Information and Knowledge Management

ER -

Li C-T, Shan MK, Lin SD. Context-based people search in labeled social networks. In CIKM'11 - Proceedings of the 2011 ACM International Conference on Information and Knowledge Management. 2011. p. 1607-1612. (International Conference on Information and Knowledge Management, Proceedings). https://doi.org/10.1145/2063576.2063809