邊預(yù)測(cè)畢業(yè)論文

1、目錄摘要iiiabstractiv第一章綜述1第一節(jié)邊預(yù)測(cè)的用途1第二節(jié)基于相似性的邊預(yù)測(cè)方法2一、局部信息下的相似性分析2二、路徑基礎(chǔ)上的相似性分析2三、隨機(jī)游走中的相似性分析3第三節(jié)cytoscape簡(jiǎn)介4第四節(jié)論文結(jié)構(gòu)5第二章cytoscape插件開(kāi)發(fā)簡(jiǎn)介6第一節(jié)cytoscape的軟件結(jié)構(gòu)6第二節(jié)cytoscape二次開(kāi)發(fā)7一、cytoscape編程控制8二、cytoscape插件開(kāi)發(fā)9第三章預(yù)測(cè)算法及其實(shí)現(xiàn)17第一節(jié)預(yù)測(cè)算法實(shí)現(xiàn)17第二節(jié)cytoscape邊預(yù)測(cè)功能實(shí)現(xiàn)18第三節(jié)cytoscape預(yù)測(cè)功能展示19第四節(jié)算法評(píng)價(jià)20第四章邊預(yù)測(cè)實(shí)驗(yàn)22第一節(jié)真實(shí)網(wǎng)絡(luò)導(dǎo)入22第二節(jié)預(yù)測(cè)插

2、件應(yīng)用及結(jié)果23第三節(jié)預(yù)測(cè)結(jié)果分析26總結(jié)28參考文獻(xiàn)30附錄32附錄a32附錄b55摘要在大數(shù)據(jù)時(shí)代，網(wǎng)絡(luò)建模成為數(shù)據(jù)處理的一項(xiàng)重要手段。而邊預(yù)測(cè)作為處理網(wǎng)絡(luò)的有效方式也逐漸受到更多的關(guān)注。邊預(yù)測(cè)是指在網(wǎng)絡(luò)中，通過(guò)已知的網(wǎng)絡(luò)信息，例如節(jié)點(diǎn)，邊或網(wǎng)絡(luò)結(jié)構(gòu)等，來(lái)對(duì)網(wǎng)絡(luò)中存在性不明的邊進(jìn)行預(yù)測(cè)6。邊預(yù)測(cè)既能解決生物網(wǎng)絡(luò)中實(shí)驗(yàn)方向不明朗的問(wèn)題，又能在數(shù)據(jù)缺失或難以集全的情況下較為精確地對(duì)研究社會(huì)網(wǎng)絡(luò)進(jìn)行研究分析。同時(shí)還能糾正網(wǎng)絡(luò)中錯(cuò)誤連邊，完成網(wǎng)絡(luò)結(jié)構(gòu)重組。而cytoscape作為一項(xiàng)重要的網(wǎng)絡(luò)處理軟件，既能對(duì)網(wǎng)絡(luò)進(jìn)行可視化處理，又能對(duì)網(wǎng)絡(luò)進(jìn)行集成分析，已在各種復(fù)雜網(wǎng)絡(luò)分析處理和可視化領(lǐng)域應(yīng)用中占據(jù)

3、十分重要的地位。但是，邊預(yù)測(cè)作為網(wǎng)絡(luò)處理的強(qiáng)大手段，目前cytoscape仍然缺乏通用的預(yù)測(cè)插件，因此，本文以cytoscape為軟件平臺(tái)，基于共同鄰居的邊預(yù)測(cè)算法，實(shí)現(xiàn)了符合osgi標(biāo)準(zhǔn)的cytoscape插件，總結(jié)了cytoscape第三方開(kāi)發(fā)接口和插件開(kāi)發(fā)流程，為開(kāi)發(fā)通用的cytoscape邊預(yù)測(cè)插件包提供了參考。關(guān)鍵詞：邊預(yù)測(cè)；cytoscape；插件；相似性abstractin the era of big data, network modeling becomes one of these important methods. and edge prediction draws

4、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 directio

5、n 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 plays a

6、n 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 no u

7、niversal 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 cytos

8、cape 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第一章綜述第一節(jié)邊預(yù)測(cè)的用途邊預(yù)測(cè)是指在網(wǎng)絡(luò)中，通過(guò)已知的網(wǎng)絡(luò)信息，例如節(jié)點(diǎn)，邊或者是網(wǎng)絡(luò)結(jié)構(gòu)等，來(lái)對(duì)網(wǎng)絡(luò)中存在性不明的邊進(jìn)行預(yù)測(cè)。該預(yù)測(cè)包含兩層概念，一是評(píng)估未知邊存在的可能性，另一個(gè)則是預(yù)測(cè)已知尚未存在的邊將來(lái)產(chǎn)生鏈接的可能

9、性。因此，邊預(yù)測(cè)問(wèn)題成了各個(gè)領(lǐng)域不同科學(xué)家視線的聚焦點(diǎn)。首先，邊預(yù)測(cè)在實(shí)際應(yīng)用領(lǐng)域具有十分重大的價(jià)值。例如，生物研究領(lǐng)域的各種生物分子交互網(wǎng)絡(luò)、代謝網(wǎng)絡(luò)中，需要通過(guò)大量的實(shí)驗(yàn)，并依賴其結(jié)果才能對(duì)網(wǎng)絡(luò)進(jìn)行內(nèi)在規(guī)律揭示和分析。而網(wǎng)絡(luò)內(nèi)的內(nèi)部相互作用歸根到底就是節(jié)點(diǎn)之間的連接關(guān)系。 然而，巨大的生物網(wǎng)絡(luò)在實(shí)驗(yàn)中顯露出來(lái)的僅僅是網(wǎng)絡(luò)中相當(dāng)小的一部分。僅以蛋白質(zhì)網(wǎng)絡(luò)為例研究其交互作用，就人類本身我們認(rèn)識(shí)到的竟只有0.3%。即使是簡(jiǎn)單生物酵母菌的蛋白質(zhì)相互作用，仍有80%不被人類所掌握。如果在此類實(shí)驗(yàn)中，僅僅依靠龐大的實(shí)驗(yàn)數(shù)量進(jìn)行枚舉式的研究，那么，揭示其網(wǎng)絡(luò)中邊的存在性需要的將是無(wú)比巨大的實(shí)驗(yàn)成本與資源

10、。但是，能在已知的網(wǎng)絡(luò)中找到合理精確的邊預(yù)測(cè)算法，以此進(jìn)行邊預(yù)測(cè)，并利用預(yù)測(cè)結(jié)果引導(dǎo)實(shí)驗(yàn)方向，將有可能極大的在減少實(shí)驗(yàn)數(shù)量的同時(shí)提高實(shí)驗(yàn)的成功率，這不僅能很大程度上節(jié)省實(shí)驗(yàn)消耗，還能大大地加快研究進(jìn)程。其次，社會(huì)網(wǎng)絡(luò)研究分析過(guò)程中會(huì)出現(xiàn)數(shù)據(jù)缺失或難以集全的問(wèn)題，此時(shí)，邊預(yù)測(cè)又將展現(xiàn)它在保證精確性前提下輔助分析網(wǎng)絡(luò)結(jié)構(gòu)的強(qiáng)大能力。除此之外，邊預(yù)測(cè)還能幫助分析并演化網(wǎng)絡(luò)。舉個(gè)簡(jiǎn)單例子，在當(dāng)下迅速發(fā)展并深受民眾喜愛(ài)的社交在線網(wǎng)絡(luò)中，邊預(yù)測(cè)可以基于用戶已有的好友網(wǎng)絡(luò)分析出整個(gè)網(wǎng)絡(luò)中未成為該用戶好友單應(yīng)該彼此相識(shí)的使用者，并將此結(jié)果推薦給該用戶，以此演化社交在線網(wǎng)絡(luò)。此外，邊預(yù)測(cè)仍有其他諸多作用，它方法

