何 艷, 趙曉婷, 于云莉

?

復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)相似性算法及其在癲癇病輔助診斷的應(yīng)用①

何 艷1, 趙曉婷1, 于云莉2

1(貴州醫(yī)科大學(xué)生物與工程學(xué)院, 貴陽 550004)2(貴州醫(yī)科大學(xué)附屬醫(yī)院神經(jīng)內(nèi)科, 貴陽 550004)

節(jié)點(diǎn)相似性分析是鏈路預(yù)測(cè)和社團(tuán)挖掘中的重要部分. 引入CN(Common Neighbor, 共同鄰居)算法、RA(Resource Allocation, 資源分配)算法、AA(Adamic-Adar)算法、Sorenson算法等四種節(jié)點(diǎn)相似性算法作用于真實(shí)網(wǎng)絡(luò)以及仿真網(wǎng)絡(luò)(即小世界網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò))網(wǎng)絡(luò), 計(jì)算AUC(Area Under the Curve, 曲線下面積)曲線從而比較算法的預(yù)測(cè)準(zhǔn)確性, 結(jié)果表明RA算法的預(yù)測(cè)準(zhǔn)確性優(yōu)于其他三種算法. 隨后將四種算法用于分析8例全身性癲癇患者腦電數(shù)據(jù)功能連接網(wǎng)絡(luò), 結(jié)果發(fā)現(xiàn)RA算法預(yù)測(cè)準(zhǔn)確性最佳, 通過RA算法能確定最大節(jié)點(diǎn)相似度組成的節(jié)點(diǎn)簇, 為量化大腦功能狀態(tài)提供客觀指標(biāo), 未來可以將該方法用于臨床輔助診斷.

復(fù)雜網(wǎng)絡(luò); 節(jié)點(diǎn)相似性; 鏈路預(yù)測(cè); 癲癇

大腦是一個(gè)復(fù)雜系統(tǒng), 其信息傳遞和認(rèn)知功能實(shí)現(xiàn)依賴于大腦中的神經(jīng)電活動(dòng). 已知大腦電活動(dòng)其時(shí)空分辨率隨記錄手段而變化, 但總體呈現(xiàn)出高維度和非平穩(wěn)的特點(diǎn). 多通道電極記錄能盡可能地捕捉大腦電活動(dòng)的空間分布特征. 在癲癇疾病中, 患者癲癇發(fā)作時(shí)往往伴隨著神經(jīng)集群的陣發(fā)性放電異常. 隨著癲癇發(fā)作次數(shù)的增加, 癲癇患者大腦認(rèn)知功能也會(huì)受到損傷, 可能表現(xiàn)出學(xué)習(xí)記憶能力減退或衰弱. 目前國內(nèi)約1000萬癲癇患者, 一般假設(shè)癲癇患者大腦回路特性發(fā)生改變, 進(jìn)而引發(fā)功能異常, 臨床上通過長(zhǎng)程腦電檢測(cè)和顱內(nèi)腦電記錄信號(hào)對(duì)癲癇發(fā)作相關(guān)的病灶區(qū)域進(jìn)行定位. 由于癲癇疾病病理機(jī)制異常復(fù)雜, 多種神經(jīng)遞質(zhì)和神經(jīng)受體參與神經(jīng)電活動(dòng), 典型的癲癇發(fā)作如何對(duì)神經(jīng)回路發(fā)生影響目前還沒有確切的結(jié)論; 此外, 已知大腦靜息態(tài)功能網(wǎng)絡(luò)對(duì)維持大腦反應(yīng)臨界性從而對(duì)外界刺激產(chǎn)生快速響應(yīng)具有重要作用, 通過研究大腦靜息態(tài)功能網(wǎng)絡(luò)連接特征從而對(duì)大腦狀態(tài)進(jìn)行客觀評(píng)價(jià)將有利于臨床輔助診斷與療效估計(jì).

復(fù)雜網(wǎng)絡(luò)是一種簡(jiǎn)單高效的描述方法, 網(wǎng)絡(luò)節(jié)點(diǎn)為記錄電極位點(diǎn), 網(wǎng)絡(luò)連接邊為不同大腦區(qū)域的相互作用估計(jì), 基于復(fù)雜網(wǎng)絡(luò)的大腦神經(jīng)電活動(dòng)分析方法能從系統(tǒng)角度量化大腦功能狀態(tài).

