|
社区搜索问题以及如何策划一个成功的鸡尾酒会
The community-search problem and how to plan a successful cocktail party |
|
| |
| 课程网址: |
http://videolectures.net/kdd2010_sozio_csp/
|
| 主讲教师: |
Mauro Sozio
|
| 开课单位: |
马克斯普朗克研究所
|
| 开课时间: |
2010-10-01
|
| 课程语种: |
英语
|
| 中文简介: |
图形挖掘的许多研究都致力于社区的发现。大部分工作都集中在只需要参考输入图就可以发现社区的场景中。然而，对于许多有趣的应用程序来说，我们有兴趣找到由一组给定节点组成的社区。本文研究了社区检测问题的一个查询相关变量，我们称之为社区搜索问题：给定一个图G和图中的一组查询节点，我们寻求找到一个包含查询节点且连接紧密的图G的子图。基于最小度和距离约束，提出了一种密度度量方法，并给出了该方法的最优贪婪算法。通过对一类单调约束的刻画，推广了求解满足任意单调约束的最优解的算法。最后，我们修改了贪婪算法，并给出了两个启发式算法，发现大小不超过指定上限的社区。我们对真实数据集的实验评估证明了所提出的算法的效率和我们获得的解决方案的质量。
|
| 课程简介: |
A lot of research in graph mining has been devoted in the discovery of communities. Most of the work has focused in the scenario where communities need to be discovered with only reference to the input graph. However, for many interesting applications one is interested in finding the community formed by a given set of nodes. In this paper we study a query-dependent variant of the community-detection problem, which we call the community-search problem: given a graph G, and a set of query nodes in the graph, we seek to find a subgraph of G that contains the query nodes and it is densely connected. We motivate a measure of density based on minimum degree and distance constraints, and we develop an optimum greedy algorithm for this measure. We proceed by characterizing a class of monotone constraints and we generalize our algorithm to compute optimum solutions satisfying any set of monotone constraints. Finally we modify the greedy algorithm and we present two heuristic algorithms that find communities of size no greater than a specified upper bound. Our experimental evaluation on real datasets demonstrates the efficiency of the proposed algorithms and the quality of the solutions we obtain.
|
| 关 键 词: |
应用程序; 社区检测问题; 贪婪算法; 启发式算法
|
| 课程来源: |
视频讲座网
|
| 最后编审: |
2019-12-21：lxf
|
| 阅读次数: |
120
|
|
图 书 馆