11、和理論同樣可被節(jié)點(diǎn)類型預(yù)測(cè)所借鑒，它可以用以驗(yàn)證已存在邊的準(zhǔn)確性，并以此清除錯(cuò)誤鏈接，并完成網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化和重組。例如在一些實(shí)驗(yàn)中，不同的數(shù)據(jù)可能引導(dǎo)出矛盾的結(jié)果，邊預(yù)測(cè)為我們清除不恰當(dāng)數(shù)據(jù)提供快捷準(zhǔn)確的途徑。第二節(jié)基于相似性的邊預(yù)測(cè)方法一、局部信息下的相似性分析局部信息下的相似性分析，是指運(yùn)用只需要通過(guò)部分節(jié)點(diǎn)信息便可運(yùn)算得到的相似性指標(biāo)進(jìn)行邊預(yù)測(cè)分析。這類指標(biāo)的優(yōu)勢(shì)在于復(fù)雜程度低，可運(yùn)用于規(guī)模過(guò)大的應(yīng)用網(wǎng)絡(luò)。但因其依賴的信息量有限，預(yù)測(cè)精度相對(duì)于一些全局性的指標(biāo)而言顯得不夠高。最簡(jiǎn)單常用的方法是基于共同鄰居的邊預(yù)測(cè)分析。共同鄰居一般稱為cn，全稱common neighbor ，是局部信息

12、下最簡(jiǎn)單的相似性參數(shù)。cn相似性在某種程度上又被稱為結(jié)構(gòu)等價(jià)，即，若兩個(gè)節(jié)點(diǎn)具有較多的共同鄰居，則這兩個(gè)節(jié)點(diǎn)相似。由此可見(jiàn)，cn關(guān)注的更多地是兩個(gè)節(jié)點(diǎn)存在的環(huán)境是否相同。在邊預(yù)測(cè)的應(yīng)用cn有其必要的前提假設(shè)，即若兩個(gè)節(jié)點(diǎn)的共同鄰居越多，它們之間存在連邊的可能性越大。cn指標(biāo)的定義如下：對(duì)于網(wǎng)絡(luò)的節(jié)點(diǎn)，定義其鄰居集合為集合，則兩個(gè)節(jié)點(diǎn)和的相似性就定義為它們的共同鄰居數(shù)1，即0 （1.2.1）在cn指標(biāo)的基礎(chǔ)上，考慮共同鄰居的度的影響便有了aa指標(biāo)（adami-adar指標(biāo)）。它的主要思想是度不同的共同鄰居對(duì)節(jié)點(diǎn)的影響不同，度高的共同鄰居會(huì)比度小的造成更大的影響。因此，基于共同鄰居度的大小，aa賦

13、予每個(gè)節(jié)點(diǎn)一個(gè)權(quán)重，該權(quán)重大小是該節(jié)點(diǎn)度取對(duì)數(shù)后求倒數(shù)。另一個(gè)與aa指標(biāo)近似的指標(biāo)是ra指標(biāo)，即資源分配指數(shù)10，靈感來(lái)源于網(wǎng)絡(luò)資源分配過(guò)程。在網(wǎng)絡(luò)中，沒(méi)有邊存在的節(jié)點(diǎn)間的資源交互需要以共同鄰居作為媒介，我們假設(shè)每個(gè)節(jié)點(diǎn)擁有一個(gè)單位的資源并平均分給它的鄰居，則可定義兩個(gè)節(jié)點(diǎn)的相似性為兩個(gè)節(jié)點(diǎn)共同鄰居數(shù)量的倒數(shù)。二、路徑基礎(chǔ)上的相似性分析局部信息下的相似性分析計(jì)算復(fù)雜程度低，但由于依賴信息有限，導(dǎo)致相似性分?jǐn)?shù)分布太集中，使節(jié)點(diǎn)之間的差異性不明顯，造成預(yù)測(cè)精度稍低。因此，在局部共同鄰居之后，又出現(xiàn)了依賴于局部路徑的相似性分析。周濤等經(jīng)過(guò)研究，在考慮共同鄰居的同時(shí)，又引入三階路徑因素，提出局部路徑指

14、標(biāo)并定義為 （1.2.2）其中，為可調(diào)節(jié)的參數(shù)，a為鄰接矩陣。s的值越大，邊存在的可能性越大1。此外，還有另一個(gè)指標(biāo)katz指標(biāo)，它將所有的路徑及其長(zhǎng)度納入考慮了范圍。同時(shí)，在該指標(biāo)假設(shè)了路徑越短對(duì)邊存在性的影響越大。同時(shí)，katz指標(biāo)對(duì)于不同長(zhǎng)度的路徑分別賦予不同的權(quán)重，當(dāng)然，長(zhǎng)度越短，權(quán)重越高8。它定義如下： （1.2.3）其中是可調(diào)節(jié)的參數(shù)，|表示的則是兩節(jié)點(diǎn)間長(zhǎng)度為l的路徑數(shù)量，當(dāng)其收斂時(shí)，該定義簡(jiǎn)化為（i為單位矩陣） （1.2.4）另一個(gè)路徑基礎(chǔ)上的相似性指標(biāo)是lhn-，該指標(biāo)的基本思想是在一般等價(jià)的基礎(chǔ)上提出的。一般等價(jià)是指，若兩節(jié)點(diǎn)具有相似的鄰居節(jié)點(diǎn)，則這兩個(gè)節(jié)點(diǎn)相似。與結(jié)構(gòu)等價(jià)

15、不同，這并不要求兩個(gè)節(jié)點(diǎn)擁有共同鄰居。它的最終定義式 （1.2.5）其中m代表網(wǎng)絡(luò)的總邊數(shù)，是鄰接矩陣a最大的特征值，d代表度矩陣，i為單位矩陣，為可調(diào)節(jié)的參數(shù)17。三、隨機(jī)游走中的相似性分析假設(shè)在網(wǎng)絡(luò)中有一個(gè)對(duì)象在節(jié)點(diǎn)間隨機(jī)地、沒(méi)有規(guī)律地移動(dòng)，那么在移動(dòng)過(guò)程中，會(huì)產(chǎn)生一些例如節(jié)點(diǎn)間距離的數(shù)據(jù)，基于這些數(shù)據(jù)，產(chǎn)生了對(duì)應(yīng)的相似性指標(biāo)。act指數(shù)，是基于平均通信時(shí)間的相似性指標(biāo)，它的值由對(duì)象在兩個(gè)節(jié)點(diǎn)間的游走平均步數(shù)決定，假設(shè)對(duì)象從節(jié)點(diǎn)x隨機(jī)游走到節(jié)點(diǎn)y的平均所需步數(shù)為m(x,y)，則節(jié)點(diǎn)x，y之間的平均通信時(shí)間為m(x,y)與m(y,x)的和11。當(dāng)平均通信時(shí)間越小時(shí)，兩個(gè)節(jié)點(diǎn)之間的相似程度越高

16、。因此，act指數(shù)被定義為 （1.2.6）cos+指標(biāo)，即余弦相似度指標(biāo)，它基于馬氏距離來(lái)進(jìn)行向量相似性的分析。馬氏距離常用于描述兩個(gè)向量之間的差異度，且當(dāng)其中的協(xié)方差矩陣恰好是一個(gè)單位矩陣是，就相當(dāng)于是歐式距離。而節(jié)點(diǎn)可用向量將其在歐式幾何空間中表達(dá)。因此，令節(jié)點(diǎn)x在歐式幾何空間中的坐標(biāo)向量為，可以將余弦相似性定義18為 （1.2.7）此外，基于全局范圍的隨機(jī)游走中的相似性指標(biāo)還有rwr指標(biāo)及simrank指標(biāo)等。rwr指標(biāo)基于假設(shè)對(duì)象在每次隨機(jī)游走的過(guò)程中，都有一定返回起點(diǎn)的概率。它將從節(jié)點(diǎn)x到達(dá)節(jié)點(diǎn)y的概率與從節(jié)點(diǎn)y游走到x的概率和作為相似性程度指標(biāo)。simrank指標(biāo)則考慮兩個(gè)分別以節(jié)

