图 书 馆
在社交网络中寻找效应器Finding Effectors in Social Networks |
|
| 课程网址: | http://videolectures.net/kdd2010_terzi_fes/ |
| 主讲教师: | Evimaria Terzi |
| 开课单位: | 波士顿大学 |
| 开课时间: | 2010-10-01 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | Assume a network (V,E) where a subset of the nodes in V are active. We consider the problem of selecting a set of k active nodes that best explain the observed activation state, under a given information-propagation model. We call these nodes effectors. We formally define the k-Effectors problem and study its complexity for different types of graphs. We show that for arbitrary graphs the problem is not only NP-hard to solve optimally, but also NP-hard to approximate. We also show that, for some special cases, the problem can be solved optimally in polynomial time using a dynamic- programming algorithm. To the best of our knowledge, this is the first work to consider the k-Effectors problem in networks. We experimentally evaluate our algorithms using the DBLP co-authorship graph, where we search for effectors of topics that appear in research papers. |
| 关 键 词: | 信息传播; 激活状态; 效应器 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2019-05-11：cwx |
| 阅读次数: | 62 |