標題: On Finding Socially Tenuous Groups for Online Social Networks
作者: Shen, Chih-Ya
Huang, Liang-Hao
Yang, De-Nian
Shuai, Hong-Han
Lee, Wang-Chien
Chen, Ming-Syan
電機工程學系
Department of Electrical and Computer Engineering
公開日期: 1-Jan-2017
摘要: Existing research on finding social groups mostly focuses on dense subgraphs in social networks. However, finding socially tenuous groups also has many important applications. In this paper, we introduce the notion of k-triangles to measure the tenuity of a group. We then formulate a new research problem, Minimum k-Triangle Disconnected Group (MkTG), to find a socially tenuous group from online social networks. We prove that MkTG is NP-Hard and inapproximable within any ratio in arbitrary graphs but polynomial-time tractable in threshold graphs. Two algorithms, namely TERA and TERA-ADV, are designed to exploit graph theoretical approaches for solving MkTG on general graphs effectively and efficiently. Experimental results on seven real datasets manifest that the proposed algorithms outperform existing approaches in both efficiency and solution quality.
URI: http://dx.doi.org/10.1145/3097983.3097995
http://hdl.handle.net/11536/150985
DOI: 10.1145/3097983.3097995
期刊: KDD'17: PROCEEDINGS OF THE 23RD ACM SIGKDD INTERNATIONAL CONFERENCE ON KNOWLEDGE DISCOVERY AND DATA MINING
起始頁: 415
結束頁: 424
Appears in Collections:Conferences Paper