17、點(diǎn)x、節(jié)點(diǎn)y為起點(diǎn)的兩個(gè)對(duì)象在相遇前走過(guò)的距離。第三節(jié)cytoscape簡(jiǎn)介cytoscape是一個(gè)開(kāi)源的軟件平臺(tái)，它可以將分子的交互作用網(wǎng)絡(luò)和生物路徑進(jìn)行可視化處理，并運(yùn)用注釋、基因表達(dá)配置文件以及其他形態(tài)的數(shù)據(jù)對(duì)網(wǎng)絡(luò)進(jìn)行集成分析。雖然cytoscape最初是為了生物科學(xué)研究而設(shè)計(jì)產(chǎn)生，但是，當(dāng)下，cytoscape的應(yīng)用領(lǐng)域已不局限與生物范圍，它在各種復(fù)雜網(wǎng)絡(luò)分析處理和可視化領(lǐng)域應(yīng)用中占據(jù)十分重要的地位。cytoscape的核心提供了一些基本的操作來(lái)對(duì)數(shù)據(jù)進(jìn)行交互、分析和可視化。除此之外，其他一些cytoscape本身不具備的操作可以通過(guò)插件的方式導(dǎo)入其中。插件可以被應(yīng)用于網(wǎng)絡(luò)分析、分子分

18、布分析、新布局設(shè)計(jì)、新支持類型添加、腳本處理以及數(shù)據(jù)庫(kù)連接。同時(shí)，cytoscape的使用者可以通過(guò)基于java技術(shù)的開(kāi)源cytoscape用戶界面發(fā)展cytoscape的諸多功能，而cytoscape的插件開(kāi)發(fā)社區(qū)正在進(jìn)一步壯大。目前，cytoscape已存在可實(shí)現(xiàn)各類功能的插件，而這些插件在cytoscape插件商城都有收錄。cytoscape 3 具有模塊化架構(gòu)，是目前較為主流的cytoscape版本。考慮其長(zhǎng)期可維護(hù)性，它已基本取代了cytoscape2.x系列版本。該版本添加了包括新用戶接口、新式可視化函數(shù)、隨意的命令行分布以及多樣化的翻譯引擎等新功能。直到2014年11月，cyto

19、scape社區(qū)還在緊張的從2.x版本向3.x版本進(jìn)化，而插件開(kāi)發(fā)人員正努力使2.x版本的cytoscape插件能適應(yīng)3.x及以后版本。第四節(jié)論文結(jié)構(gòu)本文主要闡述了cytoscape插件開(kāi)發(fā)方法以及邊預(yù)測(cè)方法及算法實(shí)現(xiàn)。并以osgi為框架，利用eclipse完成插件編程并最終導(dǎo)入cytoscape，完成圖形化的關(guān)聯(lián)關(guān)系預(yù)測(cè)。本文主要有五章。第一章是綜述，主要邊預(yù)測(cè)的用途以及對(duì)cytoscape的基本情況進(jìn)行簡(jiǎn)介，簡(jiǎn)要描述研究的方向。并綜述邊預(yù)測(cè)方法，介紹了當(dāng)前邊預(yù)測(cè)領(lǐng)域所常用而且較為簡(jiǎn)單的邊預(yù)測(cè)的方法，主要描述在邊預(yù)測(cè)過(guò)程中所利用的指標(biāo)，及采用相應(yīng)指標(biāo)所基于的假設(shè)。第二章著眼于cytoscape

20、的軟件結(jié)構(gòu)，分析其中各個(gè)模塊的作用及內(nèi)部的編程控制，描述各類cytoscape操作所基于的代碼基礎(chǔ)。同時(shí)介紹了兩種cytoscape插件實(shí)現(xiàn)的方法，并按步驟完成了簡(jiǎn)單的隱藏插件。第三章重點(diǎn)講解了如何利用邊預(yù)測(cè)的相似性指標(biāo)完成邊預(yù)測(cè)算法，并以第二章完成的簡(jiǎn)單插件為基礎(chǔ)框架，實(shí)現(xiàn)cytoscape的邊預(yù)測(cè)功能插件。并利用auc指標(biāo)對(duì)算法進(jìn)行評(píng)價(jià)。第四章是插件應(yīng)用實(shí)驗(yàn)，通過(guò)引入真實(shí)網(wǎng)絡(luò)，對(duì)其隱藏的必要邊進(jìn)行預(yù)測(cè)，通過(guò)將預(yù)測(cè)結(jié)果與現(xiàn)實(shí)結(jié)果相對(duì)比，分析算法的利弊。第五章對(duì)全文進(jìn)行總結(jié)第二章cytoscape插件開(kāi)發(fā)簡(jiǎn)介第一節(jié)cytoscape的軟件結(jié)構(gòu)cytoscape 3.0致力于模塊化結(jié)構(gòu)建設(shè)。該結(jié)

21、構(gòu)中，應(yīng)用程序由一系列的jar文件組成，每個(gè)jar文件包含完整定義的程序的函數(shù)子集。該面向?qū)ο蟮脑O(shè)計(jì)基于osgi服務(wù)器模型，將應(yīng)用程序編程接口及其實(shí)現(xiàn)分別打包進(jìn)不同的jar文件。而其目的是提供一系列定義了公共cytoscape程序設(shè)計(jì)的接口。每個(gè)應(yīng)用程序編程接口的jar文件都會(huì)包含對(duì)應(yīng)的完全由私人的代碼構(gòu)成的執(zhí)行jar文件。執(zhí)行jar文件中會(huì)提供接口jar文件中定義的服務(wù)器接口。該方法能實(shí)現(xiàn)給定編程接口中不同執(zhí)行jar文件的快速替換。同時(shí)，它還清晰地對(duì)公共的代碼和私人的代碼進(jìn)行分類從而讓開(kāi)發(fā)者知道哪些代碼能被改變而哪些不能。cytoscape核心組件包含了多種多樣的模塊，每個(gè)模塊中都封裝了關(guān)鍵

22、的函數(shù)。當(dāng)前，這些模塊主要有數(shù)據(jù)模型、視圖模型、任務(wù)執(zhí)行、映射、事件處理、輸入輸出、布局、應(yīng)用結(jié)構(gòu)、描述、會(huì)話、網(wǎng)絡(luò)服務(wù)、應(yīng)用程序、實(shí)用模塊。每個(gè)提到的模塊都包含獨(dú)立的編程接口及實(shí)現(xiàn)的jar文件cytoscape主要支持網(wǎng)絡(luò)和表兩種數(shù)據(jù)類型，在數(shù)據(jù)模型模塊中，其中網(wǎng)最基本的接口是cynetwork，可以此對(duì)網(wǎng)及邊和節(jié)點(diǎn)進(jìn)行必要的操作。視圖模塊中的核心接口是visualproperty，它為cytoscape控制了了對(duì)視圖變量的操作，例如節(jié)點(diǎn)顏色、隱藏節(jié)點(diǎn)等。cytoscape 3 的核心模塊是任務(wù)執(zhí)行模塊，任務(wù)接口主要的兩個(gè)函數(shù)時(shí)run()和cancel()，用以確定一項(xiàng)操作的執(zhí)行與否。輸入輸

23、出模塊控制著cytoscape與環(huán)境的交互，可確定數(shù)據(jù)的輸入輸出、及數(shù)據(jù)類型等。布局模塊抽象出了一些一般化的網(wǎng)絡(luò)布局操作，它能分析一個(gè)網(wǎng)絡(luò)并以網(wǎng)絡(luò)布局的放肆提供結(jié)果。應(yīng)用結(jié)構(gòu)模塊主要由兩部分組成，一部分用以保證任何可行的osgi bundle都能被用作插件，另一部分則是簡(jiǎn)單的插件程序接口，用以滿足非osgi規(guī)范的插件。描述模塊的編程接口非常簡(jiǎn)化，只具有三個(gè)初級(jí)的接口分別用以允許翻譯引擎的創(chuàng)建、翻譯引擎支持格式的描述以及翻譯引擎使用記錄的管理。會(huì)話模塊包含了對(duì)對(duì)話框進(jìn)行操作的所有必要的接口，可實(shí)現(xiàn)對(duì)話框的關(guān)閉、對(duì)話框中內(nèi)容存儲(chǔ)、導(dǎo)入等一系列功能。網(wǎng)絡(luò)服務(wù)模塊主要管理cytoscape聯(lián)網(wǎng)操作，并

