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

何 艷, 趙曉婷, 于云莉

?

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

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

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

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

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

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

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

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

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

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

S=()∩() (1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3　結(jié)語

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

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

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

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

2016-04-18;收到修改稿時間:2016-06-01

[10.15888/j.cnki.csa.005554]