基本介紹
- 中文名：關鍵節
- 外文名：Critical Seciton
- 性質：名詞
- 類別：電子工程
- 拼音：guān jiàn jié
- 套用：醫學領域
關鍵節定義,關鍵節算法,關鍵節最佳化,關鍵節排序,關鍵節求解,關鍵節套用,套用實例,關鍵節套用背景,關鍵節前景,
關鍵節定義
關鍵節在雜網路中的結構洞節點對於信息傳播具有重要作用, 現有關鍵節點排序方法多數沒有兼顧結構洞節點和其他類型的關鍵節點進行排序. 本文根據結構洞理論與關鍵節點排序相關研究選取了網路約束係數、介數中心性、等級度、效率、網路規模、PageRank值以及聚類係數7個度量指標, 將基於ListNet的排序學習方法引入到複雜網路的關鍵節點排序問題中, 融合7個度量指標, 構建了一個能夠綜合評價面向結構洞節點的關鍵節點排序方法. 採用模擬網路和實際複雜網路進行了大量實驗, 人工標準試驗結果表明本文排序方法能夠綜合考慮結構洞節點和核心節點, 關鍵節點排序與人工排序結果具有較高的一致性. SIR傳播模型評估實驗結果表明由本文選擇TOP-K節點發起的傳播能夠在較短的傳播時間內達到最大的傳播範圍. 複雜網路的研究一直備受關注, 為了解釋不同網路所具有的不同特徵, 研究焦點從網路的社團結構到網路中的關鍵節點發現。
關鍵節點對複雜網路上的信息傳播、防止傳染病的傳播和擴散等現實情境起到重大作用. 網路中關鍵節點排序問題不僅與網路拓撲結構特徵有關還應考慮到其功能特徵因素. Burt 的結構洞理論[5]認為, 在社會結構中占據結構洞位置的企業會獲得更多的競爭優勢, 從而使企業獲得累加收益, 包括信息利益和控制利益. 在信息社會中, 處於結構洞位置的成員能夠獲取更關鍵的信息, 從而影響甚至控制社會關係與信息的傳播. 如圖1所示, 該圖為網際網路上某個熱點話題的傳播圖, 圖中紅色節點為處於結構洞的節點, 社會媒體上一些熱點話題被擁有冬粉較多的藍色節點發起, 而處於邊緣地帶的結構洞節點卻帶動了將近50%的話題傳播量, 如果沒有這些處於結構洞的節點發揮作用, 話題將不會有廣泛的傳播範圍, 這說明話題在傳播過程中, 核心節點固然很重要, 但處於結構洞的節點也起到重大作用. 所以, 關鍵節點排序問題關注的焦點不能僅局限於網路中的核心節點, 也不可忽略處於結構洞位置的節點. 現有關鍵節點排序研究很少考慮結構洞節點,如何在複雜網路的關鍵節點排序問題中綜合考慮結構洞節點和其他類型的關鍵節點是一個值得深入研究的問題.近年來, 複雜網路中的關鍵節點的排序問題已經成為研究熱點. 定量的衡量網路中節點的重要程度通常會用到一些中心性度量指標, 如節點的度、接近中心性、流介數中心性, Katz 中心性等, 但是這些指標對網路的拓撲結構依賴性很強. 而Kitsak 等從新的視角提出利用K-核分解來研究網路中的關鍵節點, 該方法認為關鍵節點的重要性與其所處網路的位置有關, 將外層的節點層層剝去, 處於內層的節點即為網路中的關鍵節點. 另外, 在搜尋引擎領域, 排序問題的研究已經廣為人知, 如著名的Google網頁排名算法Pagerank, Lü 等提出的LeaderRank算法這些關鍵節點排序方法各有利弊, 於是學者們尋找綜合性的方法對網路中的關鍵節點進行評價. 於會等提出了一種多屬性決策的排序方法, 對網路中單個節點的度中心性、介數中心性等多個指標作為決策評價方案的屬性進行綜合計算, 從而對網路中關鍵節點進行排序; Hou 等考慮度、介數、K-核三個不同指標對節點重要性的影響, 採用歐拉距離公式計算三種不同指標的綜合作用得到節點的排序結果; Comin等綜合考慮介數與度的關係, 定義了一個關鍵節點排序的指標; 任卓明等提出了一種基於度與聚類係數的網路節點重要性度量方法對大規模網路的節點重要性進行有效分析; 周漩等針對節刪除法、節點收縮法和介數法的不足綜合考慮了節點效率、節點度值和相鄰接點重要度貢獻, 提出了一種利用重要度評價矩陣來確定複雜網路關鍵節點的方法通過實驗證明, 這些綜合利用度量指標的方法取得的結果均優於單個指標獲得的關鍵節點排序結果, 但是這些排序方法也沒有融入具有結構洞特徵的因素, 因而無法考慮處於結構洞位置的關鍵節點.對於複雜網路中面向結構洞的關鍵節點排序問題的研究目前不多, 一方面是由於處於結構洞位置的節點擁有獨特特徵, 這些特徵將結構洞節點與複雜網路中的核心節點區分開, 因此即使處於結構洞的關鍵節點在網路中發揮重要作用卻依然容易被忽略。
另一方面, 在複雜網路中關於結構洞的研究還不深入, 如何在複雜網路中科學的測量結構洞節點還值得探索. Burt提出的幾個定量描述結構洞的指標, 如網路約束係數(Constraint, CT)、網路有效規模(EffectiveSize, ES)、效率(Efficient,EF)、等級度(Hierarchy, HI)等; Freeman提出用介數中心性(Betweenness Centrality, BT)測量方法描述結構洞 這些指標能夠定量的刻畫結構洞的一些局部特徵. 根據相關結構洞指標, 本文提出一種能夠融合結構洞特徵與網路節點其他重要性特徵的排序方法, 從而更加全面的對網路中的關鍵節點進行綜合評價.排序學習方法是當前文本檢索領域的研究熱點, 它將機器學習方法引入到信息檢索的文檔相關性排序問題中, 充分考慮各種排序方法對最終排序結果的影響, 通過訓練學習排序參數, 將各種排序方法視為特徵, 對文檔的相關性做綜合的評估.本文將該方法引入到複雜網路中面向結構洞節點的排序問題上, 對不同的度量指標進行排序學習,最後獲得參數.排序學習方法能夠有效結合多個特徵的關鍵在於該方法能夠學習多維特徵的參數估計問題.而排序學習方法根據訓練樣本的不同可以分為三類: 基於單個樣本的Pointwise算法、基於樣本對的Pairwise算法和基於樣本佇列的Listwise算法.Pointwise算法將每個訓練數據集作為學習樣本,將分類問題轉化為單個文檔的分類和回歸問題;Pairwise算法將訓練數據集中有不同相關性標註的一對數據作為樣本, 根據這些樣本對將排序問題轉化為二值分類問題, 如套用比較廣泛的RankingSVM[26]算法; Listwise算法將訓練數據的相關性序列作為樣本, 該樣本序列與標註序列的距離作為損失函式進行學習, 這三類方法中Listwise算法的實際效果最好, 因此這種方法是排序學習領域當前的研究熱點, 而其中套用效果較好的算法是ListNet 算法[27]. 所以本文將ListNet 排序學習方法引入複雜網路多指標關鍵節點排序問題中.綜上所述, 本文將基於ListNet排序學習方法對網路中單個節點的CT, EF, ES, HT, BC, Pager-ank 值(PageRank, PR)、聚類係數(Clustering Co-efficient, CC)這7個度量指標進行融合, 綜合評價複雜網根據具有人工排序的實驗結果分析, 綜合7個度量指標評價複雜網路中的關鍵節點比單一指標評價效果更好, 驗證了相關研究闡述的集成性排序方法優於單個指標排序的結論對於大型複雜網路, 本文方法排序得到的TOP-K節點能夠在較短的時間內達到最大的傳播範圍, 在網路拓撲結構具有多樣性的情況下效果更佳, 說明本文方法選擇出的節點具有較高的傳播能力, 對於現實複雜網路中的實用性比較強.由於介數中心性計算複雜度高, 下一步工作中, 我們將最佳化本文方法, 探索利用簡單指標實現有效排序, 將本文方法運用在更大型的複雜網路關鍵節點排序上.絡中面向結構洞的節點的重要性。
關鍵節算法
關鍵節最佳化
針對感測器網路多跳通信和多對一的流量特徵，提出負載均衡的約束條件，將關鍵節點集選取問題轉化為多目標最佳化問題，提出一種基於非支配遺傳算法的關鍵節點集輪換算法。通過節點密度控制機制，從投放的節點池中選取關鍵節點集，以滿足監測區域覆蓋連通。在每輪網路工作的開始，激活不同的關鍵節點集，保證在每個時刻，有且僅有一個節點集完成對網路的充分覆蓋。仿真結果表明該算法能夠快速收斂於最優解，極大化網路關鍵節點集數目，有效延長網路的生存時間。無線感測器網路由大量集成了感測器、處理器、無線通信等模組的低功耗節點以 Ad hoc 方式構成，節點協作完成監測區域環境信息的採集、處理和轉發，可以為環境監測、工業控制和災難現場緊急救援等諸多套用提供支持。受制於感測器節點的能量有限性及其套用區域的不可達性，無線感測器網路大多通過飛機布撒等方式投放大量節點以消除覆蓋盲區。但是這種高密度的節點部署方式往往會導致共享無線信道的節點之間相互競爭，進而發生通信干擾，不僅影響數據傳輸的可靠性，而且能量開銷較大。為此，覆蓋控制問題成為感測器網路研究中的關鍵問題。立足於傳統計算機網路定義，網路覆蓋通常歸屬於系統“服務質量”範疇。當網路覆蓋低於預先定義的閾值時，表征整個網路已經不能提供正常的功能，即網路失效。密度控制是無線感測器網路覆蓋問題的一種有效解決方案。
關鍵節排序
基於 NSGA-II 的多目標最佳化關鍵節點集輪換精 銳 非 支 配 遺 傳 算 法 NSGA-II(Non-dominatedSorting Genetic Algorithm)從非劣性排序、以擁擠距代替適值共享及基於精銳策略保留優異解等三個方面對原始 NSGA算法進行改進，具有快速求解 Pareto 最優解的能力。基於 NSGA-II 進行無線感測器網路關鍵節點集選取首先需要將問題空間轉化到編碼空間。為了避免重組操作中丟失優秀解，採用了一種循環重組的方法。同時，為了避免高適值個體快速繁殖而導致早熟，本文在非支配排序的過程中引入了刪除運算元，用來刪除種群中的相同個體。
關鍵節求解
通過將多目標最佳化領域相關理論引入節點集輪換求解中，提一種基於 NSGA-II 的覆蓋節點集選取機制。充分考慮全網通信的負載均衡需求，從而儘可能利用網路剩餘節點，在節省網路能量的同時，增強了網路的健壯性。仿真實驗表明，提出的多目標最佳化覆蓋節點集輪換算法與現有的最大小限制條件的啟發式算法相比，具有更優良的性能，為以後的研究奠定了良好的基礎。
關鍵節套用
套用實例
為解決乳腺癌疾病模組挖掘方法中基因表達譜樣本數量少、數據不完整、存在噪聲和偏差的問題，提出了一種基於關鍵節點子團和局部適應度的候選疾病模組挖掘算法———KNGLF 算法。 該算法首先將候選基因與致病基因間的重疊相似性得分和功能相似性得分進行融合，通過比較融合得分與閾值，篩選出關鍵節點，並構建關鍵節點子團; 然後，基於局部適應度及不同節點對應的不同判定標準，擴展挖掘候選疾病模組; 最後，根據富集分析結果確定候選疾病基因模組。 實驗結果表明，與現有其他乳腺癌模組挖掘算法相比，KNGLF 中關鍵節點選擇算法所得平均排名較小，曲線下面積較大。 KNGLF 算法挖掘出 15 個具有較顯著生物意義的乳腺癌候選疾病模組。
關鍵節套用背景
此外，KNGLF 算法還可擴展至其他疾病候選模組。癌症是一種細胞失控增長的複雜多發疾病，在全世界範圍內已成為一個重要的公共健康問題。 在各類型癌症中，乳腺癌是全球女性最常見的惡性腫瘤，世界上絕大多數國家在過去 20 年中發病率都持續增長。 以統計生化試驗的方法來尋求疾病分子靶點進行治療，雖然取得了一定的成果，但大都以特定的基因目標為試驗對象，因而所得結果有限，且需消耗大量時間和人力物力。通過生物網路挖掘疾病功能模組，不僅能為分子靶點研究提供有效的信息，還能展示疾病基因及其產物以及它們彼此之間的協同關係，全面闡明其在複雜疾病過程中的作用機理。 目前，學者們已提出了多種基於網路的乳腺癌疾病模組挖掘方法。提出了一種基於路徑的乳腺癌核心模組挖掘方法，利用該方法雖然辨識出了一些與該疾病有關的生物標記和功能模組，但由於主要依靠基因表達譜數據，故易受表達數據缺失、冗餘和偏差以及樣本數量有限的影響，且模組構建較為簡單，沒有進行更深入的篩選。
關鍵節前景
利用已有工具從構建出的局部共表達網路中挖掘模組，然後結合差異表達基因和顯著樣本的分布特性來篩選出癌症風險模組，通過與已知癌症樣本之間的風險關係來判斷模組的疾病風險程度; 該方法仍局限於表達譜所涉及的基因，且使用統一的閾值來確定基因間連線關係，故而會導致一些弱相關性基因丟失。鑒於此，本文提出了一種新的基於關鍵節點子團和局部適應度算法來挖掘乳腺癌候選疾病模組。該算法不使用基因表達譜數據，採用融合打分策略篩選出關鍵節點並構建關鍵節點子團，藉助關鍵節點子團和局部適應度的思想進行模組挖掘，並根據富集分析來決定所挖掘模組是否為候選致病基因模組。挖掘結果及部分富集分析在致病基因集中，從 BCGB，G2SBC 和 OMIM資料庫中分別收集了 62，44 和 48 個致病基因，剔除重複數據後，獲得 138 個乳腺癌致病基因。 利用表型間相似性構建相應候選基因集，通過打分篩選，最終得到 1 935 個關鍵節點，並構建出各關鍵節點子團。 採用 KNGLF 算法挖掘候選疾病模組，套用線上工具 Go-TermFinder 進行富集分析和確認，顯著性閾值 P 默認為 0。 01，最終獲得 15 個具有一定生物學意義乳腺癌候選疾病模組。以排名第 1 的關鍵節點子團所挖掘出的台 DAVID，分別在生物過程、細胞成分和分子功能以及 KEGG 通路中進行富集條目( P < 0。 01) 分析。 從分析結果中發現，該模組的富集條目主要集中在調控過程，如血管再生、某些複合物的合成過程、新陳代謝過程和細胞活動方面以及部分轉錄化合物的活性和綁定功能方面。 其中，GO: 0045766和 GO: 0001525 涉及到血管再生，尤其是對乳腺組織的血管再生和增殖; GO: 0061180 涉及乳腺上皮細胞發展和乳腺增生過程，文獻[8]也提出該注釋相關的血管內皮增長因子與乳腺極性組織的缺失有關。 在 KEGG 通路富集分析中，hsa04110 直接磷酸化和激活了腫瘤抑制蛋白 p53，而 p53 與其轉錄目標在乳腺癌中其重要作用; ko03440 同源重組為DNA 雙鏈損傷精確修復的關鍵，與乳腺癌相關的抑癌基因通過同源重組共同起作用。 由此可以推測，該模組可能對乳腺癌抑制細胞起負作用，同時激活癌細胞並使其失控增長。針對利用基因表達譜數據進行乳腺癌疾病模組挖掘時易受樣本數量少、數據不完整影響、存在噪聲和偏差的問題，提出了一種基於關鍵節點子團和局部適應度的模組挖掘 KNGLF 算法。 該算法未採用基因表達譜數據，而是通過整合疾病表型信息、GO 深度信息、PPI 網路等對候選基因進行打分，篩選關鍵節點來構建關鍵節點子團，使用局部適應度和富集顯著性分析思想進行模組挖掘和確認。 實驗結果表明，利用 KNGLF 算法所挖掘出的模組不僅有較好的富集顯著性，且與乳腺癌疾病密切相關，在該疾病的發生和發展過程中起到了一定的作用和影響。 相比於其他打分策略，KNGLF 算法打分策略得到的致病基因平均排名較低，AUC值大於 RWR 算法和 CIPHER 算法; 與其他模組挖掘算法相比，KNGLF 算法挖掘的模組不僅包含較多核心基因數目，而且在模組數目、平均模組 P值、模組 Top 5 平均 P 值、模組 Top 10 平均 P 值、平均模組密度等方面具有明顯優勢。 由此可知，KNGLF 算法不依賴於表達譜數據，可準確挖掘出具有一定生物意義的乳腺癌候選模組，對疾病病理了解、前期診斷、後期預防和治療提供了較大幫助，還可進一步擴展用於挖掘其他疾病候選模組。