復(fù)雜網(wǎng)絡(luò)是刻畫復(fù)雜系統(tǒng)的有效方法, 從1998年Watts和Strogatz提出小世界網(wǎng)絡(luò)的概念以后, 復(fù)雜網(wǎng)絡(luò)受到學(xué)者的廣泛關(guān)注[1], 比如通訊網(wǎng)絡(luò)、互聯(lián)網(wǎng)、交通運(yùn)輸網(wǎng)等, 還有科學(xué)家合作網(wǎng)、微信朋友圈等社會(huì)網(wǎng)絡(luò). 其中團(tuán)簇發(fā)現(xiàn)以及鏈路預(yù)測(cè)[2,3]是復(fù)雜網(wǎng)絡(luò)研究的重要組成部分. 鏈路預(yù)測(cè)融合網(wǎng)絡(luò)節(jié)點(diǎn)及網(wǎng)絡(luò)結(jié)構(gòu)信息, 通過對(duì)復(fù)雜網(wǎng)絡(luò)設(shè)置不同的特征估計(jì), 如隨機(jī)分塊模型、相似性預(yù)測(cè)等預(yù)測(cè)網(wǎng)絡(luò)中的缺失邊并識(shí)別錯(cuò)誤鏈接, 有助于準(zhǔn)確高效地檢測(cè)出癲癇患者大腦復(fù)雜網(wǎng)絡(luò)的異常通路. 節(jié)點(diǎn)相似性于1998年由Lin提出, 可以通過節(jié)點(diǎn)屬性的相似性對(duì)網(wǎng)絡(luò)鏈路進(jìn)行預(yù)測(cè), 如果兩節(jié)點(diǎn)的相似度越大, 則說明這兩個(gè)節(jié)點(diǎn)可能存在某種鏈接的可能性[4,5]也就越大. Lin通過節(jié)點(diǎn)的屬性定義節(jié)點(diǎn)間相似性并以此來對(duì)鏈路進(jìn)行預(yù)測(cè). Fouss、Pirotte提出基于隨機(jī)游走的協(xié)同推薦[6], Liben-Nowell、Kleinberg等人在對(duì)科學(xué)家網(wǎng)絡(luò)進(jìn)行分析, 發(fā)現(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)同時(shí)對(duì)預(yù)測(cè)有著一定影響, 并提出新的相似性定義[7]及基于網(wǎng)絡(luò)拓?fù)涞念A(yù)測(cè)方法優(yōu)于隨機(jī)的預(yù)測(cè)方法. 局部路徑指數(shù)、全局隨機(jī)游走指數(shù)、協(xié)同過濾預(yù)測(cè)方法均取得了較好的鏈路預(yù)測(cè)效果. 2008年, Newman在《自然》上的論文中又提出了基于網(wǎng)絡(luò)層次結(jié)構(gòu)的預(yù)測(cè)方法[8]. 節(jié)點(diǎn)和邊是構(gòu)成復(fù)雜網(wǎng)絡(luò)的兩個(gè)重要因素, 網(wǎng)絡(luò)結(jié)構(gòu)特征和網(wǎng)絡(luò)性質(zhì)是復(fù)雜網(wǎng)絡(luò)研究的重要組成部分[9-13]. 節(jié)點(diǎn)度的大小表示此節(jié)點(diǎn)在網(wǎng)絡(luò)中的地位的重要性, 兩節(jié)點(diǎn)之間的聯(lián)系可以用節(jié)點(diǎn)間的最短距離描述.

