普适的结构相似度在大规模网络中的计算优化技术研究

发布时间：2016-07-14 05:14

  本文关键词：普适的结构相似度在大规模网络中的计算优化技术研究，，由笔耕文化传播整理发布。

《东华大学》 2012年

普适的结构相似度在大规模网络中的计算优化技术研究

俞唯仁  

【摘要】：对象间的相似度计算是当前数据挖掘领域的重要研究课题之一。近年来,在Google网页排名算法PageRank的推动下,基于网页链接分析的普适相似度模型研究热潮席卷全球,以SimRank SimFusion、Penetrating-Rank(以下简称P-Rank)为代表的新相似度模型相继问世,成为目前国内外共同关注的热点问题。随着Internet网络规模的日异膨胀与应用需求的不断提高,这些新出现的相似度模型理论已端倪渐显,但尚有一系列科学技术难题亟待解决,主要包括算法的时空复杂度优化、误差与稳定性分析、规模可扩性问题等。针对这类相似度模型的核心理论与算法优化问题进行研究,可为网页排名、协同过滤、搜索引擎优化、网络图聚类等提供坚实的理论和技术基础,具有重要的科研和应用价值。 本文针对三种基于链接的新相似度模型(即SimRank、SimFusion、P-Rank),旨在深入研究这些相似度计算的优化问题,其中包括：相似度解的精度控制、加快迭代的收敛速度、降低计算时间与内存空间的代价、实现并行计算与增量算法等。结合这三种模型递归定义的特点,本文重点对相似度高效计算的关键技术进行研究,通过矩阵优化等途径,在可控精度下提高相似度算法性能并降低其代价开销。此外,本文还对这些相似度模型进行改进,研究并实现了具有可控精度、高稳定性、低时空复杂度特点的结构相似度改进算法。主要研究成果如下 1)提出了SimRank相似度计算的优化方法。利用矩阵形式表示SimRank方程,设计出一种新的SimRank迭代范式,可以指数级加快SimRank解的收敛速度。通过建立低维的Krylov子空间,把原SimRank方程(n×n维)投影到这个低维子空间(r×r维)计算,从而使计算时间由原来的O(Knm)降为(?)(rm＋r2n＋Kr3),内存空间由O(n2)降为O(rn),其中n,m是图的总结点数和边数,r(《n)是邻接矩阵的秩,K是总迭代次数。为进一步降低SimRank时间复杂度,对无向图的SimRank进行优化,借助邻接矩阵的特征向量分解,将计算时间再降到(?)(rm+Kr2),同时实现无向图的SimRank并行算法。 2)改进了SimFusion模型并优化其相似度算法。针对原SimFusion模型中存在的两个问题——同构网络中的发散解、异构网络的平凡解.提出一种改进的SimFusion模型(下称SimFusion+),通过引入一致邻接矩阵(UAM)和“推迟行归一化”操作,确保SimFusion+方程解的存在唯一性。为解决SimFusion+计算的优化问题,利用UAM矩阵的主特征向量表示SimFusion+相似度,把计算时间从原先的p(Kn3)降为O(n2),内存空间由O(n2)降到O(n)。还探索了SimFusion+的近似算法与增量算法,分别适用于大型与动态网络图上的相似度计算,解决了SimFusion+算法的规模可扩性问题。 3)优化了P-Rank模型的计算。通过矩阵形式给出P-Rank相似度的两种表现形式——逆矩阵式、幂级数式。基于P-Rank逆矩阵式,利用转移矩阵的奇异值分解,提出一种新的P-Rank确定性算法,把计算时间由原来的O(Kn4)降为O(v4n2+v2n),同时给出误差估计,其中v(《n)是一个时间与精度权衡参数。基于P-Rank幂级数式,结合Monte Carlo法,提出一种规模可扩的P-Rank随机算法,把计算时间进一步降到O(Nn),其中N是样本大小。还通过定义P-Rank条件数并估计其上界,研究P-Rank相似度的稳定性。在无向图中,利用矩阵对角变换,提出一种P-Rank非迭代算法,把时间再降为O(vn2)。 在人工与实际数据集上的实验结果表明,基于链接结构的三种相似度模型经算法优化与模型改进后,具有时空复杂度低、稳定性强、规模可扩、精度可控等特点,其计算性能比原先的算法提高若干数量级,这些模型在大规模网络图上计算有显著的加速效果。尤其是提出的并行和增量相似度算法能有效降低代价开销,改善相似度在多处理器、动态网络图中的计算性能。相关研究成果为结构相似度的计算提供了较好的解决方案和理论分析基础,可肖接适用基于网页链接的搜索引擎算法设计与实现。

