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

发布时间：2017-08-16 09:16

  本文关键词：一种基于Sketch的Top-k紧密中心性快速搜索算法

  更多相关文章： 紧密中心性 图算法 近似算法 图分析 社交网络

【摘要】：在大数据的时代背景下,由于网络数据(network data)能有效简洁地描述社交网络、电子商务、医疗记录、在线教育等多种应用中各类复杂关系,越来越受到工业界和学术界的关注.在社交网络分析任务中,一个基本操作是从网络中发现重要程度前k大的节点.紧密中心性(closeness centrality)是一种常见的节点重要性刻画指标,它用节点在网络中心的程度来反映节点的重要性.用紧密中心性衡量节点重要性进行节点搜索的问题称为top-k紧密中心性搜索问题.然而,传统的精确算法由于其多项式级别的复杂度无法高效地扩展到大规模的网络数据上.近来,研究人员提出了近似算法,通过牺牲结果精度来获得性能提升.通过分析发现,目前存在的近似算法虽然性能得到了有效提升,但是结果精度牺牲过大.为了解决这个问题,该文设计了一种新颖的近似算法,叫做基于Sketch的紧密中心性搜索算法.此近似算法应用了一个全新的计算方式,利用Sketch估计同一距离的邻居数目,然后得到近似的最短距离之和,最终得到各个节点的紧密中心性的估计值.此算法的时间复杂度为O(mt Dmax),其中t是常数,Dmax是网络直径,m是网络边数.根据实际社交网络的小世界现象的特性,此近似算法基本是个线性算法.最后,相比于目前存在的精确算法和近似算法,该文通过全面的实验验证了基于Sketch的紧密中心性搜索算法在时间性能和结果精度等两方面的优势.
【作者单位】： 北京大学信息科学技术学院高可信软件技术重点实验室;昆士兰大学信息技术和电子工程学院;
【关键词】： 紧密中心性 图算法 近似算法 图分析 社交网络
【基金】：国家自然科学基金(61272155,61572039) 国家“九七三”重点基础研究发展规划项目基金(2014CB340405) 深圳政府研究项目(JCYJ20151014093505032)资助~~
【分类号】：TP301.6
【正文快照】： 1引言 近年来,随着万维网、Web2.0、移动网络、社交媒体以及电子商务等技术的迅速发展,大规模的网络数据已经无处不在.截至2014年2月,Facebook拥有全球12亿用户,其中仅好友关系已多达2016亿条(1).同时,根据CNNIC的统计(2)表明,截至2013年12月,国内社交网站用户规模达2.78亿.

【相似文献】

中国期刊全文数据库 前3条

1 邵浩;陈东方;刘欣;;复杂网络算法中K-shell与介数中心性算法的实现[J];现代计算机(专业版);2014年17期

2 刘建明;张德政;阿孜古丽;刘洁卉;;基于中医网络的中心性算法研究[J];计算机仿真;2008年05期

3 ;[J];;年期

中国博士学位论文全文数据库 前1条

1 付立东;复杂网络中心性度量及社团检测算法研究[D];西安电子科技大学;2012年

中国硕士学位论文全文数据库 前3条

1 马梦瑶;基于证据理论的社会网络中心性结点识别方法研究[D];吉林大学;2016年

2 李明雪;基于社会网络的社区发现和中心性分析算法研究[D];吉林大学;2016年

3 武龙举;基于复杂网络的社区发现算法研究[D];吉林大学;2013年

，

本文编号：682461