基于概率与推断的社交网络聚类技术研究

本文将位置敏感哈希算法（LSH）应用于图聚类，提出了概率化的图聚类法（PGC）。利用LSH技术比较图中各结点邻居集的相似度，并结合贝叶斯统计推断进行验证，在线性时间内找到图中最紧密的、非精确聚类。测试结果表明，随着图尺寸的增大PGC扩展性更强，在现实世界数据集上PGC比PageRank Cluster 聚类速度快约1倍，是一种有效的解决方案。

Probability and interference based social network clustering technology

We apply Locality Sensitive Hashing (LSH) to graph clustering, and then present a new clustering technology, Probabilistic Graph Cluster (PGC). We also compare the similarity of the neighbor set of every node in a graph, and verify it with Bayesian statistic inference to find the most compact and inexact clustering in linear time. Experimental results show that PGC is more scalable with the enlargement of a graph and that the clustering speed of PGC is twice faster than that of PageRank Cluster in real data sets. PGC is therefore an effective and alternative solution.