在傳統(tǒng)計(jì)算節(jié)點(diǎn)相似性算法的過程中主要考慮節(jié)點(diǎn)的共同鄰居和節(jié)點(diǎn)的度, 通過這些算法對(duì)兩節(jié)點(diǎn)相似度的計(jì)算, 判斷這兩個(gè)節(jié)點(diǎn)之間存在鏈接的可能性大小. 在基于節(jié)點(diǎn)相似性的預(yù)測(cè)算法中, 如果兩節(jié)點(diǎn)的相似值越大, 則被認(rèn)為兩節(jié)點(diǎn)存在鏈接的可能性就越大. 比如, 現(xiàn)在大多數(shù)人都在用的社交工具QQ, 如果兩個(gè)陌生人之間存在的共同好友越多, 那么他們就被認(rèn)為相似, 則他(她)們成為朋友的幾率也越大. 基于節(jié)點(diǎn)屬性(主要為共同鄰居及共同鄰居的節(jié)點(diǎn)度)的節(jié)點(diǎn)相似性方法計(jì)算復(fù)雜度小, 公式簡(jiǎn)單, 速度快, 如CN算法; AA 算法又被稱為頻率加權(quán)共同鄰居算法, 是將不尋常的特征賦予更多權(quán)重, 即稀有特征蘊(yùn)含更多信息, 該算法假設(shè)一個(gè)朋友較少的人可能更傾向于將他的一對(duì)朋友相互介紹; Sorensen指標(biāo)除了考慮共同鄰居的規(guī)模, 同時(shí)假設(shè)低節(jié)點(diǎn)度的共同鄰居節(jié)點(diǎn)有更高連接可能性; RA算法來自網(wǎng)絡(luò)中的資源配置理論[13], 節(jié)點(diǎn)對(duì)之間可以通過共同鄰居傳遞信息, 假設(shè)每個(gè)傳遞者均有一個(gè)資源單元且在所有鄰居中平均分配, 節(jié)點(diǎn)對(duì)之間傳遞并被接收的資源數(shù)量被定義為節(jié)點(diǎn)對(duì)之間的相似性, 與此同時(shí)RA算法考慮所有排序結(jié)果, 并引入次臨近鄰居信息度量節(jié)點(diǎn)節(jié)點(diǎn)相似性. 不同的預(yù)測(cè)算法的表現(xiàn)與網(wǎng)絡(luò)結(jié)構(gòu)信息相關(guān), 本文將引入CN、RA、AA、Sorenson等四種相似性算法作用于真實(shí)復(fù)雜網(wǎng)絡(luò)、仿真網(wǎng)絡(luò)及癲癇患者腦電復(fù)雜網(wǎng)絡(luò), 為揭示癲癇患者大腦功能連接異常通路提供技術(shù)支持.

1　節(jié)點(diǎn)相似性算法描述

CN算法是基于局部信息中最簡(jiǎn)單的相似性算法, 即為共同鄰居算法(Common Neighbors)的英文縮寫. 表示的是如果兩個(gè)節(jié)點(diǎn)的共同鄰居數(shù)越多, 則這兩個(gè)節(jié)點(diǎn)越相似. 共同鄰居CN算法定義為: 對(duì)于網(wǎng)絡(luò)中的節(jié)點(diǎn), 定義的鄰居集合為(), 那么兩個(gè)節(jié)點(diǎn)和的節(jié)點(diǎn)相似性S就定義為它們的共同鄰居數(shù)量, 公式即為:

S=()∩() (1)

以下舉一個(gè)簡(jiǎn)單的例子來理解CN算法, 網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示.

圖1中總共包含4個(gè)節(jié)點(diǎn), 根據(jù)網(wǎng)絡(luò)的連接情況, 我們可以得到節(jié)點(diǎn)2和節(jié)點(diǎn)4的共同鄰居只有1個(gè), 那就是節(jié)點(diǎn)1, 所以得到節(jié)點(diǎn)2和節(jié)點(diǎn)4的相似性為1, 即為S{2,4}=1.

與CN算法不同, RA算法考慮的是共同鄰居節(jié)點(diǎn)的度, 而不是共同鄰居. 由于受到資源分配的啟發(fā), 周濤等人提出了資源分配這一相似性指標(biāo)[13]. 網(wǎng)絡(luò)中沒有直接相連的兩個(gè)節(jié)點(diǎn), 從節(jié)點(diǎn)v到節(jié)點(diǎn)v, 這一傳遞過程中作為媒介的就是共同鄰居, 通過共同鄰居這一“中間人”, 可以從v中傳遞一些資源到v. 在算法中, 每個(gè)媒介都有一個(gè)單位的資源并且將其平均分配傳給它的鄰居.

其節(jié)點(diǎn)相似性定義為:

圖2 示例網(wǎng)絡(luò)圖

在節(jié)點(diǎn)相似性的算法中, 考慮節(jié)點(diǎn)共同鄰居的節(jié)點(diǎn)的度的影響, 著名的有Adamic-Adar算法, 即是AA算法, 它的主要思想為度小的節(jié)點(diǎn)的貢獻(xiàn)度大于度大的節(jié)點(diǎn)的貢獻(xiàn)度. 比如在微博中關(guān)注度非常高的人, 他們要么是某些領(lǐng)域的專家, 要么是明星, 因此關(guān)注他們的那些人很有可能并沒有什么相同的興趣愛好, 共同點(diǎn); 相反, 如果是一位粉絲很少的人, 當(dāng)有兩個(gè)人同時(shí)關(guān)注了他, 那則說明這兩個(gè)人很有可能具有相同的愛好, 共同的志趣. 在網(wǎng)絡(luò)中則表現(xiàn)為這兩個(gè)節(jié)點(diǎn)存在某種鏈接的可能性很大.