24、為服務(wù)器、客戶端等的創(chuàng)建使用操作提供支持。應(yīng)用程序模塊主要包含了所有應(yīng)用程序一般性的接口，用以控制例如菜單欄、按鈕、面板等。應(yīng)用結(jié)構(gòu)模塊則主要由兩部分組成，一部分用以保證任何可行的osgi bundle都能被用作插件，另一部分則是簡(jiǎn)單的插件程序接口，用以滿足非osgi規(guī)范的插件。而當(dāng)下的cytoscape 3.0只是打包了必要的jar文件，并在osgi容器中運(yùn)行。osgi英文全稱open service gateway initiative，它是osgi聯(lián)盟發(fā)起的基于java平臺(tái)的模塊化規(guī)范。osgi起初著眼于嵌入式程序開(kāi)發(fā)，為各類應(yīng)用提供環(huán)境中的模塊化服務(wù)。由于osgi的熱插拔特性，它逐漸在

25、java開(kāi)發(fā)中發(fā)揮越來(lái)越重要的作用。當(dāng)前，osgi規(guī)范已對(duì)java模塊化建設(shè)的各種控制（例如開(kāi)發(fā)、更新等）進(jìn)行了定義，其中還囊括了一些基本模型和格式化接口。osgi規(guī)范包含了眾多的子規(guī)范，一部分主要運(yùn)用于osgi框架的規(guī)范化描述，還有一部分則構(gòu)成了以osgi為基礎(chǔ)，在應(yīng)用程序開(kāi)發(fā)的編程中建立標(biāo)準(zhǔn)接口的規(guī)范化服務(wù)。osgi可以實(shí)現(xiàn)無(wú)需重啟的條件下，應(yīng)用程序中各個(gè)模塊的動(dòng)態(tài)變化（如安裝、功能變化等），并能允許同一模塊的不同版本在容器中的運(yùn)行兼容。osgi框架在osgi中占據(jù)核心地位，它的基本模塊化單元bundle。bundle與插件相似，是一個(gè)jar文件，包含了一個(gè)插件所需要的所有資源。簡(jiǎn)化來(lái)說(shuō)，

26、osgi給各種容器和應(yīng)用程序提供了一個(gè)通用的可兼容的java架構(gòu)。在這個(gè)架構(gòu)中，插件能被直接模塊化部署和實(shí)現(xiàn)，而實(shí)現(xiàn)了得插件可直接被目標(biāo)應(yīng)用程序所接納。第二節(jié)cytoscape二次開(kāi)發(fā)為cytoscape編寫插件，將其導(dǎo)入cytoscape使其實(shí)現(xiàn)新的功能就是 cytoscape的二次開(kāi)發(fā)。為實(shí)現(xiàn)cytoscape的二次開(kāi)發(fā)，我們首先必須了解cytoscape內(nèi)部的函數(shù)控制和運(yùn)行機(jī)制，并掌握插件的開(kāi)發(fā)及導(dǎo)入方式。一、cytoscape編程控制在2.1節(jié)中，我們介紹了cytoscape的軟件架構(gòu)，其主要由多個(gè)不同的模塊組成，而要編寫cytoscape的插件，必須對(duì)主要模塊的編程控制有一定的了解。

27、cytoscape是由具有不同功能的模塊集成而來(lái)，而不同的模塊都被打包成特定的jar包。當(dāng)編寫插件對(duì)cytoscape進(jìn)行控制時(shí)，必須在cyactivator類中通過(guò)申明，取得相應(yīng)服務(wù)器的權(quán)限。對(duì)于swing應(yīng)用，cytoscape內(nèi)由cytopanelomponent服務(wù)器實(shí)現(xiàn)對(duì)其界面（主要是面板的各類操作，例如添加一個(gè)自定義面板等）的控制，由cyaction接口控制菜單項(xiàng)。同時(shí)，cytoscape在cynetworkmanager和cynetworkfactory兩個(gè)服務(wù)器的支持下，可以完成對(duì)網(wǎng)絡(luò)的例如創(chuàng)建刪除等各項(xiàng)操作，并通過(guò)cynetwork、cyactivator、cytableut

28、il、cyrow等接口實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)內(nèi)部的具體控制（例如添加新的節(jié)點(diǎn)等）。類似的，cynetworkviewfactory和cynetworkviewmanager是cytoscape中網(wǎng)絡(luò)視圖控制的中心服務(wù)器，具體的操作都被打包在 cynetworkview類中。在任務(wù)執(zhí)行、映射、事件處理、輸入輸出、布局、應(yīng)用結(jié)構(gòu)、描述、會(huì)話、網(wǎng)絡(luò)服務(wù)、應(yīng)用程序、實(shí)用模塊等模塊同樣的具有其相應(yīng)的服務(wù)器，以及包含了該模塊各項(xiàng)操作的類，具體內(nèi)容見(jiàn)附錄a（cytoscape的內(nèi)部編程控制）。在此，僅以創(chuàng)建子菜單為例，示范簡(jiǎn)單的cytoscape編程控制：應(yīng)用開(kāi)發(fā)者需要先定義一個(gè)實(shí)現(xiàn)了cyaction 或是拓展了abs

29、tractcaction的類，然后把它申明為一個(gè)osgi服務(wù)器。cytoscape內(nèi)部的cyaction管理器會(huì)拾起這個(gè)新申明的服務(wù)器，并按照定義創(chuàng)建一個(gè)菜單項(xiàng)，并說(shuō)明其根菜單項(xiàng)。程序如下，第一步申明類：同時(shí)，在cyactivator類中，將其命名為“edge prediction”并注冊(cè)為服務(wù)器：二、cytoscape插件開(kāi)發(fā)（一） 一般化的app插件實(shí)現(xiàn)cytoscape 是一個(gè)用網(wǎng)絡(luò)實(shí)現(xiàn)數(shù)據(jù)的一體化、可視化及數(shù)據(jù)分析的一項(xiàng)開(kāi)源軟件工具，下面我要介紹的內(nèi)容主要包括：1.為cytoscape寫一個(gè)簡(jiǎn)單的功能性應(yīng)用2.應(yīng)用的jar文件的生成3.將最終的應(yīng)用配置到cytoscape中我們將通過(guò)實(shí)

30、現(xiàn)一個(gè)完整的功能性應(yīng)用來(lái)解釋怎樣為cytoscape創(chuàng)建一個(gè)簡(jiǎn)單應(yīng)用（套裝應(yīng)用）。這個(gè)功能性應(yīng)用會(huì)在select菜單欄下添加一個(gè)點(diǎn)擊之后可以當(dāng)前網(wǎng)絡(luò)視圖中隱藏所有度數(shù)為0的節(jié)點(diǎn)的菜單項(xiàng)。開(kāi)始前，你首先需要安裝cytoscape（3.x版本及以上）及1.6版本以上的java development kit (jdk)。除此之外，你還需要下載cytoscape swing app api jar（這是對(duì)cytoscape 3.1 有效地），注意保存的路徑，稍后我們將會(huì)用到該路徑。下載安裝cytoscape和swing app api jar之后，為你要寫的簡(jiǎn)單應(yīng)用的源代碼創(chuàng)建一個(gè)目錄。接下來(lái)，我們

31、先創(chuàng)建代碼框架，這個(gè)框架對(duì)所有的簡(jiǎn)單應(yīng)用來(lái)說(shuō)都是一樣的，代碼如下：（注意：載這個(gè)簡(jiǎn)單的java類中，我們不把代碼進(jìn)行打包，所以我們的類都會(huì)在一個(gè)簡(jiǎn)單的目錄中）把這代碼保存為hidesingletonnodesapp.java文件。接下來(lái)，我們?yōu)閏toscape菜單項(xiàng)添加框架，框架代碼如下：我們把這段代碼保存為menuaction.java在應(yīng)用主類的代碼框架中，我們加入如下幾行代碼：得到最終的代碼如下:我們?cè)诓藛蝿?dòng)作類中加入隱藏孤立點(diǎn)的代碼，代碼寫在actionperformed() 方法中。同時(shí)，我們還加入了import 代碼來(lái)申明我們所需要的apis。具體代碼如下： 打開(kāi)命令行界面，進(jìn)入源

