[發明專利]一種復雜網絡圖的概要方法及其在蛋白質關系網中的應用

在審

• 申請號: 201911335783.8
• 申請日: 2019-12-23
• 公開（公告）號: CN110956223A
• 公開（公告）日: 2020-04-03
• 發明（設計）人: 董一鴻;徐麗麗;王雄
• 申請（專利權）人: 寧波大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 寧波誠源專利事務所有限公司 33102
• 代理人: 徐雪波;鄧青玲

1.一種復雜網絡圖的概要方法，將復雜網絡圖記為G＝(V，E)，其中，V為復雜網絡圖中節點的集合，E為復雜網絡圖中邊的集合，其特征在于：包括以下步驟：

步驟1、在復雜網絡圖中挑選出滿足如下條件的子圖H＝(V′,E′)，對于子圖中任意兩節點u和v組成的邊，u∈V′，v∈V′，滿足條件：sup(e(u,v)，H)≥k-2，其中，sup(e(u,v)，H)＝|{△_uvw:w∈V′}|，△_uvw為任意節點u、v和w構成的三角形數目，將這些子圖標記為稠密子圖；其中，k為大于等于3的預設值；

步驟2、將每個稠密子圖中的所有節點壓縮成一個節點，將該節點標記為超點，將與所有超點相關聯的邊，標記為超邊；

步驟3、將步驟2中的所有超點和復雜網絡圖中除超點外的其他節點組成新的節點集合，將超邊和除超邊外的其他邊組成新的邊集合，將新的節點集合和新的邊集合形成所述復雜網絡圖的概要圖。

2.根據權利要求1所述的復雜網絡圖的概要方法，其特征在于：所述步驟1中采用并行化方法計算任意節點u和v組成的邊構成的三角形數目，具體步驟為：

步驟1-1、將復雜網絡圖G＝(V，E)按照網絡圖(V1，(V2))形式存儲，其中，V1是V中的任意一個節點，V2為與V1相關聯的所有節點；

步驟1-2、復制步驟1-1中的網絡圖(V1，(V2))，對這兩個相同的網絡圖進行笛卡爾乘積計算，將得到的結果按照((V3，n1)，(V4，n2))的形式存儲；

步驟1-3、將步驟1-2中計算得到的結果中過濾掉節點相同的結果，即過濾掉V3＝V4的情況，得到不同節點的網絡圖；

步驟1-4、將步驟1-3中得到的網絡圖中求取n1和n2中節點相同的個數，將該個數作為節點V3和節點V4組成的邊構成的三角形數目，即得到任意一條邊構成的三角形數目。

3.根據權利要求1所述的復雜網絡圖的概要方法，其特征在于：所述步驟1中k值設定的具體方法為：通過計算不同k值對應的模塊度，將模塊度最大值時對應的k值作為預設值。

4.根據權利要求3所述的復雜網絡圖的概要方法，其特征在于：所述步驟1中k值的取值范圍為3～10。

5.根據權利要求1所述的復雜網絡圖的概要方法，其特征在于：所述步驟3中得到的概要圖分層進行存儲，概要圖分為外層存儲和內層存儲，以超點和復雜網絡圖中除超點外的其他節點為單元以及其關聯邊構建原始圖關聯信息的外層存儲，以每個超點內部節點及其關聯邊構建超點內關聯信息的內層存儲。

6.根據權利要求5所述的復雜網絡圖的概要方法，其特征在于：所述概要圖采用鏈接表的方式對每個超點和復雜網絡圖中除超點外的其他節點以及其關聯邊信息進行外層存儲。

7.根據權利要求5所述的復雜網絡圖的概要方法，其特征在于：所述概要圖采用矩陣的方式對每個超點內部節點以及其關聯邊信息進行內層存儲。

8.根據權利要求6或7所述的復雜網絡圖的概要方法，其特征在于：所述步驟3中的概要圖存儲時還保存有概要圖中所有邊的權值，其中，概要圖中邊的權值設定的計算公式為：

其中，E_ij為節點i和j之間邊的數目，|V_i|為超點i內部的節點數目；|V_j|為超點j內部的節點數目。

9.一種如權利要求1至8中任意一項權利要求所述復雜網絡圖的概要方法的應用，其特征在于：將某一物質中的蛋白質關系網定義為權利要求1至8中任意一項權利要求中提及的復雜網絡圖，即將該物質中的蛋白質節點作為復雜網絡圖中的節點，將任意兩個會發生相互作用的蛋白質之間進行連線，將該連線記為該兩個節點的之間形成的邊；通過步驟1的方法，該物質中的蛋白質關系網中多個蛋白質節點組成的稠密子圖即表示為蛋白質復合物，通過步驟2和步驟3的方法，將該蛋白質復合物壓縮成一個節點，作為超點，并由此得到該物質中蛋白質復合物與其他蛋白質或蛋白質復合物之間的相互作用。