對(duì)于AA算法的定義為: 對(duì)于網(wǎng)絡(luò)中節(jié)點(diǎn), 定義的度為()=() , 該算法是在共同鄰居算法的基礎(chǔ)上賦與其權(quán)重, 節(jié)點(diǎn)和的節(jié)點(diǎn)相似性定義為:

用AA算法計(jì)算圖2所示網(wǎng)絡(luò)節(jié)點(diǎn)相似性, 同樣計(jì)算節(jié)點(diǎn)3與節(jié)點(diǎn)5的相似值, 結(jié)果如下:

AA算法和RA算法都是賦予共同鄰居節(jié)點(diǎn)權(quán)重, 而它們的最大的區(qū)別在于, 賦予共同鄰居節(jié)點(diǎn)權(quán)重的方式不同, AA算法是以的形式遞減, RA算法以形式遞減.

Sorenson算法與前三種節(jié)點(diǎn)相似性算法相比, 它不僅受共同鄰居的影響, 同時(shí)也受到節(jié)點(diǎn)的度的影響. 此算法一般用于生態(tài)學(xué)數(shù)據(jù)的研究. 其相似性的值的計(jì)算方法為共同鄰居數(shù)目的兩倍與這兩個(gè)節(jié)點(diǎn)的度之和的比值, 定義為:

2　節(jié)點(diǎn)相似性分析結(jié)果

2.1 數(shù)據(jù)預(yù)處理

首先將網(wǎng)絡(luò)隨機(jī)劃分成訓(xùn)練集和測(cè)試集. 即將一個(gè)完整的網(wǎng)絡(luò)劃分成兩個(gè)部分, 其中一部分作為訓(xùn)練集, 剩余部分為測(cè)試集, 比較CN、RA、AA、Sorenson四種算法的預(yù)測(cè)效果, 通過測(cè)試集得到預(yù)測(cè)能力的結(jié)果. 針對(duì)一個(gè)無向網(wǎng)絡(luò)G(V, E), 給定一種預(yù)測(cè)算法并運(yùn)用這種算法為每對(duì)沒有連邊的節(jié)點(diǎn)賦予一個(gè)值, 所賦予的這個(gè)值與這兩個(gè)節(jié)點(diǎn)的連接概率正相關(guān). 然后將所有沒有連接的節(jié)點(diǎn)的對(duì)按照值從大到小進(jìn)行排列, 排在前面的說明兩個(gè)節(jié)點(diǎn)相互連接的可能性越大. 若給出一個(gè)完整網(wǎng)絡(luò), 此網(wǎng)絡(luò)包含有13個(gè)節(jié)點(diǎn), 19條邊, 該網(wǎng)絡(luò)的全集為78條邊, 說明有59條邊是不存在的. 隨機(jī)選出這19條邊中的4條作為測(cè)試集, 剩下的15條邊作為訓(xùn)練集. 給出某種預(yù)測(cè)算法, 此算法賦予63條未知邊一個(gè)值(包括4條測(cè)試邊跟59條不存在的邊), 然后將這63條邊的分?jǐn)?shù)值按照從大到小的順序進(jìn)行排序, 如果能使4條測(cè)試邊盡可能多的排列在前面, 則說明算法的預(yù)測(cè)準(zhǔn)確性越高.

引入AUC作為衡量預(yù)測(cè)準(zhǔn)確性的指標(biāo), AUC可以理解成在測(cè)試集中隨機(jī)選取一條邊的分?jǐn)?shù)值比隨機(jī)從不存在的邊選取一條邊的分?jǐn)?shù)值要高的概率. 其中, 測(cè)試邊與不存在的邊的集合為未知邊. 每次從測(cè)試邊中隨機(jī)抽取一條邊, 然后從不存在的邊中隨機(jī)抽取一條邊, 比較兩個(gè)邊的分?jǐn)?shù)值, 如果測(cè)試邊的分?jǐn)?shù)值大于不存在的邊的分?jǐn)?shù)值, 那么就加1分, 要是這兩個(gè)分?jǐn)?shù)值相等就加0.5分. AUC定義如下:

2.2 真實(shí)網(wǎng)絡(luò)分析結(jié)果

