一种基于 Sketch 的 Top-k 紧密中心性快速搜索算法

• 作者: 崔斌 邵蓥侠 阴红志 马林
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 紧密中心性 图算法 近似算法 图分析 社交网络
• 年，卷（期）: 2016,（10）
• 所属期刊栏目: 数据科学与工程
• 页码范围: 1965-1978
• 页数: 14页
• 分类号: TP311
• 字数: 12617字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2016.01965

摘要

在大数据的时代背景下，由于网络数据（network data）能有效简洁地描述社交网络、电子商务、医疗记录、在线教育等多种应用中各类复杂关系，越来越受到工业界和学术界的关注。在社交网络分析任务中，一个基本操作是从网络中发现重要程度前 k 大的节点。紧密中心性（closeness centrality）是一种常见的节点重要性刻画指标，它用节点在网络中心的程度来反映节点的重要性。用紧密中心性衡量节点重要性进行节点搜索的问题称为 top-k 紧密中心性搜索问题。然而，传统的精确算法由于其多项式级别的复杂度无法高效地扩展到大规模的网络数据上。近来，研究人员提出了近似算法，通过牺牲结果精度来获得性能提升。通过分析发现，目前存在的近似算法虽然性能得到了有效提升，但是结果精度牺牲过大。为了解决这个问题，该文设计了一种新颖的近似算法，叫做基于 Sketch的紧密中心性搜索算法。此近似算法应用了一个全新的计算方式，利用 Sketch 估计同一距离的邻居数目，然后得到近似的最短距离之和，最终得到各个节点的紧密中心性的估计值。此算法的时间复杂度为 O（m tD max ），其中 t 是常数，D max 是网络直径，m 是网络边数。根据实际社交网络的小世界现象的特性，此近似算法基本是个线性算法。最后，相比于目前存在的精确算法和近似算法，该文通过全面的实验验证了基于 Sketch 的紧密中心性搜索算法在时间性能和结果精度等两方面的优势。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	崔斌	北京大学信息科学技术学院高可信软件技术重点实验室	53	357	10.0	17.0
2	马林	北京大学信息科学技术学院高可信软件技术重点实验室	2	9	2.0	2.0
3	邵蓥侠	北京大学信息科学技术学院高可信软件技术重点实验室	3	5	1.0	2.0
4	阴红志	昆士兰大学信息技术和电子工程学院	1	4	1.0	1.0