On Extracting Socially Tenuous Groups for Online Social Networks With k-Triangles

Chih Ya Shen, Hong Han Shuai, De Nian Yang, Guang Siang Lee, Liang Hao Huang, Wang Chien Lee, Ming Syan Chen

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


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 article, 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 with No-Pair Constraint (MkTG), to find a socially tenuous group from the online social network. We prove that MkTG is NP-hard and inapproximable within any ratio. Two algorithms, namely TERA and TERA-ADV, are designed for solving MkTG effectively and efficiently. Further, we examine the MkTG problem on tree-based social networks, due to their structural resemblance with corporate social networks built upon the supervision relation. Accordingly, we devise an efficient algorithm, namely Tenuity Maximization for Trees (TMT), to obtain the optimal solution in polynomial time. In addition, we study a more general version of MkTG, named Generalized Minimum k-Triangle Disconnected Group without No-Pair Constraint (MkTG-G). We formulate MkTG-G, analyze its inapproximability, and propose a randomized approximation algorithm, named Randomized Ranking with Limited Neighborhood Participation (RLNP). Experimental results on real datasets manifest that the proposed algorithms outperform the baselines in terms of both efficiency and solution quality.

Original languageEnglish (US)
Pages (from-to)3431-3446
Number of pages16
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number7
StatePublished - Jul 1 2022

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'On Extracting Socially Tenuous Groups for Online Social Networks With k-Triangles'. Together they form a unique fingerprint.

Cite this