【关键词】：
【学位授予单位】：东华大学
【学位级别】：博士
【学位授予年份】：2012
【分类号】：TP311.13
【目录】：

下载全文 更多同类文献

CAJ全文下载

(如何获取全文？ 欢迎：购买知网充值卡、在线充值、在线咨询)

CAJViewer阅读器支持CAJ、PDF文件格式

【参考文献】

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

1 罗辛;欧阳元新;熊璋;袁满;;通过相似度支持度优化基于K近邻的协同过滤算法[J];计算机学报;2010年08期

2 张乃洲;李石君;余伟;张卓;;使用联合链接相似度评估爬取Web资源[J];计算机学报;2010年12期

3 黄承慧;印鉴;侯昉;;一种结合词项语义信息和TF-IDF方法的文本相似度量方法[J];计算机学报;2011年05期

4 林学民;王炜;;集合和字符串的相似度查询[J];计算机学报;2011年10期

5 王晓宇,周傲英;万维网的链接结构分析及其应用综述[J];软件学报;2003年10期

6 杨建武;陈晓鸥;;基于核矩阵学习的XML文档相似度量方法[J];软件学报;2006年05期

7 彭京;唐常杰;元昌安;李川;胡建军;;一种基于概念相似度的数据分类方法[J];软件学报;2007年02期

8 黄健斌;孙鹤立;Dustin BORTNER;刘亚光;;从链接密度遍历序列中挖掘网络社团的层次结构[J];软件学报;2011年05期

【共引文献】

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

1 蒋宗礼;李宪雷;徐学可;;基于主题Hub值的元搜索[J];北京工业大学学报;2009年03期

2 高明霞;姚文集;毛国君;;XML数据流中面向聚类的指数直方图[J];北京工业大学学报;2011年08期

3 叶琳莉;林嵩凯;;基于Web结构挖掘算法的网站构建[J];电脑知识与技术;2008年34期

4 王梅;;搜索引擎中的web链接算法研究与改进[J];电脑知识与技术;2009年24期

5 谭涛;;高效的动态脚本网页关联性挖掘算法研究[J];电脑知识与技术;2012年13期

6 李江;殷之明;;链接分析研究综述[J];大学图书馆学报;2008年02期

7 王艳辉,吴斌,王柏;电信社群网络静态几何性质分析研究[J];复杂系统与复杂性科学;2005年02期

8 段晓东;王存睿;刘向东;张庆灵;;基于网络权重的多社团网络结构划分算法[J];复杂系统与复杂性科学;2009年03期

9 谭丽华;董毅明;李林红;;互联网群体智能的涌现[J];管理学报;2010年12期

10 邱均平,张洋;网络信息计量学综述[J];高校图书馆工作;2005年01期

中国重要会议论文全文数据库 前5条

1 张冉;卡米力毛依丁;;基于论文参考文献引用分析的专业文献查询库[A];第十届全国少数民族语言文字信息处理学术研讨会论文集[C];2005年

2 杨宇航;赵铁军;郑德权;于浩;;基于链接分析的重要Blog信息源发现[A];内容计算的研究与应用前沿——第九届全国计算语言学学术会议论文集[C];2007年

3 王玉婷;杜亚军;涂腾涛;;基于Web链接的主题爬行虫初始URL的研究[A];第四届全国信息检索与内容安全学术会议论文集（上）[C];2008年

4 刘喜平;万常选;;一种二维的树型文档结构相似性度量[A];第二十五届中国数据库学术会议论文集（二）[C];2008年