四個(gè)真實(shí)網(wǎng)絡(luò)分別為線蟲代謝網(wǎng)絡(luò)(Metabolic), 科學(xué)家合作網(wǎng)(NetScience)、爵士音樂家合作網(wǎng)(Jazz)以及美國航空網(wǎng)絡(luò)(USAir), 其基本統(tǒng)計(jì)特征如表1所示. 分別取不同的訓(xùn)練集比例, 運(yùn)用CN、RA、AA、Sorenson四種相似性算法, 計(jì)算出每個(gè)訓(xùn)練集比例對(duì)應(yīng)的AUC值, 繪制曲線圖.

表1 真實(shí)網(wǎng)絡(luò)基本統(tǒng)計(jì)特征

由于訓(xùn)練集的取值范圍受到網(wǎng)絡(luò)的限制, 不同網(wǎng)絡(luò)訓(xùn)練集的取值范圍不同. 通過對(duì)線蟲的新陳代謝網(wǎng)絡(luò)數(shù)據(jù)的處理, 得到CN、RA、AA、Sorenson四種相似性算法在線蟲的代謝網(wǎng)絡(luò)中AUC曲線圖3所示.

圖3 線蟲代謝網(wǎng)絡(luò)鏈路預(yù)測(cè)的AUC曲線圖

由此可以看出, 在線蟲的代謝網(wǎng)絡(luò)中, CN、RA、AA、Sorenson四種相似性算法的預(yù)測(cè)效果還是存在比較明顯的差異的, AUC的值越大說明預(yù)測(cè)準(zhǔn)確性越高, RA算法優(yōu)于其他算法.

利用科學(xué)家合作網(wǎng)(NetScience)、爵士音樂家合作網(wǎng)(Jazz)、美國航空網(wǎng)絡(luò)(USAir)三個(gè)真實(shí)網(wǎng)絡(luò)檢驗(yàn)上述四種算法, 三個(gè)網(wǎng)絡(luò)的性質(zhì)基本都不一樣, 其中, 科學(xué)家合作網(wǎng)是一個(gè)無向加權(quán)網(wǎng)絡(luò), 而爵士音樂家合作網(wǎng)是一個(gè)無向無權(quán)的網(wǎng)絡(luò). 依據(jù)AUC曲線圖的變化趨勢(shì), 隨著訓(xùn)練集樣本比例的上升, 結(jié)果發(fā)現(xiàn)當(dāng)曲線趨于平緩時(shí), RA算法預(yù)測(cè)精確度明顯高于其他三種算法.

2.3 仿真網(wǎng)絡(luò)分析結(jié)果

由于國際標(biāo)準(zhǔn)10-20腦電信號(hào)采集系統(tǒng)一般為21通道左右, 網(wǎng)絡(luò)中節(jié)點(diǎn)和連邊數(shù)目較小, 因此引入兩個(gè)仿真網(wǎng)絡(luò), 其中一個(gè)為WS小世界網(wǎng)絡(luò)、另外一個(gè)為BA無標(biāo)度網(wǎng)絡(luò), 節(jié)點(diǎn)的數(shù)目分別為20和30, 根據(jù)AUC曲線圖分析, CN、AA算法的預(yù)測(cè)精度基本相同, 最佳的仍然是RA算法. 不管是在復(fù)雜的真實(shí)網(wǎng)絡(luò)中還是在仿真的只有30個(gè)節(jié)點(diǎn)的BA網(wǎng)絡(luò)(如圖4所示)中, RA算法都比其他三種算法具有優(yōu)勢(shì).

2.4 癲癇患者大腦功能連接網(wǎng)絡(luò)分析結(jié)果

癲癇是一種常見神經(jīng)系統(tǒng)疾病, 臨床認(rèn)為大腦神經(jīng)元異常放電導(dǎo)致癲癇發(fā)作. 給患者生活帶來極大不便, 嚴(yán)重的甚至影響到患者的心理健康, 多通道腦電信號(hào)是臨床癲癇疾病篩查和診斷的重要手段. 本文中的腦電數(shù)據(jù)來自于8例全身性癲癇患者, 其男/女比例為5/3, 年齡為8.50±4.01, 腦電采集設(shè)備為Nicolet長(zhǎng)程視頻腦電采集系統(tǒng). 原始腦電信號(hào)記錄時(shí)間為3小時(shí)至24小時(shí)不等, 其不同頻率波段腦電信號(hào)組成的復(fù)雜網(wǎng)絡(luò)提取來自于其相位鎖定值[14]. 以alpha(8-13Hz)波段腦電信號(hào)構(gòu)成的復(fù)雜網(wǎng)絡(luò)為研究對(duì)象, 結(jié)果發(fā)現(xiàn)RA算法優(yōu)于其他3種算法, 如圖5所示. 在算法檢驗(yàn)中, 由于對(duì)癲癇患者大腦功能性連接矩陣進(jìn)行了稀疏化處理[15], 網(wǎng)絡(luò)節(jié)點(diǎn)及連接邊數(shù)目較少, 因此測(cè)試集比例需要在70%及以上.

