图 书 馆
动态社团识别的常数因子近似算法Constant-Factor Approximation Algorithms for Identifying Dynamic Communities |
|
| 课程网址: | http://videolectures.net/kdd09_tantipathananandh_cfaaidc/ |
| 主讲教师: | Chayant Tantipathananandh |
| 开课单位: | 伊利诺大学 |
| 开课时间: | 2009-09-14 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | We propose two approximation algorithms for identifying communities in dynamic social networks. Communities are intuitively characterized as unusually densely knit subsets of a social network. This notion becomes more problematic if the social interactions change over time. Aggregating social networks over time can radically misrepresent the existing and changing community structure. Recently, we have proposed an optimization-based framework for modeling dynamic community structure. Also, we have proposed an algorithm for finding such structure based on maximum weight bipartite matching. In this paper, we analyze its performance guarantee for a special case where all actors can be observed at all times. In such instances, we show that the algorithm is a small constant factor approximation of the optimum. We use a similar idea to design an approximation algorithm for the general case where some individuals are possibly unobserved at times, and to show that the approximation factor increases twofold but remains a constant regardless of the input size. This is the first algorithm for inferring communities in dynamic networks with a provable approximation guarantee. We demonstrate the general algorithm on real data sets. The results confirm the efficiency and effectiveness of the algorithm in identifying dynamic communities. |
| 关 键 词: | 计算机科学; 数据挖掘; 图挖掘 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2020-07-16：yumf |
| 阅读次数: | 127 |