32、代碼所在的文件夾，我們用以下代碼編譯兩個(gè)類：javac cp “.;/路徑/cytoscape-swing-app-api-3.2.0.jar” *.java其中，路徑就是cytoscaoe-swing-app-api-3.2.0.jar所在的位置，運(yùn)行后，會(huì)在源代碼所在文件夾生成兩個(gè)可以被打包成jar文件的class文件。一個(gè)簡(jiǎn)單的應(yīng)用是一個(gè)有meta-inf的jar文件。它確定了類在abstractcyapp的入口和路徑以及應(yīng)用的主類。為了將其導(dǎo)入jar文件中，我們創(chuàng)建一個(gè)包含以下內(nèi)容的app-manifest文件：最后，我們通過(guò)在命令提示符中先進(jìn)入類所在目錄，然后通過(guò)命令：建立應(yīng)用的ja

33、r文件。最終完成的jar文件就是可以運(yùn)行的應(yīng)用，我們可以在cytoscape中對(duì)其進(jìn)行測(cè)試。首先打開(kāi)cytoscape，選中apps菜單下的app manager。在彈出來(lái)的對(duì)話框中選中從文件中安裝按鈕，選中事先完成的jar文件（hidesingletonnodesapp.jar）。我們可以畫或?qū)胍粋€(gè)有游離點(diǎn)的網(wǎng)絡(luò)，然后點(diǎn)擊apps菜單下的hide unconnected nodes選項(xiàng)觀察網(wǎng)絡(luò)中的游離點(diǎn)是否被隱藏。（二）集成開(kāi)發(fā)環(huán)境下的app插件實(shí)現(xiàn)利用osgi框架可以極大的簡(jiǎn)化app插件的實(shí)現(xiàn)過(guò)程，我們將完成創(chuàng)建osgi bundle類型的cytoscape 3的插件應(yīng)用。創(chuàng)建一個(gè)本地的

34、cytoscape 3插件應(yīng)用，我們本來(lái)需要理解osgi的基礎(chǔ)，但是現(xiàn)在又很多工具可以自動(dòng)化實(shí)現(xiàn)這個(gè)進(jìn)程。在cytoscape 3中，core和apps沒(méi)有明顯區(qū)別，所有的程序又是osgi bundle。我們需要的工具有jdk 6或7、maven3.x和eclipse。在eclipse中用maven原型創(chuàng)建app我們能用cytoscape maven原型來(lái)創(chuàng)建osgi bundle應(yīng)用。這樣，我們可以快速建立一個(gè)可以快速擴(kuò)充成滿足你需要的基于maven的工程，它會(huì)自動(dòng)生成基于osgi中bundle的cytoscape app。具體建立過(guò)程如下：選中file選項(xiàng)，在子菜單中選中new下的othe

35、r。在彈出的選項(xiàng)中，選擇maven下的maven project 并點(diǎn)擊next后繼續(xù)點(diǎn)擊next。首先，導(dǎo)入cytoscape 原型目錄（如果已經(jīng)有可跳過(guò)下面步驟）。點(diǎn)擊configure在彈出的對(duì)話框中選擇add remote catalog會(huì)彈出如下對(duì)話框圖3.2.2.1在catalog file中粘貼上如下網(wǎng)址：在description中輸入你自定的名稱，這里我們用cytoscape release。點(diǎn)ok后再選中apply。在彈出的對(duì)話框中，catalog項(xiàng)選中catalog release，并取消勾選第一項(xiàng)，會(huì)出現(xiàn)如下界面，選擇cyaction-app 3.0.0，點(diǎn)擊next。圖

36、3.2.2.2在接下來(lái)的對(duì)話框中填入必要信息，我們填寫group id和artifact id如下，package會(huì)自動(dòng)生成。圖3.2.2.3點(diǎn)擊finish后需要等待10至20秒時(shí)間，然后eclipse會(huì)創(chuàng)建一個(gè)工程包含你在上一步指定包的maven工程，工程目錄如下所示：圖3.2.2.4右鍵點(diǎn)擊pom.xml，選擇run as菜單下的maven install。eclipse會(huì)在工程目錄的target文件夾中生成目標(biāo)jar文件。運(yùn)行生成的應(yīng)用首先，我們需要找到生成的jar文件，并將其復(fù)制到如下目錄中：c:usersadministratorcytoscapeconfiguration3app

37、sinstalled，然后運(yùn)行cytoscape，注意，我們通過(guò)執(zhí)行cytoscape.bat文件來(lái)進(jìn)行而不是用cytoscape.exe。 在命令行中，輸入list，它會(huì)顯示當(dāng)前osgi工作環(huán)境中正在運(yùn)行的bundle，我們能找到我們之前完成的目標(biāo)應(yīng)用。在打開(kāi)的cytoscape中，我們能在apps菜單下發(fā)現(xiàn)生成的“hello world app”菜單項(xiàng)。具體應(yīng)用轉(zhuǎn)化在這個(gè)例子中，我們將添加與第一節(jié)相同的應(yīng)用，即隱藏網(wǎng)絡(luò)視圖中的所有孤立點(diǎn)。首先，我們先雙擊打開(kāi)pom.xml，打開(kāi)下方的dependencies，選擇add按鈕，在跳出的對(duì)話框中，對(duì)應(yīng)輸入如下內(nèi)容：group id ：org.c

38、ytoscapeartifact id ：presentation-apiversion3.0.0我們雙擊打開(kāi)menuaction類，將其代碼變得與第一節(jié)所訴的menuaction類的最終版本一致，這里不贅述代碼。最后，編輯cyactivator類，將“hello world app”替換為“hide unconnected nodes”即可。同樣右鍵單擊pom.xml，選中run as下的maven install生成目標(biāo)jar文件，并重復(fù)“運(yùn)行生成應(yīng)用”的過(guò)程。我們能在cytoscape的apps菜單想發(fā)現(xiàn)“hide unconnected nodes”選項(xiàng)，在任意倒入或畫一個(gè)有孤立節(jié)點(diǎn)的

39、網(wǎng)絡(luò)后，點(diǎn)擊該選項(xiàng)，則所有的孤立點(diǎn)被隱藏。第三章預(yù)測(cè)算法及其實(shí)現(xiàn)上一章中對(duì)邊預(yù)測(cè)所常用的相似度指標(biāo)進(jìn)行了介紹，本章將以共同鄰居指標(biāo)為基礎(chǔ)，實(shí)現(xiàn)完整的預(yù)測(cè)算法，并將之應(yīng)用于cytoscape插件，從而在cytoscape中實(shí)現(xiàn)可視化的邊預(yù)測(cè)功能。第一節(jié)預(yù)測(cè)算法實(shí)現(xiàn)要進(jìn)行邊預(yù)測(cè)，首先讀入目標(biāo)網(wǎng)絡(luò)，基于此網(wǎng)絡(luò)，對(duì)其中的未知邊進(jìn)行預(yù)測(cè)。共同鄰居主要基于兩個(gè)節(jié)點(diǎn)所共有的相鄰節(jié)點(diǎn)，而要了解節(jié)點(diǎn)的相鄰節(jié)點(diǎn)就需要觀察已存在的邊的情況，因此，它以網(wǎng)絡(luò)中已存在的邊為主要數(shù)據(jù)基礎(chǔ)?；仡檆n指標(biāo)定義可知，cn將兩節(jié)點(diǎn)擁有的共同的相鄰節(jié)點(diǎn)的數(shù)量作為相似性指標(biāo)，即共同鄰居數(shù)量越大，兩節(jié)點(diǎn)間連邊存在的可能性越大。而我們希望

