https://scholars.lib.ntu.edu.tw/handle/123456789/632388
標題: | On Extracting Socially Tenuous Groups for Online Social Networks With k-Triangles | 作者: | Shen C.-Y Shuai H.-H Yang D.-N Lee G.-S Huang L.-H Lee W.-C MING-SYAN CHEN |
關鍵字: | k-triangle; online social networks; Socially tenuous groups | 公開日期: | 2022 | 卷: | 34 | 期: | 7 | 起(迄)頁: | 3431-3446 | 來源出版物: | IEEE Transactions on Knowledge and Data Engineering | 摘要: | 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. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85131830469&doi=10.1109%2fTKDE.2020.3025911&partnerID=40&md5=b559c7cbdc24e3c52db3d3f2c54d2fac https://scholars.lib.ntu.edu.tw/handle/123456789/632388 |
ISSN: | 10414347 | DOI: | 10.1109/TKDE.2020.3025911 | SDG/關鍵字: | 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) |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。