|
对于网络社区检测算法的实证比较
Empirical Comparison of Algorithms for Network Community Detection |
|
| |
| 课程网址: |
http://videolectures.net/www2010_leskovec_eca/
|
| 主讲教师: |
Jure Leskovec
|
| 开课单位: |
斯坦福大学
|
| 开课时间: |
2010-05-17
|
| 课程语种: |
英语
|
| 中文简介: |
在大型真实世界图形 (如大型社交或信息网络) 中检测集群或社区是一个相当令人感兴趣的问题。实际上, 通常会选择一个客观函数来捕获网络集群的直觉, 将其捕获为具有比外部连接更好的内部连接的节点集, 然后应用近似算法或启发式方法提取节点是相关的目标函数和 "看起来像" 良好的社区应用的兴趣。本文探讨了一系列网络社区检测方法, 以便对其进行比较, 了解它们的相对性能及其识别的集群的系统性偏差。我们评估了几个用于形式化网络社区概念的常见目标函数, 并检查了几种不同类别的近似算法, 这些算法旨在优化这些目标函数。此外, 我们考虑的不是简单地固定一个目标并要求对任何大小的最佳集群进行近似, 而是一个大小解析版本的优化问题。将社区质量视为其大小的函数为研究社区检测算法提供了更精细的镜头, 因为目标函数和近似算法通常具有不明显的大小依赖行为。
|
| 课程简介: |
Detecting clusters or communities in large real-world graphs such as large social or information networks is a problem of considerable interest. In practice, one typically chooses an objective function that captures the intuition of a network cluster as set of nodes with better internal connectivity than external connectivity, and then one applies approximation algorithms or heuristics to extract sets of nodes that are related to the objective function and that “look like” good communities for the application of interest. In this paper, we explore a range of network community detection methods in order to compare them and to understand their relative performance and the systematic biases of clusters they identify. We evaluate several common objective functions that are used to formalize the notion of a network community, and examine several different classes of approximation algorithms that aim to optimize such objective functions. In addition, rather than simply fixing an objective and asking for an approximation to the best cluster of any size, we consider a size-resolved version of the optimization problem. Considering community quality as a function of its size provides a much finer lens with which to examine community detection algorithms, since objective functions and approximation algorithms often have non-obvious size-dependent behavior.
|
| 关 键 词: |
计算机科学; 网络分析; 社交网络
|
| 课程来源: |
视频讲座网
|
| 最后编审: |
2020-06-12：yumf
|
| 阅读次数: |
47
|
|
图 书 馆