40、預(yù)測(cè)算法最終運(yùn)行的結(jié)果是預(yù)測(cè)出網(wǎng)絡(luò)中未知邊的集合內(nèi)應(yīng)該存在的邊。因此，我們要設(shè)定一個(gè)參數(shù)，一旦兩個(gè)節(jié)點(diǎn)的共同鄰居數(shù)量超過(guò)這個(gè)參數(shù)，我們認(rèn)定這兩節(jié)點(diǎn)間應(yīng)該存在連邊，而這個(gè)參數(shù)應(yīng)當(dāng)視目標(biāo)網(wǎng)絡(luò)的復(fù)雜程度而定。（經(jīng)大量實(shí)驗(yàn)發(fā)現(xiàn)，這個(gè)參數(shù)取5比較合理，預(yù)測(cè)效果最好，所以將此參數(shù)定為5）在算法中，首先讀入網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量n，并以此為依據(jù)，生成大小為nn的二維矩陣。接下來(lái)是共同鄰居數(shù)量的獲取及存儲(chǔ)。主要有兩種方法。第一種是讀入網(wǎng)絡(luò)中所有的邊，并以此為依據(jù)生成成鄰接矩陣，并用二維數(shù)組對(duì)其進(jìn)行保存。將二維數(shù)組進(jìn)行自乘，會(huì)得到二次鄰接矩陣，這個(gè)矩陣中的元素值代表的是一個(gè)對(duì)象能通過(guò)兩步從一個(gè)節(jié)點(diǎn)到達(dá)另一個(gè)節(jié)點(diǎn)的路徑

41、數(shù)。這個(gè)對(duì)象經(jīng)過(guò)的中間節(jié)點(diǎn)顯然就是兩個(gè)節(jié)點(diǎn)都相鄰的節(jié)點(diǎn)，而路徑數(shù)則可表示不同中間節(jié)點(diǎn)的數(shù)量，即共同鄰居的數(shù)量，我們稱這個(gè)二維矩陣為cn指標(biāo)的存儲(chǔ)矩陣。第二種方法是遍歷網(wǎng)絡(luò)中所有節(jié)點(diǎn)對(duì)，利用計(jì)數(shù)器記錄在遍歷過(guò)程中其出現(xiàn)共同的相鄰節(jié)點(diǎn)次數(shù)，即得到cn指標(biāo)，同樣需將其存入二維數(shù)組。最后，用循環(huán)語(yǔ)句遍歷cn指標(biāo)的存儲(chǔ)矩陣，將其中的元素值與之前設(shè)定的參數(shù)進(jìn)行比較，當(dāng)元素值大于參數(shù)值，即認(rèn)定，對(duì)應(yīng)兩個(gè)節(jié)點(diǎn)間的邊經(jīng)預(yù)測(cè)后確定是存在的。具體程序代碼見(jiàn)附錄b。第二節(jié)cytoscape邊預(yù)測(cè)功能實(shí)現(xiàn)上一章中，我們已實(shí)現(xiàn)了簡(jiǎn)單的cytoscape的插件開(kāi)發(fā)，因?yàn)榧砷_(kāi)發(fā)環(huán)境的發(fā)展已較為完善，而且該方法過(guò)程簡(jiǎn)單，實(shí)現(xiàn)

42、的插件也具有更好的插拔特性，在這里，我們選擇在集成開(kāi)發(fā)環(huán)境中開(kāi)發(fā)插件。跟隨第三章第二節(jié)第二小節(jié)所示步驟，我們能實(shí)現(xiàn)簡(jiǎn)單的具有隱藏孤立節(jié)點(diǎn)功能的插件。因?yàn)閏ytoscape插件之間的框架結(jié)構(gòu)基本一致，一般的插件都可在此基礎(chǔ)上，通過(guò)對(duì)功能函數(shù)及一些基本信息的修改來(lái)實(shí)現(xiàn)。邊預(yù)測(cè)功能插件的實(shí)現(xiàn)主要需要將隱藏節(jié)點(diǎn)的功能函數(shù)替換為邊預(yù)測(cè)的算法函數(shù)，并將菜單項(xiàng)的名稱改為“edge prediction”。為方便記憶，我們稱隱藏孤立節(jié)點(diǎn)的插件為示例插件。首先，與示例插件相同，我們需要在app菜單欄下添加子菜單，唯一不同的是名稱。用eclipse打開(kāi)示例插件，雙擊示例插件的cyactivator類，在其中找到初

43、始化子菜單項(xiàng)變量的語(yǔ)句，將字符串“hide unconnected nodes”用“edge prediction”替換，此時(shí)，示例插件中子菜單的名稱即變?yōu)檫咁A(yù)測(cè)插件所要求的名稱。其次，我們將完成子菜單響應(yīng)的功能，即點(diǎn)擊“edge prediction”項(xiàng)，cytoscape能實(shí)現(xiàn)邊預(yù)測(cè)功能。在示例插件中，子菜單的功能是通過(guò)menuaction類進(jìn)行響應(yīng)的，這同樣適用于邊預(yù)測(cè)插件。在示例插件的菜單動(dòng)作類中，實(shí)現(xiàn)孤立節(jié)點(diǎn)隱藏功能是通過(guò)遍歷所有節(jié)點(diǎn)，篩選沒(méi)有出連接的節(jié)點(diǎn)，并用setvisualproperty函數(shù)將其可視性設(shè)為false，其代碼可以被快速地找到。因此，將此部分代碼替換為邊預(yù)測(cè)功能所

44、需程序即可實(shí)現(xiàn)目標(biāo)插件。這一部分中，首先添加預(yù)測(cè)算法，使之能進(jìn)行未知邊存在與否的預(yù)測(cè)，根據(jù)預(yù)測(cè)結(jié)果，確定未知邊中存在的邊，利用addedge（）函數(shù)將預(yù)測(cè)得到的邊添加到網(wǎng)絡(luò)中，并利用setvisualproperty將這些邊的類型設(shè)置為虛線。具體程序及代碼見(jiàn)附錄b。第三節(jié)cytoscape預(yù)測(cè)功能展示對(duì)示例插件的功能代碼進(jìn)行替換后，依照上一章中運(yùn)行生成應(yīng)用的過(guò)程，將生成的jar文件，導(dǎo)入cytoscape。于是，cytoscape的apps菜單下便有子菜單“edge prediction”。打開(kāi)一個(gè)網(wǎng)絡(luò)，或手繪一個(gè)網(wǎng)絡(luò)，下圖為示例：圖 4.3.1 示例圖點(diǎn)擊apps菜單下的“edge pred

45、iction”，結(jié)果如下：圖 4.3.2 結(jié)果圖預(yù)測(cè)得到最下方兩個(gè)節(jié)點(diǎn)間存在連邊。第四節(jié)算法評(píng)價(jià)邊預(yù)測(cè)所使用的指標(biāo)最終都指向邊存在的可能性，而預(yù)測(cè)結(jié)果與實(shí)際邊的存在情況的符合程度根據(jù)選用指標(biāo)的不同而不同，這個(gè)符合程度被稱為邊預(yù)測(cè)算法的精確度。描述預(yù)測(cè)精確度根據(jù)側(cè)重點(diǎn)不同主要有三個(gè)指標(biāo)。auc是從整體上描述預(yù)測(cè)準(zhǔn)確性的指標(biāo)，基于給定的預(yù)測(cè)算法，最終都會(huì)給每一條目標(biāo)邊賦予一個(gè)值，即該邊存在的概率值。分別隨機(jī)從測(cè)試集和不存在的邊的集合中選擇一條邊，在測(cè)試集中選擇的邊存在的概率值高的概率可理解為auc指標(biāo)9。很多情況下，并不是所有的預(yù)測(cè)結(jié)果都有考慮的必要。一般來(lái)說(shuō)，我們僅僅要考慮算法預(yù)測(cè)最初若干條邊的