圖5 癲癇患者腦電網(wǎng)絡(luò)AUC曲線圖

隨后利用RA算法分析癲癇患者腦電特征, 圖6顯示了某一例癲癇患者腦電信號(hào)alpha波段組成復(fù)雜網(wǎng)絡(luò)的相似度矩陣. 該網(wǎng)絡(luò)總共含有19個(gè)節(jié)點(diǎn)(1至19分別對(duì)應(yīng)于Fp1, Fp2, F7, F3, Fz, F4, F8, T3, C3, Cz, C4, T4, T5, P3, Pz, P4, T6, O1, O2), 圖中矩陣的行與列分別表示節(jié)點(diǎn)V1到節(jié)點(diǎn)V19, 矩陣?yán)锏拿恳粋€(gè)元素代表兩節(jié)點(diǎn)的相似度. 若相似值越大則說明兩個(gè)節(jié)點(diǎn)越有可能產(chǎn)生鏈接. 然而, 每個(gè)節(jié)點(diǎn)都有一個(gè)最大相似度節(jié)點(diǎn), 而這個(gè)最大相似度節(jié)點(diǎn)對(duì)此節(jié)點(diǎn)的影響力也是最大的. 將9例癲癇患者腦電信號(hào)中每個(gè)記錄節(jié)點(diǎn)的最大相似度節(jié)點(diǎn)找出來(由于部分患者腦電信號(hào)僅采集了18通道信號(hào), 因此以18為網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)), 結(jié)果如表2和表3所示, 其中列出了每個(gè)節(jié)點(diǎn)的最大相似度節(jié)點(diǎn)以及對(duì)應(yīng)的相似值. 圖7顯示了基于RA算法的某癲癇患者腦電信號(hào)alpha波段節(jié)點(diǎn)簇示意圖.

結(jié)果發(fā)現(xiàn), 在alpha波段組成的復(fù)雜網(wǎng)絡(luò)中, 樣本1形成4個(gè)節(jié)點(diǎn)簇(如圖7所示), 分別為13(10) (其中13代表節(jié)點(diǎn)位點(diǎn), 10代表節(jié)點(diǎn)位點(diǎn)連接的節(jié)點(diǎn)個(gè)數(shù)), 10(6), 9; 樣本8則形成6個(gè)簇, 分別為11(2), 13(3), 17(5), 15(5), 9(2), 1; 而樣本2至樣本7則分別形成4至8個(gè)不同的簇. 在delta(0.5-4Hz) 波段組成的復(fù)雜網(wǎng)絡(luò), 樣本8形成13, 3, 14(4), 11(2), 18(2), 15(2), 1(2), 6, 9, 17, 8等11個(gè)簇, 而樣本2則形成18(13) 13(3) 10 15等4個(gè)子簇, 其余樣本分別形成5至9個(gè)子簇.

圖7 樣本1中alpha波段基于RA算法的節(jié)點(diǎn)簇示意圖

表2 癲癇患者腦電alpha 波段所有節(jié)點(diǎn)對(duì)應(yīng)的最大相似度節(jié)點(diǎn)

表3 癲癇患者腦電delta 波段所有節(jié)點(diǎn)對(duì)應(yīng)的最大相似度節(jié)點(diǎn)

3　結(jié)語

本文以復(fù)雜網(wǎng)絡(luò)的基本特征出發(fā), 研究其節(jié)點(diǎn)的相似性, 基于節(jié)點(diǎn)的相似性算法對(duì)癲癇患者復(fù)雜網(wǎng)絡(luò)鏈路特征進(jìn)行分析. 自從1998年Watts和Strogatz提出小世界網(wǎng)絡(luò)的概念后[16], 有許多研究學(xué)者們開始利用小世界這一模型展開對(duì)大腦網(wǎng)絡(luò)的研究. 此外, 張方風(fēng)等人[17]也利用網(wǎng)絡(luò)建構(gòu)分析方法對(duì)手指活動(dòng)的大腦功能連接特征進(jìn)行了分析, 結(jié)果表明該網(wǎng)絡(luò)具有小世界的特性. 基于復(fù)雜網(wǎng)絡(luò)的研究有助于量化分析大腦特征.

