图 书 馆
为在线社交网络寻找社会弱势群体On Finding Socially Tenuous Groups for Online Social Networks |
|
| 课程网址: | http://videolectures.net/kdd2017_shen_online_social_networks/ |
| 主讲教师: | Chih-Ya Shen |
| 开课单位: | 视频讲座网 |
| 开课时间: | 2017-10-09 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | 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. |
| 关 键 词: | 社会群体; 社交网络; 密集子图 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2023-03-06：chenxin01 |
| 最后编审: | 2023-04-20：liyy |
| 阅读次数: | 26 |