5 张志强;梁婷婷;谢晓芹;;一种基于用户标记的搜索结果排序算法[A];第26届中国数据库学术会议论文集（B辑）[C];2009年

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

1 殷志伟;基于统计学习理论的分类方法研究[D];哈尔滨工程大学;2009年

2 黄莉;基于语义关联的重复数据清理技术研究[D];华中科技大学;2011年

3 杨抒;基于WEB的林产品信息资源整合方法研究[D];北京林业大学;2011年

4 龙军;基于信任感知与演化的服务组合关键技术研究[D];中南大学;2011年

5 邓小龙;基于复杂网络分析的新一代电信CRM关键技术研究[D];北京邮电大学;2011年

6 许笑;分布式Web信息采集关键技术研究[D];哈尔滨工业大学;2011年

7 寇月;Deep Web实体搜索的关键技术研究[D];东北大学;2009年

8 朱振方;基于微粒群和遗传优化的文本过滤关键技术研究[D];山东师范大学;2012年

9 刘娜;文本自动摘要和信息抽取方法及其应用研究[D];大连海事大学;2012年

10 乐小虬;非结构化网络空间信息智能搜索与服务研究[D];中国科学院研究生院（遥感应用研究所）;2006年

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

1 王芳;基于EVS相似度的邮件社区划分方法研究[D];郑州大学;2010年

2 张士军;基于随机游走的网页协同排序算法研究[D];大连理工大学;2010年

3 杨阳;复杂网络社团划分算法的研究与实现[D];西安电子科技大学;2010年

4 张韦;基于语义的Web主题提取的研究[D];湖北工业大学;2011年

5 李卓;基于编辑图的XML相似性研究[D];吉林大学;2011年

6 李彤宇;XML函数依赖研究[D];吉林大学;2011年

7 李莹;基于最大流与页面相似度值的Web结构挖掘研究[D];陕西师范大学;2011年

8 马燕;基于快速相似度的Web结构挖掘的研究[D];南京信息工程大学;2011年

9 马丽;融入语义相似度的HITS算法研究及实现[D];南京理工大学;2011年

10 董馨;基于增量更新的自适应协同过滤算法研究[D];中南大学;2011年

【二级参考文献】

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

1 王辉;左万利;王晖昱;宁爱军;孙志伟;满春雷;;基于质心向量的增量式主题爬行[J];计算机研究与发展;2009年02期

2 彭涛;孟宇;左万利;王英;胡亮;;主题爬行中的隧道穿越技术[J];计算机研究与发展;2010年04期

3 杨博;刘大有;金弟;马海宾;;复杂网络聚类方法[J];软件学报;2009年01期

4 彭京;唐常杰;曾涛;乔少杰;雍小嘉;;基于神经网络和属性距离矩阵的中药方剂功效归约算法[J];四川大学学报(工程科学版);2006年01期

【相似文献】

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

1 刘华文;;模糊模式识别的基础——相似度量[J];模式识别与人工智能;2004年02期

2 范平;;Vague集之间的相似度量分析[J];咸宁学院学报;2007年03期

3 权双燕;;信息意义下Vague集的相似度量[J];计算机工程与应用;2007年25期

4 石玉强;;Vague(值)集间的接近度及其在网络信息过滤中的应用[J];琼州学院学报;2007年05期

5 石玉强;;Vague(值)集间的相似度量及其应用[J];计算机工程与应用;2008年11期

6 石玉强;吴家培;;Vague(值)集的相似度量及其在模式识别中的应用[J];仲恺农业技术学院学报;2008年02期

7 刘明;;一个Vague集(值)间的相似度量公式[J];琼州学院学报;2008年05期

8 张晓晨;张福金;王鸿绪;;基于Vague值的扩展的Vague集间的相似度量[J];计算机应用与软件;2009年03期

9 王鸿绪;;两类高区分能力的Vague集之间的相似度量[J];计算机工程与应用;2009年22期

10 秦轩;;Vague集及其相似度量[J];魅力中国;2010年14期

