0


局部高阶图聚类

Local Higher-Order Graph Clustering
课程网址: http://videolectures.net/kdd2017_yin_graph_clustering/  
主讲教师: Hao Yin
开课单位: 斯坦福大学
开课时间: 2017-10-09
课程语种: 英语
中文简介:
局部图聚类方法旨在通过探索图的小区域来找到节点簇。这些方法很有吸引力，因为它们能够围绕给定种子节点进行有针对性的聚类，并且比传统的全局图聚类方法更快，因为它们的运行时间不依赖于输入图的大小。然而，当前的局部图划分方法并非旨在考虑对网络至关重要的高阶结构，也不能有效地处理有向网络。在这里，我们介绍一类新的局部图聚类方法，该方法通过合并小子图（也称为网络基序）捕获的高阶网络信息来解决这些问题。第一的，我们展示了如何采用近似个性化 PageRank 算法来查找包含具有最小主题电导的种子节点的簇，这是网络主题电导度量的概括。我们还概括了现有的理论，以保持快速运行时间（与图的大小无关）和簇质量（就基序电导而言）的特性。对于合成网络和现实网络上的社区检测任务，我们的新框架优于当前基于边缘的个性化 PageRank 方法。其次，我们开发了一种节点邻域理论，用于查找具有小主题电导的集合，其中主题是一个团。我们将这些结果应用于寻找良好种子节点以用作个性化 PageRank 算法的输入的情况。我们还概括了现有的理论，以保持快速运行时间（与图的大小无关）和簇质量（就基序电导而言）的特性。对于合成网络和现实网络上的社区检测任务，我们的新框架优于当前基于边缘的个性化 PageRank 方法。其次，我们开发了一种节点邻域理论，用于查找具有小主题电导的集合，其中主题是一个团。我们将这些结果应用于寻找良好种子节点以用作个性化 PageRank 算法的输入的情况。我们还概括了现有的理论，以保持快速运行时间（与图的大小无关）和簇质量（就基序电导而言）的特性。对于合成网络和现实网络上的社区检测任务，我们的新框架优于当前基于边缘的个性化 PageRank 方法。其次，我们开发了一种节点邻域理论，用于查找具有小主题电导的集合，其中主题是一个团。我们将这些结果应用于寻找良好种子节点以用作个性化 PageRank 算法的输入的情况。我们的新框架优于当前基于边缘的个性化 PageRank 方法。其次，我们开发了一种节点邻域理论，用于查找具有小主题电导的集合，其中主题是一个团。我们将这些结果应用于寻找良好种子节点以用作个性化 PageRank 算法的输入的情况。我们的新框架优于当前基于边缘的个性化 PageRank 方法。其次，我们开发了一种节点邻域理论，用于查找具有小主题电导的集合，其中主题是一个团。我们将这些结果应用于寻找良好种子节点以用作个性化 PageRank 算法的输入的情况。
课程简介: Local graph clustering methods aim to find a cluster of nodes by exploring a small region of the graph. These methods are attractive because they enable targeted clustering around a given seed node and are faster than traditional global graph clustering methods because their runtime does not depend on the size of the input graph. However, current local graph partitioning methods are not designed to account for the higher-order structures crucial to the network, nor can they effectively handle directed networks. Here we introduce a new class of local graph clustering methods that address these issues by incorporating higher-order network information captured by small subgraphs, also called network motifs. First, we show how to adapt the approximate personalized PageRank algorithm to find clusters containing a seed node with minimal motif conductance, a generalization of the conductance metric for network motifs. We also generalize existing theory to maintain the properties of fast running time (independent of the size of the graph) and cluster quality (in terms of motif conductance). For community detection tasks on both synthetic and real-world networks, our new framework outperforms the current edge-based personalized PageRank methodology. Second, we develop a theory of node neighborhoods for finding sets that have small motif conductance, where the motif is a clique. We apply these results to the case of finding good seed nodes to use as input to the personalized PageRank algorithm.
关 键 词: 局部图聚; 社区检测任务; 数据科学
课程来源: 视频讲座网
数据采集: 2023-12-27：wujk
最后编审: 2023-12-27：wujk
阅读次数: 13

纠错/补充/评论/留言
评论/留言 纠错/补充
验证算术题： 1 + 6 =