《边预测.doc》由会员分享，可在线阅读，更多相关《边预测.doc（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，即0 （1.2.1）在CN指标的基础上，考虑共同邻居的度的影响便有了AA指标（Adami-Adar指标）。它的主要思想是度不同的共同邻居对节点的影响不同，度高的共同邻居会比度小的造成更大的影响。因此，基于共同邻居度的大小，
13、AA赋予每个节点一个权重，该权重大小是该节点度取对数后求倒数。另一个与AA指标近似的指标是RA指标，即资源分配指数10，灵感来源于网络资源分配过程。在网络中，没有边存在的节点间的资源交互需要以共同邻居作为媒介，我们假设每个节点拥有一个单位的资源并平均分给它的邻居，则可定义两个节点的相似性为两个节点共同邻居数量的倒数。二、路径基础上的相似性分析局部信息下的相似性分析计算复杂程度低，但由于依赖信息有限，导致相似性分数分布太集中，使节点之间的差异性不明显，造成预测精度稍低。因此，在局部共同邻居之后，又出现了依赖于局部路径的相似性分析。周涛等经过研究，在考虑共同邻居的同时，又引入三阶路径因素，提出局部
14、路径指标并定义为 （1.2.2）其中，为可调节的参数，A为邻接矩阵。S的值越大，边存在的可能性越大1。此外，还有另一个指标Katz指标，它将所有的路径及其长度纳入考虑了范围。同时，在该指标假设了路径越短对边存在性的影响越大。同时，Katz指标对于不同长度的路径分别赋予不同的权重，当然，长度越短，权重越高8。它定义如下： （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。当平均通信时间越小时，两个节点之间的相似程
16、度越高。因此，ACT指数被定义为 （1.2.6）Cos+指标，即余弦相似度指标，它基于马氏距离来进行向量相似性的分析。马氏距离常用于描述两个向量之间的差异度，且当其中的协方差矩阵恰好是一个单位矩阵是，就相当于是欧式距离。而节点可用向量将其在欧式几何空间中表达。因此，令节点x在欧式几何空间中的坐标向量为，可以将余弦相似性定义18为 （1.2.7）此外，基于全局范围的随机游走中的相似性指标还有RWR指标及SimRank指标等。RWR指标基于假设对象在每次随机游走的过程中，都有一定返回起点的概率。它将从节点x到达节点y的概率与从节点y游走到x的概率和作为相似性程度指标。SimRank指标则考虑两个分
17、别以节点x、节点y为起点的两个对象在相遇前走过的距离。第三节Cytoscape简介Cytoscape是一个开源的软件平台，它可以将分子的交互作用网络和生物路径进行可视化处理，并运用注释、基因表达配置文件以及其他形态的数据对网络进行集成分析。虽然Cytoscape最初是为了生物科学研究而设计产生，但是，当下，Cytoscape的应用领域已不局限与生物范围，它在各种复杂网络分析处理和可视化领域应用中占据十分重要的地位。Cytoscape的核心提供了一些基本的操作来对数据进行交互、分析和可视化。除此之外，其他一些Cytoscape本身不具备的操作可以通过插件的方式导入其中。插件可以被应用于网络分析、
18、分子分布分析、新布局设计、新支持类型添加、脚本处理以及数据库连接。同时，Cytoscape的使用者可以通过基于Java技术的开源CYtoscape用户界面发展Cytoscape的诸多功能，而Cytoscape的插件开发社区正在进一步壮大。目前，Cytoscape已存在可实现各类功能的插件，而这些插件在Cytoscape插件商城都有收录。Cytoscape 3 具有模块化架构，是目前较为主流的Cytoscape版本。考虑其长期可维护性，它已基本取代了Cytoscape2.x系列版本。该版本添加了包括新用户接口、新式可视化函数、随意的命令行分布以及多样化的翻译引擎等新功能。直到2014年11月，C
19、ytoscape社区还在紧张的从2.x版本向3.x版本进化，而插件开发人员正努力使2.x版本的Cytoscape插件能适应3.x及以后版本。第四节论文结构本文主要阐述了Cytoscape插件开发方法以及边预测方法及算法实现。并以OSGi为框架，利用Eclipse完成插件编程并最终导入Cytoscape，完成图形化的关联关系预测。本文主要有五章。第一章是综述，主要边预测的用途以及对Cytoscape的基本情况进行简介，简要描述研究的方向。并综述边预测方法，介绍了当前边预测领域所常用而且较为简单的边预测的方法，主要描述在边预测过程中所利用的指标，及采用相应指标所基于的假设。第二章着眼于Cytosc
20、ape的软件结构，分析其中各个模块的作用及内部的编程控制，描述各类Cytoscape操作所基于的代码基础。同时介绍了两种Cytoscape插件实现的方法，并按步骤完成了简单的隐藏插件。第三章重点讲解了如何利用边预测的相似性指标完成边预测算法，并以第二章完成的简单插件为基础框架，实现Cytoscape的边预测功能插件。并利用AUC指标对算法进行评价。第四章是插件应用实验，通过引入真实网络，对其隐藏的必要边进行预测，通过将预测结果与现实结果相对比，分析算法的利弊。第五章对全文进行总结第二章Cytoscape插件开发简介第一节Cytoscape的软件结构Cytoscape 3.0致力于模块化结构建设
21、。该结构中，应用程序由一系列的jar文件组成，每个jar文件包含完整定义的程序的函数子集。该面向对象的设计基于OSGi服务器模型，将应用程序编程接口及其实现分别打包进不同的jar文件。而其目的是提供一系列定义了公共Cytoscape程序设计的接口。每个应用程序编程接口的jar文件都会包含对应的完全由私人的代码构成的执行jar文件。执行jar文件中会提供接口jar文件中定义的服务器接口。该方法能实现给定编程接口中不同执行jar文件的快速替换。同时，它还清晰地对公共的代码和私人的代码进行分类从而让开发者知道哪些代码能被改变而哪些不能。Cytoscape核心组件包含了多种多样的模块，每个模块中都封装
22、了关键的函数。当前，这些模块主要有数据模型、视图模型、任务执行、映射、事件处理、输入输出、布局、应用结构、描述、会话、网络服务、应用程序、实用模块。每个提到的模块都包含独立的编程接口及实现的jar文件Cytoscape主要支持网络和表两种数据类型，在数据模型模块中，其中网最基本的接口是CyNetwork，可以此对网及边和节点进行必要的操作。视图模块中的核心接口是VisualProperty，它为Cytoscape控制了了对视图变量的操作，例如节点颜色、隐藏节点等。Cytoscape 3 的核心模块是任务执行模块，任务接口主要的两个函数时run()和Cancel()，用以确定一项操作的执行与否。
23、输入输出模块控制着Cytoscape与环境的交互，可确定数据的输入输出、及数据类型等。布局模块抽象出了一些一般化的网络布局操作，它能分析一个网络并以网络布局的放肆提供结果。应用结构模块主要由两部分组成，一部分用以保证任何可行的OSGi bundle都能被用作插件，另一部分则是简单的插件程序接口，用以满足非OSGi规范的插件。描述模块的编程接口非常简化，只具有三个初级的接口分别用以允许翻译引擎的创建、翻译引擎支持格式的描述以及翻译引擎使用记录的管理。会话模块包含了对对话框进行操作的所有必要的接口，可实现对话框的关闭、对话框中内容存储、导入等一系列功能。网络服务模块主要管理Cytoscape联网操
24、作，并为服务器、客户端等的创建使用操作提供支持。应用程序模块主要包含了所有应用程序一般性的接口，用以控制例如菜单栏、按钮、面板等。应用结构模块则主要由两部分组成，一部分用以保证任何可行的OSGi bundle都能被用作插件，另一部分则是简单的插件程序接口，用以满足非OSGi规范的插件。而当下的Cytoscape 3.0只是打包了必要的jar文件，并在OSGi容器中运行。OSGi英文全称Open Service Gateway Initiative，它是OSGi联盟发起的基于java平台的模块化规范。OSGi起初着眼于嵌入式程序开发，为各类应用提供环境中的模块化服务。由于OSGi的热插拔特性，它
25、逐渐在java开发中发挥越来越重要的作用。当前，OSGi规范已对java模块化建设的各种控制（例如开发、更新等）进行了定义，其中还囊括了一些基本模型和格式化接口。OSGi规范包含了众多的子规范，一部分主要运用于OSGi框架的规范化描述，还有一部分则构成了以OSGi为基础，在应用程序开发的编程中建立标准接口的规范化服务。OSGi可以实现无需重启的条件下，应用程序中各个模块的动态变化（如安装、功能变化等），并能允许同一模块的不同版本在容器中的运行兼容。OSGi框架在OSGi中占据核心地位，它的基本模块化单元bundle。Bundle与插件相似，是一个jar文件，包含了一个插件所需要的所有资源。简化
26、来说，OSGi给各种容器和应用程序提供了一个通用的可兼容的java架构。在这个架构中，插件能被直接模块化部署和实现，而实现了得插件可直接被目标应用程序所接纳。第二节Cytoscape二次开发为Cytoscape编写插件，将其导入Cytoscape使其实现新的功能就是 Cytoscape的二次开发。为实现Cytoscape的二次开发，我们首先必须了解Cytoscape内部的函数控制和运行机制，并掌握插件的开发及导入方式。一、Cytoscape编程控制在2.1节中，我们介绍了Cytoscape的软件架构，其主要由多个不同的模块组成，而要编写Cytoscape的插件，必须对主要模块的编程控制有一定的
27、了解。Cytoscape是由具有不同功能的模块集成而来，而不同的模块都被打包成特定的jar包。当编写插件对Cytoscape进行控制时，必须在CyActivator类中通过申明，取得相应服务器的权限。对于swing应用，Cytoscape内由CytoPanelomponent服务器实现对其界面（主要是面板的各类操作，例如添加一个自定义面板等）的控制，由CyAction接口控制菜单项。同时，Cytoscape在CyNetworkManager和CyNetworkFactory两个服务器的支持下，可以完成对网络的例如创建删除等各项操作，并通过CyNetwork、CyActivator、CyTabl
28、eUtil、CyRow等接口实现对网络内部的具体控制（例如添加新的节点等）。类似的，CyNetworkViewFactory和CyNetworkViewManager是Cytoscape中网络视图控制的中心服务器，具体的操作都被打包在 CyNetworkView类中。在任务执行、映射、事件处理、输入输出、布局、应用结构、描述、会话、网络服务、应用程序、实用模块等模块同样的具有其相应的服务器，以及包含了该模块各项操作的类，具体内容见附录A（Cytoscape的内部编程控制）。在此，仅以创建子菜单为例，示范简单的Cytoscape编程控制：应用开发者需要先定义一个实现了CyAction 或是拓展了
29、AbstractCAction的类，然后把它申明为一个OSGi服务器。Cytoscape内部的CyAction管理器会拾起这个新申明的服务器，并按照定义创建一个菜单项，并说明其根菜单项。程序如下，第一步申明类：同时，在CyActivator类中，将其命名为“Edge prediction”并注册为服务器：二、Cytoscape插件开发（一） 一般化的App插件实现Cytoscape 是一个用网络实现数据的一体化、可视化及数据分析的一项开源软件工具，下面我要介绍的内容主要包括：1.为Cytoscape写一个简单的功能性应用2.应用的jar文件的生成3.将最终的应用配置到Cytoscape中我们将
30、通过实现一个完整的功能性应用来解释怎样为Cytoscape创建一个简单应用（套装应用）。这个功能性应用会在Select菜单栏下添加一个点击之后可以当前网络视图中隐藏所有度数为0的节点的菜单项。开始前，你首先需要安装Cytoscape（3.x版本及以上）及1.6版本以上的Java Development Kit (JDK)。除此之外，你还需要下载Cytoscape Swing App API JAR（这是对Cytoscape 3.1 有效地），注意保存的路径，稍后我们将会用到该路径。下载安装Cytoscape和Swing App API JAR之后，为你要写的简单应用的源代码创建一个目录。接下来
31、，我们先创建代码框架，这个框架对所有的简单应用来说都是一样的，代码如下：（注意：载这个简单的Java类中，我们不把代码进行打包，所以我们的类都会在一个简单的目录中）把这代码保存为HideSingletonNodesApp.java文件。接下来，我们为Ctoscape菜单项添加框架，框架代码如下：我们把这段代码保存为MenuAction.java在应用主类的代码框架中，我们加入如下几行代码：得到最终的代码如下:我们在菜单动作类中加入隐藏孤立点的代码，代码写在actionPerformed() 方法中。同时，我们还加入了import 代码来申明我们所需要的APIs。具体代码如下： 打开命令行界面，
32、进入源代码所在的文件夹，我们用以下代码编译两个类：javac cp “.;/路径/cytoscape-swing-app-api-3.2.0.jar” *.java其中，路径就是cytoscaoe-swing-app-api-3.2.0.jar所在的位置，运行后，会在源代码所在文件夹生成两个可以被打包成Jar文件的class文件。一个简单的应用是一个有meta-inf的jar文件。它确定了类在AbstractCyApp的入口和路径以及应用的主类。为了将其导入jar文件中，我们创建一个包含以下内容的app-manifest文件：最后，我们通过在命令提示符中先进入类所在目录，然后通过命令：建立应用
33、的jar文件。最终完成的jar文件就是可以运行的应用，我们可以在Cytoscape中对其进行测试。首先打开Cytoscape，选中Apps菜单下的App Manager。在弹出来的对话框中选中从文件中安装按钮，选中事先完成的jar文件（HideSingletonNodesApp.jar）。我们可以画或导入一个有游离点的网络，然后点击Apps菜单下的Hide unconnected nodes选项观察网络中的游离点是否被隐藏。（二）集成开发环境下的App插件实现利用OSGi框架可以极大的简化App插件的实现过程，我们将完成创建OSGi Bundle类型的Cytoscape 3的插件应用。创建一个
34、本地的Cytoscape 3插件应用，我们本来需要理解OSGi的基础，但是现在又很多工具可以自动化实现这个进程。在Cytoscape 3中，core和apps没有明显区别，所有的程序又是OSGi bundle。我们需要的工具有JDK 6或7、Maven3.x和Eclipse。在Eclipse中用maven原型创建App我们能用Cytoscape Maven原型来创建OSGi Bundle应用。这样，我们可以快速建立一个可以快速扩充成满足你需要的基于maven的工程，它会自动生成基于OSGi中bundle的Cytoscape App。具体建立过程如下：选中file选项，在子菜单中选中New下的O
35、ther。在弹出的选项中，选择Maven下的Maven Project 并点击next后继续点击next。首先，导入Cytoscape 原型目录（如果已经有可跳过下面步骤）。点击configure在弹出的对话框中选择Add Remote Catalog会弹出如下对话框图3.2.2.1在catalog file中粘贴上如下网址：在Description中输入你自定的名称，这里我们用Cytoscape Release。点OK后再选中Apply。在弹出的对话框中，Catalog项选中Catalog Release，并取消勾选第一项，会出现如下界面，选择cyaction-app 3.0.0，点击nex
36、t。图3.2.2.2在接下来的对话框中填入必要信息，我们填写Group Id和Artifact Id如下，Package会自动生成。图3.2.2.3点击finish后需要等待10至20秒时间，然后eclipse会创建一个工程包含你在上一步指定包的maven工程，工程目录如下所示：图3.2.2.4右键点击pom.xml，选择Run As菜单下的Maven install。Eclipse会在工程目录的target文件夹中生成目标jar文件。运行生成的应用首先，我们需要找到生成的jar文件，并将其复制到如下目录中：C:UsersAdministratorCytoscapeConfiguration3
37、appsinstalled，然后运行Cytoscape，注意，我们通过执行cytoscape.bat文件来进行而不是用cytoscape.exe。 在命令行中，输入list，它会显示当前OSGi工作环境中正在运行的bundle，我们能找到我们之前完成的目标应用。在打开的Cytoscape中，我们能在Apps菜单下发现生成的“Hello World App”菜单项。具体应用转化在这个例子中，我们将添加与第一节相同的应用，即隐藏网络视图中的所有孤立点。首先，我们先双击打开pom.xml，打开下方的dependencies，选择Add按钮，在跳出的对话框中，对应输入如下内容：Group Id ：or
38、g.cytoscapeArtifact Id ：presentation-apiversion3.0.0我们双击打开MenuAction类，将其代码变得与第一节所诉的MenuAction类的最终版本一致，这里不赘述代码。最后，编辑CyActivator类，将“Hello World App”替换为“Hide unconnected nodes”即可。同样右键单击pom.xml，选中Run As下的maven install生成目标jar文件，并重复“运行生成应用”的过程。我们能在Cytoscape的Apps菜单想发现“Hide unconnected nodes”选项，在任意倒入或画一个有孤立
39、节点的网络后，点击该选项，则所有的孤立点被隐藏。第三章预测算法及其实现上一章中对边预测所常用的相似度指标进行了介绍，本章将以共同邻居指标为基础，实现完整的预测算法，并将之应用于Cytoscape插件，从而在Cytoscape中实现可视化的边预测功能。第一节预测算法实现要进行边预测，首先读入目标网络，基于此网络，对其中的未知边进行预测。共同邻居主要基于两个节点所共有的相邻节点，而要了解节点的相邻节点就需要观察已存在的边的情况，因此，它以网络中已存在的边为主要数据基础。回顾CN指标定义可知，CN将两节点拥有的共同的相邻节点的数量作为相似性指标，即共同邻居数量越大，两节点间连边存在的可能性越大。而我
40、们希望预测算法最终运行的结果是预测出网络中未知边的集合内应该存在的边。因此，我们要设定一个参数，一旦两个节点的共同邻居数量超过这个参数，我们认定这两节点间应该存在连边，而这个参数应当视目标网络的复杂程度而定。（经大量实验发现，这个参数取5比较合理，预测效果最好，所以将此参数定为5）在算法中，首先读入网络中节点的数量n，并以此为依据，生成大小为nn的二维矩阵。接下来是共同邻居数量的获取及存储。主要有两种方法。第一种是读入网络中所有的边，并以此为依据生成成邻接矩阵，并用二维数组对其进行保存。将二维数组进行自乘，会得到二次邻接矩阵，这个矩阵中的元素值代表的是一个对象能通过两步从一个节点到达另一个节点
41、的路径数。这个对象经过的中间节点显然就是两个节点都相邻的节点，而路径数则可表示不同中间节点的数量，即共同邻居的数量，我们称这个二维矩阵为CN指标的存储矩阵。第二种方法是遍历网络中所有节点对，利用计数器记录在遍历过程中其出现共同的相邻节点次数，即得到CN指标，同样需将其存入二维数组。最后，用循环语句遍历CN指标的存储矩阵，将其中的元素值与之前设定的参数进行比较，当元素值大于参数值，即认定，对应两个节点间的边经预测后确定是存在的。具体程序代码见附录B。第二节Cytoscape边预测功能实现上一章中，我们已实现了简单的Cytoscape的插件开发，因为集成开发环境的发展已较为完善，而且该方法过程简单
42、，实现的插件也具有更好的插拔特性，在这里，我们选择在集成开发环境中开发插件。跟随第三章第二节第二小节所示步骤，我们能实现简单的具有隐藏孤立节点功能的插件。因为Cytoscape插件之间的框架结构基本一致，一般的插件都可在此基础上，通过对功能函数及一些基本信息的修改来实现。边预测功能插件的实现主要需要将隐藏节点的功能函数替换为边预测的算法函数，并将菜单项的名称改为“Edge prediction”。为方便记忆，我们称隐藏孤立节点的插件为示例插件。首先，与示例插件相同，我们需要在App菜单栏下添加子菜单，唯一不同的是名称。用Eclipse打开示例插件，双击示例插件的CyActivator类，在其中
43、找到初始化子菜单项变量的语句，将字符串“Hide unconnected Nodes”用“Edge prediction”替换，此时，示例插件中子菜单的名称即变为边预测插件所要求的名称。其次，我们将完成子菜单响应的功能，即点击“Edge prediction”项，Cytoscape能实现边预测功能。在示例插件中，子菜单的功能是通过MenuAction类进行响应的，这同样适用于边预测插件。在示例插件的菜单动作类中，实现孤立节点隐藏功能是通过遍历所有节点，筛选没有出连接的节点，并用setVisualProperty函数将其可视性设为false，其代码可以被快速地找到。因此，将此部分代码替换为边预测
44、功能所需程序即可实现目标插件。这一部分中，首先添加预测算法，使之能进行未知边存在与否的预测，根据预测结果，确定未知边中存在的边，利用addEdge（）函数将预测得到的边添加到网络中，并利用setVisualProperty将这些边的类型设置为虚线。具体程序及代码见附录B。第三节Cytoscape预测功能展示对示例插件的功能代码进行替换后，依照上一章中运行生成应用的过程，将生成的jar文件，导入Cytoscape。于是，Cytoscape的Apps菜单下便有子菜单“Edge prediction”。打开一个网络，或手绘一个网络，下图为示例：图 4.3.1 示例图点击Apps菜单下的“Edge p
45、rediction”，结果如下：图 4.3.2 结果图预测得到最下方两个节点间存在连边。第四节算法评价边预测所使用的指标最终都指向边存在的可能性，而预测结果与实际边的存在情况的符合程度根据选用指标的不同而不同，这个符合程度被称为边预测算法的精确度。描述预测精确度根据侧重点不同主要有三个指标。AUC是从整体上描述预测准确性的指标，基于给定的预测算法，最终都会给每一条目标边赋予一个值，即该边存在的概率值。分别随机从测试集和不存在的边的集合中选择一条边，在测试集中选择的边存在的概率值高的概率可理解为AUC指标9。很多情况下，并不是所有的预测结果都有考虑的必要。一般来说，我们仅仅要考虑算法预测最初若干
46、条边的准确程度，并以此作为选取预测算法的依据。此时，常用的指标是精确度（precision），它的含义也非常简单，即在进行了预测的前N条边中，预测结果与实际情况相符的边所占的比例。N作为一个参数可视情况选取。排序分同样也是预测算法评价常用的指标，它主要考虑将边进行预测后被赋予的值进行排序后，测试边在所有未知边中的所处的位置。每条测试边都有一个排序分，即所在排名与未知边总数的比值，而系统的排序分则是测试边排序分的平均值。我们在八个真实网络中计算共同邻居指标的AUC值，以此来衡量基于CN指标的算法预测的精确性，这八个网络分别是美国航空网络（USAir）、科学家合作网络（NS）、政治博客网络（PB）
47、、蛋白质相互作用网络（Yeast）、线虫的神经网络（C.elegans）、食物链网络（FWFB）、电力网络（Power）、路由器网络（Router）0，得到的AUC值如下表所示：表5-1 基于CN的预测算法的AUC值表0USAirNSPBYeastC.elegansFWFBPowerRouterAUC0.95420.97960.92340.91510.84660.60530.62500.6522在这八个网络中，前5个网络的复杂性高，边多且密度大。而数据显示，在这些网络中，以CN为基础的预测算法的AUC值很高，即预测算精度较高，说明CN指标更实用于连接密度较高的网络。第四章边预测实验本章将导入一个真实网络微信好友网络，将其作为预测插件的应用对象。在真实网络中，隐藏几条真实边，并利用预测插件对隐藏真实边后的网络进行边预测。最后，分别将预测结果与真实网络进行对比，分析预测插件的可行性与可信度。第一节真实网络导入首先，需要进行网络建模，即将真实的关联关系构造为可视的网络图。在这里，我们将采用微信好友网络，其中节点代表微信用户，边描述了用户之间的好友关系。在该网络中，网络结构经调查所得，而用户姓名则为化名。第一步，我们先选取我身边的七名同学：杨珍、陈霖、王亚、龙宇、傅小平、刘一飞、吴语。他们互相之间都为微信好友。同时，在他们微信好友中任意选取四名好友，用以构建网络，得到简单