《边预测毕业论文》由会员分享，可在线阅读，更多相关《边预测毕业论文（62页珍藏版）》请在金锄头文库上搜索。
1、目录摘要iiiABSTRACTiv第一章综述1第一节边预测的用途1第二节基于相似性的边预测方法2一、局部信息下的相似性分析2二、路径基础上的相似性分析2三、随机游走中的相似性分析3第三节Cytoscape简介4第四节论文结构5第二章Cytoscape插件开发简介6第一节Cytoscape的软件结构6第二节Cytoscape二次开发7一、Cytoscape编程控制8二、Cytoscape插件开发9第三章预测算法及其实现17第一节预测算法实现17第二节Cytoscape边预测功能实现18第三节Cytoscape预测功能展示19第四节算法评价20第四章边预测实验22第一节真实网络导入22第二节预测插
2、件应用及结果23第三节预测结果分析26总结28参考文献30附录32附录A32附录B55摘要在大数据时代，网络建模成为数据处理的一项重要手段。而边预测作为处理网络的有效方式也逐渐受到更多的关注。边预测是指在网络中，通过已知的网络信息，例如节点，边或网络结构等，来对网络中存在性不明的边进行预测6。边预测既能解决生物网络中实验方向不明朗的问题，又能在数据缺失或难以集全的情况下较为精确地对研究社会网络进行研究分析。同时还能纠正网络中错误连边，完成网络结构重组。而Cytoscape作为一项重要的网络处理软件，既能对网络进行可视化处理，又能对网络进行集成分析，已在各种复杂网络分析处理和可视化领域应用中占据
3、十分重要的地位。但是，边预测作为网络处理的强大手段，目前Cytoscape仍然缺乏通用的预测插件，因此，本文以Cytoscape为软件平台，基于共同邻居的边预测算法，实现了符合OSGi标准的Cytoscape插件，总结了Cytoscape第三方开发接口和插件开发流程，为开发通用的Cytoscape边预测插件包提供了参考。关键词：边预测；Cytoscape；插件；相似性第5页ABSTRACTIn the era of big data, network modeling becomes one of these important methods. And edge prediction dra
4、ws more attention as a valid way of handling network. Edge prediction means to predict whether an unknown edge exits or not in the network with information in the network like node, edge or structure. Edge prediction can help to solve the problem that biological experiments do not have a clear direc
5、tion when explore the inner patterns, analyze the social network accurately without complete data, correct the wrong link in the network and rebuild it. And Cytoscape is a software of network handling, which can visualize the network as well as carry out integrated analysis for it. Therefore it play
6、s an important role in the complicated network analysis and visual application field. However, Cytoscape has various functions, but it cannot do the job like edge prediction. Nowadays, edge prediction can be realized through programmed algorithm, its visual result is not so good though, and theres n
7、o universal app with the function of prediction in Cytoscape. Therefore, in this article, we finished an Cyto-app which fits the standard of OSGi with the algorithm based on common neighbors where Cytoscape was taken as the software platform. Besides, we conclude the process of how to take use of Cy
8、toscape developing port and create a Cyto-app which provides reference to develop a universal Edge-Prediction jar package.KEY WORDS: edge prediction, Cytoscape, plug-in, Similarity analysis第一章综述第一节边预测的用途边预测是指在网络中，通过已知的网络信息，例如节点，边或者是网络结构等，来对网络中存在性不明的边进行预测。该预测包含两层概念，一是评估未知边存在的可能性，另一个则是预测已知尚未存在的边将来产生链接
9、的可能性。因此，边预测问题成了各个领域不同科学家视线的聚焦点。首先，边预测在实际应用领域具有十分重大的价值。例如，生物研究领域的各种生物分子交互网络、代谢网络中，需要通过大量的实验，并依赖其结果才能对网络进行内在规律揭示和分析。而网络内的内部相互作用归根到底就是节点之间的连接关系。 然而，巨大的生物网络在实验中显露出来的仅仅是网络中相当小的一部分。仅以蛋白质网络为例研究其交互作用，就人类本身我们认识到的竟只有0.3%。即使是简单生物酵母菌的蛋白质相互作用，仍有80%不被人类所掌握。如果在此类实验中，仅仅依靠庞大的实验数量进行枚举式的研究，那么，揭示其网络中边的存在性需要的将是无比巨大的实验成本
10、与资源。但是，能在已知的网络中找到合理精确的边预测算法，以此进行边预测，并利用预测结果引导实验方向，将有可能极大的在减少实验数量的同时提高实验的成功率，这不仅能很大程度上节省实验消耗，还能大大地加快研究进程。其次，社会网络研究分析过程中会出现数据缺失或难以集全的问题，此时，边预测又将展现它在保证精确性前提下辅助分析网络结构的强大能力。除此之外，边预测还能帮助分析并演化网络。举个简单例子，在当下迅速发展并深受民众喜爱的社交在线网络中，边预测可以基于用户已有的好友网络分析出整个网络中未成为该用户好友单应该彼此相识的使用者，并将此结果推荐给该用户，以此演化社交在线网络。此外，边预测仍有其他诸多作用，
11、它方法和理论同样可被节点类型预测所借鉴，它可以用以验证已存在边的准确性，并以此清除错误链接，并完成网络的结构优化和重组。例如在一些实验中，不同的数据可能引导出矛盾的结果，边预测为我们清除不恰当数据提供快捷准确的途径。第二节基于相似性的边预测方法一、局部信息下的相似性分析局部信息下的相似性分析，是指运用只需要通过部分节点信息便可运算得到的相似性指标进行边预测分析。这类指标的优势在于复杂程度低，可运用于规模过大的应用网络。但因其依赖的信息量有限，预测精度相对于一些全局性的指标而言显得不够高。最简单常用的方法是基于共同邻居的边预测分析。共同邻居一般称为CN，全称Common neighbor ，是局
12、部信息下最简单的相似性参数。CN相似性在某种程度上又被称为结构等价，即，若两个节点具有较多的共同邻居，则这两个节点相似。由此可见，CN关注的更多地是两个节点存在的环境是否相同。在边预测的应用CN有其必要的前提假设，即若两个节点的共同邻居越多，它们之间存在连边的可能性越大。CN指标的定义如下：对于网络的节点，定义其邻居集合为集合，则两个节点和的相似性就定义为它们的共同邻居数1，即 （1.2.1）在CN指标的基础上，考虑共同邻居的度的影响便有了AA指标（Adami-Adar指标）。它的主要思想是度不同的共同邻居对节点的影响不同，度高的共同邻居会比度小的造成更大的影响。因此，基于共同邻居度的大小，A
13、A赋予每个节点一个权重，该权重大小是该节点度取对数后求倒数。另一个与AA指标近似的指标是RA指标，即资源分配指数10，灵感来源于网络资源分配过程。在网络中，没有边存在的节点间的资源交互需要以共同邻居作为媒介，我们假设每个节点拥有一个单位的资源并平均分给它的邻居，则可定义两个节点的相似性为两个节点共同邻居数量的倒数。二、路径基础上的相似性分析局部信息下的相似性分析计算复杂程度低，但由于依赖信息有限，导致相似性分数分布太集中，使节点之间的差异性不明显，造成预测精度稍低。因此，在局部共同邻居之后，又出现了依赖于局部路径的相似性分析。周涛等经过研究，在考虑共同邻居的同时，又引入三阶路径因素，提出局部路
14、径指标并定义为 （1.2.2）其中，为可调节的参数，A为邻接矩阵。S的值越大，边存在的可能性越大1。此外，还有另一个指标Katz指标，它将所有的路径及其长度纳入考虑了范围。同时，在该指标假设了路径越短对边存在性的影响越大。同时，Katz指标对于不同长度的路径分别赋予不同的权重，当然，长度越短，权重越高9。它定义如下： （1.2.3）其中是可调节的参数，|表示的则是两节点间长度为L的路径数量，当其收敛时，该定义简化为（I为单位矩阵） （1.2.4）另一个路径基础上的相似性指标是LHN-，该指标的基本思想是在一般等价的基础上提出的。一般等价是指，若两节点具有相似的邻居节点，则这两个节点相似。与结构
15、等价不同，这并不要求两个节点拥有共同邻居。它的最终定义式 （1.2.5）其中M代表网络的总边数，是邻接矩阵A最大的特征值，D代表度矩阵，I为单位矩阵，为可调节的参数17。三、随机游走中的相似性分析假设在网络中有一个对象在节点间随机地、没有规律地移动，那么在移动过程中，会产生一些例如节点间距离的数据，基于这些数据，产生了对应的相似性指标。ACT指数，是基于平均通信时间的相似性指标，它的值由对象在两个节点间的游走平均步数决定，假设对象从节点x随机游走到节点y的平均所需步数为m(x,y)，则节点x，y之间的平均通信时间为m(x,y)与m(y,x)的和11。当平均通信时间越小时，两个节点之间的相似程度越高。因此，ACT指数被定义为 （1.2.6）Cos+指标，即余弦相似度指标，它基于马氏距离来进行向量相似性的分析。马氏距离常用于描述两个向量之间的差异度，且当其中的协方差矩阵恰好是一个单位矩阵是，就相当于是欧式距离。而节点可用向量将其在欧式几何空间中表达。因此，令节点x在欧式几何空间中的坐标向量为，可以将余弦相似性定义18为 （1.2.7）此外，基于全局范围的随机游走中的相似性指标还有
