@inproceedings{12bd1b35d35f495285901e39fa1581d7,
title = "Identifying smallest unique subgraphs in a heterogeneous social network",
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.",
author = "Wang, {Yen Kai} and Chen, {Wei Ming} and Li, {Cheng Te} and Lin, {Shou De}",
note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; 3rd IEEE International Conference on Big Data, IEEE Big Data 2015 ; Conference date: 29-10-2015 Through 01-11-2015",
year = "2015",
month = dec,
day = "22",
doi = "10.1109/BigData.2015.7363820",
language = "English",
series = "Proceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "757--766",
editor = "Feng Luo and Kemafor Ogan and Zaki, {Mohammed J.} and Laura Haas and Ooi, {Beng Chin} and Vipin Kumar and Sudarsan Rachuri and Saumyadipta Pyne and Howard Ho and Xiaohua Hu and Shipeng Yu and Hsiao, {Morris Hui-I} and Jian Li",
booktitle = "Proceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015",
address = "United States",
}