復雜網絡節點相似性算法及其在癲癇病輔助診斷的應用①

何 艷, 趙曉婷, 于云莉

?

復雜網絡節點相似性算法及其在癲癇病輔助診斷的應用①

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

1(貴州醫科大學生物與工程學院, 貴陽 550004)2(貴州醫科大學附屬醫院神經內科, 貴陽 550004)

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

復雜網絡; 節點相似性; 鏈路預測; 癲癇

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

復雜網絡是一種簡單高效的描述方法, 網絡節點為記錄電極位點, 網絡連接邊為不同大腦區域的相互作用估計, 基于復雜網絡的大腦神經電活動分析方法能從系統角度量化大腦功能狀態.

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

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

1　節點相似性算法描述

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

S=()∩() (1)

以下舉一個簡單的例子來理解CN算法, 網絡結構如圖1所示.

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

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

其節點相似性定義為:

圖2 示例網絡圖

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

對于AA算法的定義為: 對于網絡中節點, 定義的度為()=() , 該算法是在共同鄰居算法的基礎上賦與其權重, 節點和的節點相似性定義為:

用AA算法計算圖2所示網絡節點相似性, 同樣計算節點3與節點5的相似值, 結果如下:

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

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

2　節點相似性分析結果

2.1 數據預處理

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

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

2.2 真實網絡分析結果

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

表1 真實網絡基本統計特征

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

圖3 線蟲代謝網絡鏈路預測的AUC曲線圖

由此可以看出, 在線蟲的代謝網絡中, CN、RA、AA、Sorenson四種相似性算法的預測效果還是存在比較明顯的差異的, AUC的值越大說明預測準確性越高, RA算法優于其他算法.

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

2.3 仿真網絡分析結果

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

2.4 癲癇患者大腦功能連接網絡分析結果

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

圖5 癲癇患者腦電網絡AUC曲線圖

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

結果發現, 在alpha波段組成的復雜網絡中, 樣本1形成4個節點簇(如圖7所示), 分別為13(10) (其中13代表節點位點, 10代表節點位點連接的節點個數), 10(6), 9; 樣本8則形成6個簇, 分別為11(2), 13(3), 17(5), 15(5), 9(2), 1; 而樣本2至樣本7則分別形成4至8個不同的簇. 在delta(0.5-4Hz) 波段組成的復雜網絡, 樣本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算法的節點簇示意圖

表2 癲癇患者腦電alpha 波段所有節點對應的最大相似度節點

表3 癲癇患者腦電delta 波段所有節點對應的最大相似度節點

3　結語

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

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

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

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

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 呂琳媛.復雜網絡鏈路預測.電子科技大學學報,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 孫俊峰,洪祥飛,童善保.復雜腦網絡研究進展-結構、功能、計算與應用.復雜系統與復雜性科學,2010,4:74–90.

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

17 張方風,陳春輝,姜璐.數字背誦過程的大腦功能網絡.中國醫學物理學雜志,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

國家自然科學基金(81460206);貴州醫科大學博士啟動基金(J2014[003])

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

[10.15888/j.cnki.csa.005554]