Identifying smallest unique subgraphs in a heterogeneous social network

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

研究成果: Conference contribution

1 引文 斯高帕斯(Scopus)

摘要

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.

原文English
主出版物標題Proceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015
編輯Feng 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
發行者Institute of Electrical and Electronics Engineers Inc.
頁面757-766
頁數10
ISBN(電子)9781479999255
DOIs
出版狀態Published - 2015 12月 22
事件3rd IEEE International Conference on Big Data, IEEE Big Data 2015 - Santa Clara, United States
持續時間: 2015 10月 292015 11月 1

出版系列

名字Proceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015

Other

Other3rd IEEE International Conference on Big Data, IEEE Big Data 2015
國家/地區United States
城市Santa Clara
期間15-10-2915-11-01

All Science Journal Classification (ASJC) codes

  • 電腦網路與通信
  • 電腦科學應用
  • 資訊系統
  • 軟體

指紋

深入研究「Identifying smallest unique subgraphs in a heterogeneous social network」主題。共同形成了獨特的指紋。

引用此