On Finding Socially Tenuous Groups for Online Social Networks
| Autor: | Hong-Han Shuai, Ming-Syan Chen, Chih-Ya Shen, Liang-Hao Huang, Wang-Chien Lee, De-Nian Yang |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Exploit
Group (mathematics) business.industry media_common.quotation_subject 0102 computer and information sciences 02 engineering and technology 01 natural sciences Measure (mathematics) Social group 010201 computation theory & mathematics 020204 information systems 0202 electrical engineering electronic engineering information engineering Quality (business) Artificial intelligence Tera business media_common Mathematics |
| Zdroj: | KDD |
| DOI: | 10.1145/3097983.3097995 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|