本文以復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)的相似性為基本特征, 引入CN、RA、AA、Sorenson四種節(jié)點(diǎn)相似性算法, 分別在線蟲的新陳代謝網(wǎng)絡(luò)(Metabolic)、科學(xué)家合作網(wǎng)(NetScience)、爵士音樂家合作網(wǎng)(Jazz)、美國航空網(wǎng)絡(luò)(USAir)四個(gè)真實(shí)系統(tǒng)中實(shí)現(xiàn)了預(yù)測(cè)實(shí)驗(yàn), 根據(jù)AUC的值評(píng)判預(yù)測(cè)的準(zhǔn)確性, 發(fā)現(xiàn)RA算法的預(yù)測(cè)效果優(yōu)于其他算法; 同時(shí)在仿真的小世界與無標(biāo)度網(wǎng)絡(luò)中也進(jìn)行了預(yù)測(cè)實(shí)驗(yàn), 結(jié)果也發(fā)現(xiàn)RA算法預(yù)測(cè)準(zhǔn)確性比較高. 隨后利用RA算法分析8例全身性癲癇患者腦電信號(hào), 發(fā)現(xiàn)該方法能較好刻畫由節(jié)點(diǎn)相似度組成的節(jié)點(diǎn)對(duì)子簇; 對(duì)同一樣本而言, 該方法也能刻畫不同頻率波段(delta, alpha)組成的復(fù)雜網(wǎng)絡(luò)其節(jié)點(diǎn)相似度組成的子簇. 結(jié)果初步表明基于節(jié)點(diǎn)相似度的分析方法能量化并可視化癲癇患者腦電信號(hào)功能連接特征.

不同節(jié)點(diǎn)相似度算法的預(yù)測(cè)能力可以顯示網(wǎng)絡(luò)潛在的結(jié)構(gòu)信息, 網(wǎng)絡(luò)結(jié)構(gòu)特征和節(jié)點(diǎn)屬性將影響網(wǎng)絡(luò)中不同鏈路預(yù)測(cè)的算法表現(xiàn). 本文中的四種算法都是基于局部信息的節(jié)點(diǎn)相似性度量技術(shù), 相對(duì)基于全局信息度量指標(biāo), 這些算法復(fù)雜度低, 計(jì)算速度快, 但預(yù)測(cè)精度較低. CN算法公式簡(jiǎn)單, 復(fù)雜度低, 但容易被節(jié)點(diǎn)度異質(zhì)性影響. Sorenson算法同時(shí)考慮共同鄰居個(gè)數(shù)和節(jié)點(diǎn)對(duì)的節(jié)點(diǎn)度, 僅從網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)屬性出發(fā), 難以與物理意義關(guān)聯(lián). RA和AA算法均抑制高節(jié)點(diǎn)度共同鄰居的作用力, 當(dāng)節(jié)點(diǎn)度小時(shí)二者表現(xiàn)類似, 當(dāng)節(jié)點(diǎn)度大時(shí)則RA算法優(yōu)于AA算法. RA描述的是網(wǎng)絡(luò)傳輸能力和連接性的非線性關(guān)系, 引入了次鄰近節(jié)點(diǎn)信息描述節(jié)點(diǎn)相似性, 有效消除了由局部相似性度量引發(fā)的退化態(tài), 這可能是RA算法優(yōu)于其他算法的潛在原因(補(bǔ)充節(jié)點(diǎn)相似性算法CN、RA、AA、Sorenson展開全面的對(duì)比, 包括算法描述、特點(diǎn)、算法復(fù)雜度等).

癲癇病是一種嚴(yán)重危害患者生命健康的惡性疾病, 且原發(fā)性癲癇患者大多為兒童, 由于其病理機(jī)制復(fù)雜, 多種神經(jīng)遞質(zhì)和生理因素都可能影響疾病進(jìn)程, 臨床診斷和治療主要依賴于醫(yī)生的經(jīng)驗(yàn), 缺乏準(zhǔn)確的量化指標(biāo). 基于節(jié)點(diǎn)相似性的癲癇患者腦網(wǎng)絡(luò)分析不僅有效量化其大腦特征, 還有助于分析和預(yù)測(cè)癲癇患者大腦中的異常連接及相關(guān)腦區(qū)病例變化. 未來可以引入大規(guī)模樣本患者及對(duì)照組數(shù)據(jù), 在本文節(jié)點(diǎn)相似性及其相似值的基礎(chǔ)上提煉關(guān)鍵指標(biāo), 為臨床輔助診斷與病人腦功能狀態(tài)量化估計(jì)提供技術(shù)支持.