中国重要会议论文全文数据库 前10条

1 张勇;金伟其;;基于结构相似度与感兴趣区域的图像融合评价方法[A];中国光学学会2010年光学大会论文集[C];2010年

2 汤韩玲;赖景生;;基于结构的西部农业发展问题探讨[A];长江上游经济发展与长江流域经济合作学术研讨会论文集[C];2005年

3 韩鹏;龚健雅;李志林;乌萌;;一种新的遥感影像空间尺度上推方法评价指标[A];中国测绘学会九届四次理事会暨2008年学术年会论文集[C];2008年

4 何昕;谢志鹏;;基于简单树匹配算法的Web页面结构相似性度量[A];第二十四届中国数据库学术会议论文集（研究报告篇）[C];2007年

5 苏毅娟;;一种新的Vague集相似度量方式[A];广西计算机学会2006年年会论文集[C];2006年

6 赵娜娜;王向文;刘顺兰;;基于中值滤波与边缘插值的视频去隔行算法[A];浙江省电子学会2011学术年会论文集[C];2011年

7 陈宁;陈安;周龙骧;;混合类型数据相似度及网格聚类算法[A];第十八届全国数据库学术会议论文集（研究报告篇）[C];2001年

8 俎小娜;金连文;;基于最优全局仿射变换的分级汉字字库的设计及实现[A];第二十六届中国控制会议论文集[C];2007年

9 刘喜平;万常选;;一种二维的树型文档结构相似性度量[A];第二十五届中国数据库学术会议论文集（二）[C];2008年

10 张东风;张金隆;刘玉青;;基于Vague集相似度量的多目标模糊决策[A];节能环保 和谐发展——2007中国科协年会论文集（一）[C];2007年

中国重要报纸全文数据库 前2条

1 本报记者 黄智军;[N];计算机世界;2010年

2 记者 洪宾;[N];深圳商报;2011年

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

1 俞唯仁;普适的结构相似度在大规模网络中的计算优化技术研究[D];东华大学;2012年

2 杜小坤;数据库模式匹配算法研究[D];华中科技大学;2010年

3 楼斌;基于NSS与HVS的图像质量评价方法研究[D];浙江大学;2009年

4 黎新;面向问答系统的段落检索技术研究[D];中国科学技术大学;2010年

5 张红;像素级多分辨率图像融合方法研究[D];吉林大学;2008年

6 宋玲;语义相似度计算及其应用研究[D];山东大学;2009年

7 窦亚玲;基于直觉模糊集的多约束网络路由决策方法研究[D];华中科技大学;2010年

8 李艳红;信息系统敏捷性及其相关技术的研究[D];大连理工大学;2002年

9 王晓艳;基于方向性多分辨率分析的遥感影像融合算法研究[D];兰州大学;2011年

10 袁庆霓;基于网络化制造环境的制造资源共享服务语义关键技术研究[D];西南交通大学;2010年

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

1 万芬;结构相似度图像质量评价算法的改进研究[D];大连海事大学;2011年

2 李红芳;基于梯度的结构相似度图像质量评价方法研究[D];西安科技大学;2012年

3 徐小琳;重视边缘的结构相似度图像/视频质量评价方法研究[D];华南理工大学;2012年

4 徐育利;基于结构相似度和Contourlet的数字水印算法研究[D];河南大学;2010年

5 汪凡;基于结构信息的图像质量评价方法研究[D];华南理工大学;2010年

6 陈勇;结构相似度及其在推荐系统中的应用研究[D];电子科技大学;2011年

7 梁敏瑜;基于结构相似度与MTF的图像质量评价方法研究[D];南京理工大学;2012年

8 王经谊;基于人类视觉特性的结构相似度图像质量评价[D];南京理工大学;2012年

9 刘显峰;基于结构相似度的图像融合质量评价[D];暨南大学;2007年

10 俎小娜;基于全局仿射变换的分级动态汉字字库[D];华南理工大学;2008年

  本文关键词：普适的结构相似度在大规模网络中的计算优化技术研究，由笔耕文化传播整理发布。

本文编号：70714