46、準(zhǔn)確程度，并以此作為選取預(yù)測(cè)算法的依據(jù)。此時(shí)，常用的指標(biāo)是精確度（precision），它的含義也非常簡(jiǎn)單，即在進(jìn)行了預(yù)測(cè)的前n條邊中，預(yù)測(cè)結(jié)果與實(shí)際情況相符的邊所占的比例。n作為一個(gè)參數(shù)可視情況選取。排序分同樣也是預(yù)測(cè)算法評(píng)價(jià)常用的指標(biāo)，它主要考慮將邊進(jìn)行預(yù)測(cè)后被賦予的值進(jìn)行排序后，測(cè)試邊在所有未知邊中的所處的位置。每條測(cè)試邊都有一個(gè)排序分，即所在排名與未知邊總數(shù)的比值，而系統(tǒng)的排序分則是測(cè)試邊排序分的平均值。我們?cè)诎藗€(gè)真實(shí)網(wǎng)絡(luò)中計(jì)算共同鄰居指標(biāo)的auc值，以此來(lái)衡量基于cn指標(biāo)的算法預(yù)測(cè)的精確性，這八個(gè)網(wǎng)絡(luò)分別是美國(guó)航空網(wǎng)絡(luò)（usair）、科學(xué)家合作網(wǎng)絡(luò)（ns）、政治博客網(wǎng)絡(luò)（pb）、蛋白

47、質(zhì)相互作用網(wǎng)絡(luò)（yeast）、線蟲的神經(jīng)網(wǎng)絡(luò)（c.elegans）、食物鏈網(wǎng)絡(luò)（fwfb）、電力網(wǎng)絡(luò)（power）、路由器網(wǎng)絡(luò)（router）0，得到的auc值如下表所示：表5-1 基于cn的預(yù)測(cè)算法的auc值表0usairnspbyeastc.elegansfwfbpowerrouterauc0.95420.97960.92340.91510.84660.60530.62500.6522在這八個(gè)網(wǎng)絡(luò)中，前5個(gè)網(wǎng)絡(luò)的復(fù)雜性高，邊多且密度大。而數(shù)據(jù)顯示，在這些網(wǎng)絡(luò)中，以cn為基礎(chǔ)的預(yù)測(cè)算法的auc值很高，即預(yù)測(cè)算精度較高，說(shuō)明cn指標(biāo)更實(shí)用于連接密度較高的網(wǎng)絡(luò)。第四章邊預(yù)測(cè)實(shí)驗(yàn)本章將導(dǎo)入一個(gè)真實(shí)

48、網(wǎng)絡(luò)微信好友網(wǎng)絡(luò)，將其作為預(yù)測(cè)插件的應(yīng)用對(duì)象。在真實(shí)網(wǎng)絡(luò)中，隱藏幾條真實(shí)邊，并利用預(yù)測(cè)插件對(duì)隱藏真實(shí)邊后的網(wǎng)絡(luò)進(jìn)行邊預(yù)測(cè)。最后，分別將預(yù)測(cè)結(jié)果與真實(shí)網(wǎng)絡(luò)進(jìn)行對(duì)比，分析預(yù)測(cè)插件的可行性與可信度。第一節(jié)真實(shí)網(wǎng)絡(luò)導(dǎo)入首先，需要進(jìn)行網(wǎng)絡(luò)建模，即將真實(shí)的關(guān)聯(lián)關(guān)系構(gòu)造為可視的網(wǎng)絡(luò)圖。在這里，我們將采用微信好友網(wǎng)絡(luò)，其中節(jié)點(diǎn)代表微信用戶，邊描述了用戶之間的好友關(guān)系。在該網(wǎng)絡(luò)中，網(wǎng)絡(luò)結(jié)構(gòu)經(jīng)調(diào)查所得，而用戶姓名則為化名。第一步，我們先選取我身邊的七名同學(xué)：楊珍、陳霖、王亞、龍宇、傅小平、劉一飛、吳語(yǔ)。他們互相之間都為微信好友。同時(shí)，在他們微信好友中任意選取四名好友，用以構(gòu)建網(wǎng)絡(luò)，得到簡(jiǎn)單的網(wǎng)絡(luò)如下圖所示：圖4.

49、1.1 微信好友網(wǎng)絡(luò)原始圖同時(shí)，調(diào)查他們之間有無(wú)好友關(guān)系，在網(wǎng)絡(luò)中用連邊表示。結(jié)果如下：圖4.1.2 微信好友網(wǎng)絡(luò)局部完整圖于是，我們得到了一個(gè)較為完整的微信好友網(wǎng)絡(luò)。在圖中，劉大毛和王杰與最初選取的七名同學(xué)構(gòu)成了完全圖，因?yàn)檫@九名同學(xué)曾在一個(gè)班學(xué)習(xí)。其余好友與這七名同學(xué)間無(wú)類似特殊關(guān)系。第二節(jié)預(yù)測(cè)插件應(yīng)用及結(jié)果在本實(shí)驗(yàn)中，主要是在隱藏真實(shí)邊的前提下，應(yīng)用預(yù)測(cè)插件對(duì)網(wǎng)絡(luò)進(jìn)行邊預(yù)測(cè)。1、實(shí)驗(yàn)一：直接應(yīng)用預(yù)測(cè)功能對(duì)真實(shí)網(wǎng)絡(luò)進(jìn)行邊預(yù)測(cè)。得到的結(jié)果如下圖所示：圖4.2.1 直接預(yù)測(cè)結(jié)果圖2、實(shí)驗(yàn)二：將實(shí)驗(yàn)一預(yù)測(cè)后的結(jié)果作為完整的真實(shí)網(wǎng)絡(luò)，隱藏劉大毛與王杰兩節(jié)點(diǎn)之間的邊，同時(shí)隱藏楊珍、陳霖之間的邊，然后

50、應(yīng)用預(yù)測(cè)功能對(duì)網(wǎng)絡(luò)進(jìn)行操作。隱藏真實(shí)邊之后的網(wǎng)絡(luò)如下圖所示：圖4.2.2 隱藏邊后的原始圖預(yù)測(cè)后的結(jié)果如下：圖4.2.3 隱藏兩邊的預(yù)測(cè)結(jié)果圖3、實(shí)驗(yàn)三：隱藏楊天天、李凱之間的連接，并用對(duì)隱藏后的網(wǎng)絡(luò)進(jìn)行邊預(yù)測(cè)操作。隱藏真實(shí)邊后的網(wǎng)絡(luò)如下：圖4.2.4 隱藏楊天天與李凱連邊的網(wǎng)絡(luò)圖預(yù)測(cè)后的結(jié)果如下：圖4.2.5 隱藏連邊后的預(yù)測(cè)結(jié)果圖第三節(jié)預(yù)測(cè)結(jié)果分析實(shí)驗(yàn)一中，通過(guò)對(duì)真實(shí)網(wǎng)絡(luò)的邊預(yù)測(cè)，結(jié)果顯示任意一、任朗間可能存在連接。而在真實(shí)網(wǎng)絡(luò)中，經(jīng)過(guò)調(diào)查發(fā)現(xiàn)，任意一、任朗確實(shí)相識(shí)，但是不是微信好友，因此這個(gè)預(yù)測(cè)結(jié)果是較為準(zhǔn)確的。這說(shuō)明了邊預(yù)測(cè)功能確實(shí)具有可行性。實(shí)驗(yàn)二中，對(duì)真實(shí)的網(wǎng)絡(luò)連接，即節(jié)點(diǎn)對(duì)劉大毛

51、、王杰和楊珍、陳霖之間的邊進(jìn)行了隱藏，并以此作為邊預(yù)測(cè)的目標(biāo)網(wǎng)絡(luò)。在得到的結(jié)果中，準(zhǔn)確地預(yù)測(cè)出了這兩條邊。以劉大毛與王杰為例，經(jīng)調(diào)查發(fā)現(xiàn)這兩者具有七個(gè)共同好友，而且他們兩者與這七名共同好友的相識(shí)是在同一個(gè)環(huán)境中，而不是分別在不同環(huán)境中單獨(dú)與七個(gè)好友相識(shí)，因此，他們兩者間產(chǎn)生關(guān)聯(lián)的可能性本身就很大，這都與預(yù)測(cè)結(jié)果相吻合。而大多數(shù)情況都與實(shí)驗(yàn)二相似，只要所預(yù)測(cè)的邊周圍的網(wǎng)絡(luò)結(jié)構(gòu)達(dá)到一定的復(fù)雜度，預(yù)測(cè)結(jié)果就具有較高的可信度。而在實(shí)驗(yàn)三中，隱藏了楊天天與李凱之間的連接后，對(duì)其進(jìn)行邊預(yù)測(cè)，并未得到期望的結(jié)果，即預(yù)測(cè)未得到隱藏的真實(shí)邊。這說(shuō)明，對(duì)于楊天天與李凱只見(jiàn)的邊無(wú)法實(shí)現(xiàn)預(yù)測(cè)。但是，這并不代表邊預(yù)測(cè)功