1 Du F, Xuan Q, Wu TJ. Empirical analysis of attention behaviors in online social networks. International Journal of Modern Physics C, 2010, 21(7): 955–971.

2 呂琳媛.復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè).電子科技大學(xué)學(xué)報(bào),2010,39(5): 651–661.

3 Lu L, Zhou T. Link prediction in complex networks: A survey. Physic A: Statistical Mechanics and its Applications, 2011, 390(6): 1150–1170.

4 Lv LY, Zhou T. Link prediction in weighted networks: The role of weak ties. EPL, 2010, 89(18001): 1–6.

5 Getoor L, Diehl CP. Link mining: A survey. ACM SIGKDD Explorations Newsletter, 2005, 7(2): 3–12.

6 Yamada T, Bork P. Evolution of biomolecular networks -lesons from metabolic and protein interactions. Nature, 2009, 10(11): 791–803.

7 Liben-Nowell D, Kleinberg J. The link prediction problem forsocial networks. Proc. of the 12th International Conference on Information and Knowledge Management (CIKM). 2003. 556–559.

8 Clauset A, Moore C, Newman MEJ. Hierarchical structure and the prediction of missing links in networks. Nature, 2008, 453(7191): 98–101.

9 Wagner A, Fell DA. The small world inside large metabolic networks. Proc. of the Royal Social of London. Series B: Biological Sciences, 2001, 268(1478): 1803–1810.

10 Maslov S, Sneppen K. Specifity and stability in topology of protein networks. Science, 2002, 296(5569): 910–913.

11 Latora V, Marchiori M. Efficient behavior of small-world networks. Physical Review Letters, 2001, 87(19): 198701.

12 Milgram S. The small world problem. Psychology Today, 1967, 2(1): 60–67.

13 Zhou T, Lu L, Zhang YC. Predicting missing links via local information. The European Physical Journal B-Condensed Matter and Complex Systems, 2009, 71(4): 623–630.

14 Yan H, et al. Frequency dependent network flexibility analysis in epileptic brain based on phase locking value and resilience test. 2014 10th International Conference on Natural Computation(ICNC). Xiamen. 2014. 25–29.

15 孫俊峰,洪祥飛,童善保.復(fù)雜腦網(wǎng)絡(luò)研究進(jìn)展-結(jié)構(gòu)、功能、計(jì)算與應(yīng)用.復(fù)雜系統(tǒng)與復(fù)雜性科學(xué),2010,4:74–90.

16 Watts DJ, Strogatz SH. Collective dynamics of “small- world” networks. Nature, 1998, 393: 440–442.

17 張方風(fēng),陳春輝,姜璐.數(shù)字背誦過程的大腦功能網(wǎng)絡(luò).中國醫(yī)學(xué)物理學(xué)雜志,2006,23(6):419–422.

Node Similarity Algorithm on Complex Network and Its Application in Epilepsy Auxiary Diagnosis

HE Yan1, ZHAO Xiao-Ting1, YU Yun-Li2

1(School of Biology & Engineering, Guizhou Medical University, Guiyang 550004, China)2(Department of Neurology, Affiliated Hospital of Guizhou Medical University, Guiyang 550004, China)

The investigation of node similarity is an important component in link prediction and community detection. In this paper, four kinds of algorithms including common neighbor (CN), resource allocation (RA), Adamic-Adar (AA) and Sorenson are introduced into various kinds of real networks and two kinds of simulation networks comprised of small world network and scale free network. The Area Under the Curve (AUC) is computed to compare their predictive accuracy. It’s found that RA performs much better than the other three kinds of algorithms. Then four algorithms are adopted in functional connectivity networks that characterize electroencephalograph (EEG) recordings from eight patients with generalized epilepsy. It’s demonstrated that RA performs best from the point of prediction accuracy. According to RA technique, clusters could be determined from nodes that own maximum similarity which provides an objective index for quantifying brain condition, and this might be applied for clinical auxiliary diagnosis in the future.

complex network; node similarity; link prediction; epilepsy

國家自然科學(xué)基金(81460206);貴州醫(yī)科大學(xué)博士啟動(dòng)基金(J2014[003])

2016-04-18;收到修改稿時(shí)間:2016-06-01

[10.15888/j.cnki.csa.005554]