On Extracting Socially Tenuous Groups for Online Social Networks With k-Triangles
Journal
IEEE Transactions on Knowledge and Data Engineering
Journal Volume
34
Journal Issue
7
Pages
3431-3446
Date Issued
2022
Author(s)
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 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. © 1989-2012 IEEE.
Subjects
k-triangle; online social networks; Socially tenuous groups
SDGs
Other Subjects
Approximation algorithms; Polynomial approximation; Trees (mathematics); Corporates; Dense sub-graphs; K-triangle; NP-hard; Optimal solutions; Polynomial-time; Research problems; Social groups; Socially tenuous group; Tree-based; Social networking (online)
Type
journal article