52、能結(jié)果不具有在實(shí)驗(yàn)二中可知一般情況下，邊預(yù)測(cè)結(jié)果是可信的。那么，為什么會(huì)出現(xiàn)無(wú)法準(zhǔn)確預(yù)測(cè)的情況呢？主要原因是信息的不足，對(duì)于楊天天與李凱，他們的度都非常小，即使有共同鄰居，但是因?yàn)榫W(wǎng)絡(luò)中展現(xiàn)的信息略少，無(wú)法確定更多地共同好友，而在微信圈中，由于好友途徑的多樣性，即使有著共同好友，但他們與共同鄰居之間的關(guān)聯(lián)聯(lián)系未必是相同或相似的。所以要使邊預(yù)測(cè)具有較高的可信度，所預(yù)測(cè)的邊需處于較為復(fù)雜的網(wǎng)絡(luò)，即必須有一定的鄰居信息基礎(chǔ)。綜上所訴，在復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)中，本文實(shí)現(xiàn)的邊預(yù)測(cè)插件能有效的進(jìn)行邊預(yù)測(cè)，而且結(jié)果與真實(shí)情況的相符度很高，但是在過(guò)于簡(jiǎn)單的網(wǎng)絡(luò)結(jié)構(gòu)中，該算法的能力受到極大限制?？偨Y(jié)預(yù)測(cè)是指在不知道目標(biāo)

53、真實(shí)狀態(tài)的情況下，通過(guò)研究、假設(shè)，并基于一定的信息基礎(chǔ)對(duì)其進(jìn)行合理的推測(cè)。它在每一門學(xué)科中都占據(jù)一定的主導(dǎo)地位。在當(dāng)今的大數(shù)據(jù)時(shí)代，對(duì)于錯(cuò)綜復(fù)雜而又無(wú)比龐大的數(shù)據(jù)，網(wǎng)絡(luò)建模因其可視化和易于演化等特性，成為了數(shù)據(jù)處理中主導(dǎo)的方法之一。節(jié)點(diǎn)和邊是網(wǎng)絡(luò)的兩大基本單元，在數(shù)據(jù)處理中，節(jié)點(diǎn)往往對(duì)應(yīng)著研究對(duì)象的單體，一般是已知的。邊作為描述研究對(duì)象之間的關(guān)聯(lián)關(guān)系，總是成為網(wǎng)絡(luò)分析的重點(diǎn)對(duì)象。而本文主要著眼于當(dāng)下流行的網(wǎng)絡(luò)分析處理軟件cytoscape，著重研究邊預(yù)測(cè)方法，并將兩者結(jié)合，以插件形式在cytoscape中實(shí)現(xiàn)邊預(yù)測(cè)功能。首先，本文就邊預(yù)測(cè)的用途開(kāi)始展開(kāi)，解釋邊預(yù)測(cè)的研究必要，同時(shí)綜述了邊預(yù)測(cè)方

54、法中基于相似性的各項(xiàng)指標(biāo)。并對(duì)目標(biāo)軟件cytoscape進(jìn)行的簡(jiǎn)要的介紹。其次，從cytoscape插件開(kāi)發(fā)著手，研究cytoscape的軟件結(jié)構(gòu)，并了解cytoscape的運(yùn)行機(jī)制及模塊分布，為下一步開(kāi)發(fā)插件打下基礎(chǔ)。同時(shí)，介紹cytosacape內(nèi)部的接口與服務(wù)器，了解其具有的功能及相應(yīng)的控制接口和函數(shù)，并介紹常用操作的編程控制。重點(diǎn)通過(guò)“hello world”和隱藏節(jié)點(diǎn)功能為例，示范簡(jiǎn)單的cytoscape二次開(kāi)發(fā)，較為清晰地介紹簡(jiǎn)單插件的制作。在主體部分，本文分析并選定相似性指標(biāo)下的算法實(shí)現(xiàn)思想以及基于簡(jiǎn)單插件的邊預(yù)測(cè)插件實(shí)現(xiàn)。通過(guò)示例展示邊預(yù)測(cè)插件的功能，并對(duì)其算法進(jìn)行評(píng)估。同時(shí)，

55、選定真實(shí)網(wǎng)絡(luò)，通過(guò)對(duì)刪除真實(shí)邊作為邊預(yù)測(cè)的初始數(shù)據(jù)，并通過(guò)對(duì)邊預(yù)測(cè)結(jié)果與真實(shí)網(wǎng)絡(luò)的對(duì)比，分析邊預(yù)測(cè)插件的可行性和局限性，并對(duì)全文進(jìn)行總結(jié)回顧。本文雖實(shí)現(xiàn)了cytoscape的邊預(yù)測(cè)功能，但其算法還有較大的局限性，在算法中各指標(biāo)的運(yùn)用太單調(diào)，單純地運(yùn)用一項(xiàng)指標(biāo)并不能非常精確地刻畫網(wǎng)絡(luò)的邊預(yù)測(cè)。同時(shí)，本文實(shí)驗(yàn)中，與其他相同領(lǐng)域的研究論文相比，實(shí)驗(yàn)數(shù)據(jù)量較少，而實(shí)際中網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量都比較大，未來(lái)將進(jìn)一步研究邊預(yù)測(cè)方法在大數(shù)據(jù)環(huán)境下的網(wǎng)絡(luò)應(yīng)用。cytoscape網(wǎng)絡(luò)處理分析功能在當(dāng)前時(shí)代已占據(jù)相當(dāng)重要的地位，而由于它的開(kāi)源特性，更使其有著非常大的發(fā)展前景。同樣，邊預(yù)測(cè)在網(wǎng)絡(luò)地復(fù)雜應(yīng)用中更是占據(jù)了一席之地

56、。隨著時(shí)代發(fā)展，這兩者必能更好的結(jié)合。屆時(shí)，預(yù)測(cè)算法將非常完善，所用預(yù)測(cè)指標(biāo)也必將是各類指標(biāo)的完美結(jié)合。最終，cytoscape將能夠完美的展現(xiàn)適用于各類環(huán)境且功能強(qiáng)大、可信度高的邊預(yù)測(cè)功能。參考文獻(xiàn)1 呂琳媛，周濤.鏈路預(yù)測(cè)m.北京：.高等教育出版社，2013.2 劉軍.社會(huì)網(wǎng)絡(luò)分析導(dǎo)論m.北京：社會(huì)科學(xué)文獻(xiàn)出版社，2004.3 王志平，王眾托.超網(wǎng)絡(luò)理論及其應(yīng)用m.北京：科學(xué)出版社，2008.4 呂琳媛.復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)j.電子科技大學(xué)學(xué)報(bào).2010，39(5)：651-661.5 王林，商超.無(wú)標(biāo)度網(wǎng)絡(luò)中的鏈路預(yù)測(cè)問(wèn)題研究j.計(jì)算機(jī)工程，2012，38(3)：67-84.6 滕兆明.多維

57、社會(huì)網(wǎng)絡(luò)中鏈路預(yù)測(cè)方法研究j.計(jì)算機(jī)應(yīng)用與軟件，2011，28(9)：9-21.7 史定華.無(wú)標(biāo)度網(wǎng)絡(luò)：基礎(chǔ)理論和應(yīng)用研究j.電子科技大學(xué)學(xué)報(bào)，2010，39(5)：644-650. 8 katz l. a new status index derived from sociometric indexj. psychometrika，1953,18(1)：39-43.9 hanely j a，mcneil b j. the meaning and use of the area under a receiver operating characteristic (roc) curvej. radiology，1983，143：29-36.10 adamic l a，adar e. friend and neighbors on the webj. social networks，2003，25(3)：211-2