On Finding Socially Tenuous Groups for Online Social Networks

Chih-Ya Shen (National Tsing Hua University);Liang-Hao Huang (Academia Sinica);De-Nian Yang (Academia Sinica);Hong-Han Shuai (National Chiao Tung University);Wang-Chien Lee (The Pennsylvania State University);Ming-Syan Chen (National Taiwan University)

Abstract

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.