[發明專利]一種改變復雜網絡中節點控制類別的方法

有效

• 申請號: 201711261943.X
• 申請日: 2017-12-04
• 公開（公告）號: CN108009061B
• 公開（公告）日: 2020-04-14
• 發明（設計）人: 張錫哲;李倩
• 申請（專利權）人: 東北大學
• 主分類號: G06F11/22
• 分類號: G06F11/22;G06N3/06;G06N3/08
• 代理公司: 北京易捷勝知識產權代理事務所(普通合伙) 11613
• 代理人: 韓國勝

1.一種改變復雜網絡中節點控制類別的方法，其特征在于，包括：

步驟101、針對待處理的冗余節點n，獲取網絡中能夠通過交錯路徑到達冗余節點n的所有未飽和節點；

步驟102、構造以所述冗余節點n為起點的交錯網絡；

步驟103、采用最小割算法處理所述交錯網絡，獲取所述冗余節點n與所述交錯路徑上所有未飽和節點斷開時所需要刪除的最少邊的集合；

步驟104、識別所述網絡中包括所述冗余節點n的交錯環，并基于識別的交錯環，確定出破壞所述交錯環所需刪除的連邊；

步驟105、刪除最少邊的集合中的所有連邊，以及刪除確定出的用于破壞所述交錯環所需刪除的連邊；

步驟106、在所述網絡中選擇一條從所述冗余節點n出發的交錯路徑，刪除選擇的交錯路徑中的一個匹配邊，使得所述冗余節點n轉換為輸入節點；

所述網絡為所述冗余節點n當前所在的網絡；所述網絡為蛋白質交互網絡，食物鏈網絡、基因調控網絡、生態系統中的網絡或科技系統中的網絡。

2.根據權利要求1所述的方法，其特征在于，所述步驟101包括：

1011、針對所述冗余節點n，獲取網絡中該冗余節點n的所有非匹配入邊，將所有非匹配入邊對應的節點加入第一隊列C中；

1012、遍歷所述第一隊列C中的節點，若遍歷的節點屬于未訪問過的未飽和節點，則更新未飽和節點集U、邊集合E’、節點集合V’；

1013、若遍歷的節點未訪問過且不是未飽和節點，則獲取該節點的匹配出邊對應的節點，將該節點加入到第二隊列Q；更新邊集合E’、節點集合V’，并更新當前遍歷的節點的狀態為已訪問狀態；

1014、遍歷完所述第一隊列C中的所有節點之后，查看第二隊列Q是否為空；

1015、若不為空，則從所述第二隊列Q取出一個節點，針對該節點，獲取該節點的非匹配入邊對應的節點，將所有非匹配入邊對應的節點加入所述第一隊列C中；

在所述第一隊列C不為空時，重復上述遍歷所述第一隊列C中的節點的步驟，直至所述第一隊列C為空；

若第二隊列Q不為空，重復步驟1015，直到第二隊列Q為空；

1016、在第一隊列C為空，且第二隊列Q為空時，所述未飽和節點集U中的所有節點即為網絡中通過交錯路徑到達冗余節點n的所有未飽和節點；

其中，遍歷所述第一隊列C和所述第二隊列Q中的節點時，若遍歷的節點為所述冗余節點n的匹配入邊對應的節點，則不處理；

若遍歷的節點的狀態為已訪問狀態，則更新邊集合E’。

3.根據權利要求2所述的方法，其特征在于，所述步驟102包括：

1021、增加一個虛擬節點t；

1022、基于所述虛擬節點t，更新節點集合V’；

1023、基于所述虛擬節點t，和所述未飽和節點集U中的所有未飽和節點，更新所述邊集合E’；

1024、將所述冗余節點n的匹配入邊對應的節點作為交錯網絡的源節點；構造該源節點到虛擬節點t的有向網絡G’，該有向網絡作為交錯網絡；

其中，所述交錯網絡中與所述虛擬節點直接關聯的所有邊的邊權重為無窮大。

4.根據權利要求3所述的方法，其特征在于，所述步驟103包括：

1031、針對上述所構造的有權重的交錯網絡，采用最小割算法處理所述交錯網絡，獲取所述交錯網絡中需要刪除的最少的邊；

1032、將所述交錯網絡中需要刪除的最少的邊轉化為所述網絡中的邊，將轉化后的邊作為所述冗余節點n與所述交錯路徑上所有未飽和節點斷開時所需要刪除的最少邊。