|
基于社区的贪婪算法在移动社交网络中挖掘影响最大的K节点
Community-based Greedy Algorithm for Mining Top-K Influential Nodes in Mobile Social Networks |
|
| |
| 课程网址: |
http://videolectures.net/kdd2010_wang_cga/
|
| 主讲教师: |
Yu Wang
|
| 开课单位: |
北京大学
|
| 开课时间: |
2010-10-01
|
| 课程语种: |
英语
|
| 中文简介: |
随着移动设备和无线技术的普及，移动社交网络系统越来越多。移动社交网络作为信息和影响以“口口相传”的形式传播起着至关重要的作用。在移动社交网络中找到有影响力的个体的子集是一个基本问题，使得最初针对它们（例如，采用新产品）将最大化影响的扩散（新产品的进一步采用）。遗憾的是，NP难以找到最有影响力的节点。已经证明，具有可证明的近似保证的Greedy算法可以给出良好的近似;然而，在大型移动网络上运行贪婪算法在计算上是昂贵的，如果不是禁止的话。在本文中，我们提出了一种新的算法，称为基于社区的贪婪算法，用于挖掘前K个有影响的节点。所提出的算法包括两个部分：1）通过考虑信息扩散来检测社交网络中的社区的算法; 2）用于选择社区以找到有影响的节点的动态编程算法。我们还为我们的算法提供可证明的近似保证。对大型现实世界移动社交网络的实证研究表明，我们的算法比现有技术Greedy算法更快的数量级，用于寻找前K个有影响的节点，并且我们的近似算法的误差很小。
|
| 课程简介: |
With the proliferation of mobile devices and wireless technologies, mobile social network systems are increasingly available. A mobile social network plays an essential role as the spread of information and influence in the form of "word-of-mouth". It is a fundamental issue to find a subset of influential individuals in a mobile social network such that targeting them initially (e.g. to adopt a new product) will maximize the spread of the influence (further adoptions of the new product). The problem of finding the most influential nodes is unfortunately NP-hard. It has been shown that a Greedy algorithm with provable approximation guarantees can give good approximation; However, it is computationally expensive, if not prohibitive, to run the greedy algorithm on a large mobile network. In this paper we propose a new algorithm called Community-based Greedy algorithm for mining top-K influential nodes. The proposed algorithm encompasses two components: 1) an algorithm for detecting communities in a social network by taking into account information diffusion; and 2) a dynamic programming algorithm for selecting communities to find influential nodes. We also provide provable approximation guarantees for our algorithm. Empirical studies on a large real-world mobile social network show that our algorithm is more than an order of magnitudes faster than the state-of-the-art Greedy algorithm for finding top-K influential nodes and the error of our approximate algorithm is small.
|
| 关 键 词: |
移动设备; 社交网络系统; 贪婪算法
|
| 课程来源: |
视频讲座网
|
| 最后编审: |
2019-05-11：cwx
|
| 阅读次数: |
74
|
|
图 书 馆