Identifying smallest unique subgraphs in a heterogeneous social network

Yen Kai Wang, Wei Ming Chen, Cheng-Te Li, Shou De Lin

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

Abstract

This paper proposes to study a novel problem, discovering a Smallest Unique Subgraph (SUS) for any node of interest specified by user in a heterogeneous social network. The rationale of the SUS problem lies in how a person is different from any others in a social network, and how to represent the identity of a person using her surrounding relational structure in a social network. To deal with the proposed SUS problem, we develop an Ego-Graph Heuristic (EGH) method to efficiently solve the SUS problem in an approximated manner. EGH intelligently examine whether one graph is not isomorphic to the other, instead of using the conventional subgraph isomorphism test. We also prove SUS is a NP-complete problem through doing a reduction from Minimum Vertex Cover (MVC) in a homogeneous tree structure. Experimental results conducted on a real-world movie heterogeneous social network data show both the promising efficiency and compactness of our method.

Original languageEnglish
Title of host publicationProceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015
EditorsFeng Luo, Kemafor Ogan, Mohammed J. Zaki, Laura Haas, Beng Chin Ooi, Vipin Kumar, Sudarsan Rachuri, Saumyadipta Pyne, Howard Ho, Xiaohua Hu, Shipeng Yu, Morris Hui-I Hsiao, Jian Li
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages757-766
Number of pages10
ISBN (Electronic)9781479999255
DOIs
Publication statusPublished - 2015 Dec 22
Event3rd IEEE International Conference on Big Data, IEEE Big Data 2015 - Santa Clara, United States
Duration: 2015 Oct 292015 Nov 1

Publication series

NameProceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015

Other

Other3rd IEEE International Conference on Big Data, IEEE Big Data 2015
CountryUnited States
CitySanta Clara
Period15-10-2915-11-01

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Computer Science Applications
  • Information Systems
  • Software

Fingerprint Dive into the research topics of 'Identifying smallest unique subgraphs in a heterogeneous social network'. Together they form a unique fingerprint.

Cite this