高效估计热核 PageRank 用于局部聚类

Apr, 2019

高效估计热核 PageRank 用于局部聚类

Efficient Estimation of Heat Kernel PageRank for Local Clustering

Renchi Yang, Xiaokui Xiao, Zhewei Wei, Sourav S Bhowmick, Jun Zhao...

TL;DR论文提出了基于热核 PageRank 的两个新的本地图聚类算法 TEA 和 TEA+，利用确定性图遍历和蒙特卡洛随机游走的优化，解决了在大规模图上计算热核 PageRank 的效率低下的问题，并在真实世界的数据集上进行大量实验，表明 TEA + 在大多数基准数据集上的计算时间是同等聚类质量时现有算法的 4 倍以上。

Abstract

Given an undirected graph G and a seed node s, the local clustering problem aims to identify a high-quality cluster containing s in time roughly proportional to the size of the cluster, regardless of the size of G. This problem finds numerous applications on large-scale graphs. Recentl

local clustering heat kernel pagerank graph traversal monte-carlo random walks tea+

发现论文，激发创造

基于热核的社区发现

本研究提出了一种确定性的本地计算热核扩散的算法，用于研究其产生的社区，并与 PageRank 扩散进行比较，实验结果表明，热核社区具有更好的导度和识别性能。

Mar, 2014

基于 PageRank 的超图聚类

本文提出了两种基于个性化 PageRank 的超图聚类算法，它们都具有输出顶点集合对导纳有理论保证的优点，并在解决方案质量和运行时间方面优于现有方法。这是第一篇在具备理论保证的情况下实现了超图聚类的实用算法。

Jun, 2020

大规模图上完全个性化 PageRank 的分布式算法

本文提出了使用分布式计算框架计算大型边加权图的全面边加权个性化 PageRank 的新方法，使用了蒙特卡罗近似并结合优化技术，其准确性表现显着超过基线算法，并且速度比现有技术快数个数量级。

Mar, 2019

有种子节点的 PageRank 算法的本地化

本研究通过研究种子 PageRank 以及它在不同网络拓扑结构下的行为，得出了在含有类似于现实社交网络中节点度数分布的图中，能够仅仅用数量较少的元素来近似种子 PageRank 向量的结论。同时，本研究在实际网络和合成网络上的试验给出了进一步的证据，并探讨了度数序列对于种子 PageRank 的影响。

Aug, 2015

区块模型与个性化 PageRank

该研究旨在通过发现 PageRank 参数与种子集扩展问题之间的联系，提出了一种评估排名方法的原则框架，并提出了一种简单的线性分类规则用于更高阶的落点概率的种子扩展问题。

Jul, 2016

快速增量和个性化 PageRank

本文分析了 Monte Carlo 方法在动态社交网络中增量计算 PageRank、个性化 PageRank 和类似的基于随机行走方法（重点关注 SALSA）时的效率，针对全局 PageRank 做出了重大改进，同时也可以同样高效地处理删除，并研究了顶部 k 个个性化 PageRank 的计算。

Jun, 2010

可扩展核聚类：近似核 k-means

本文提出了一种基于随机化的近似核 K-means 簇算法，其利用采样点与数据集中所有点之间的核相似性来近似聚类中心，实现了与传统低秩核近似聚类方案相比更好的聚类性能、更短的运行时间和更小的内存需求，最后利用集成聚类技术进一步提高算法性能。

Feb, 2014

个性化 PageRank 的高效算法

本文介绍了一种新的双向算法来估计随机游走得分，其中结合了更高效的 Monte Carlo 和线性代数方法，使速度提高了 70 倍以上，可以用于社交网络、用户 - 项目网络和网页等网络上的个性化搜索和推荐。此外，文章还提出了其他相关算法，可用于无向图、任意步长和马尔可夫链、个性化搜索排名和从给定源到给定目标集的随机路径抽样。

Dec, 2015

动态图上的近似个性化 PageRank

本文提出并研究了两种算法，用于在动态图上维护近似频繁访问节点的 PPR 向量。其中，两种变体 Forward Push 和 Reverse Push 算法，能通过图的加边和删除边的动态维护算法在保证相似性的情况下进行向前和向后推送，减少计算代价。

Mar, 2016

将热核进行草图化：使用高斯过程嵌入数据

引入一种新的非确定性方法，将数据嵌入低维欧几里德空间，该方法基于依赖于数据几何的高斯过程的实现，通过计算高斯过程的实现来计算嵌入，其中高斯过程的协方差函数被取为热核函数，嵌入的直线距离以概率意义上逼近扩散距离，避免了对距离进行尖锐截断并保留了一定的较小尺度结构，此方法还具有对异常值的鲁棒性，并通过理论和实验证明了该方法的优势。

Mar, 2024