[發明專利]一種挖掘符號網絡中最大有符號θ團的方法

在審

• 申請號: 202110793113.1
• 申請日: 2021-07-14
• 公開（公告）號: CN113409161A
• 公開（公告）日: 2021-09-17
• 發明（設計）人: 陳晨;張夢琪;盧旭峰;吳艷萍;王瀟楊
• 申請（專利權）人: 浙江工商大學
• 主分類號: G06Q50/00
• 分類號: G06Q50/00
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 劉靜

1.一種挖掘符號網絡中最大有符號θ團的方法，其特征在于，所述最大有符號θ團需滿足四個條件：其中的任意一個頂點的正鄰居數與負鄰居數之差需大于等于θ；是極大的，即任何它的超圖都不是有符號θ團；點數是最多的；是一個團，即團中的每一對頂點都是相鄰的；該方法包括：

通過三種修剪策略過濾圖G中不必要的點和邊，包括：

引理1：基于頂點的修剪規則：對于有符號θ團中的頂點u，需滿足u的正鄰居數量大于等于θ；

引理2：基于邊的修剪規則：對于有符號θ團S中的兩個頂點u和v，它們相連的邊(u，v)為正邊，則該邊至少被包含在(θ-1)個正三角形中，所述正三角形為三條邊均為正邊的三角形；

引理3：基于邊的修剪規則：對于有符號θ團S中的兩個頂點u和v，它們相連的邊(u，v)為負邊，則該邊至少被包含在(θ+1)個負三角形中，所述負三角形為兩條邊為正邊，另一條邊為負邊的三角形；

通過最大化有符號θ團貪心啟發算法在大型符號網絡上迅速挖掘最大有符號θ團，包括：

步驟一，根據引理1過濾圖G中不滿足條件的頂點，得到新的圖G'；

步驟二，根據引理2判斷圖G'中正邊所在的正三角形的數量，根據引理3判斷圖G'中負邊所在的負三角形的數量，將不滿足條件的邊從圖G'中刪去，從而得到新的圖A；

步驟三，移除圖A中孤立的點；

步驟四，使用著色算法貪心地將圖A中的點著色；

步驟五，在步驟四著色后的圖A中，根據遞歸算法找到最大有符號θ團MaxC，即待挖掘的符號網絡子圖。

2.根據權利要求1所述的一種挖掘符號網絡中最大有符號θ團的方法，其特征在于，所述步驟四包括：迭代地從圖A中選擇鄰居數量最大的頂點并為其分配顏色，如果當前選擇的頂點與有顏色的頂點相鄰，為其分配一種與其相鄰頂點不同的顏色。

3.根據權利要求1所述的一種挖掘符號網絡中最大有符號θ團的方法，其特征在于，所述步驟五中，調用遞歸算法尋找分支中是否存在有符號θ團，遞歸算法接收兩個輸入參數{S，C}，其中S是臨時結果集，初始為空集，C是待加入S的候選點集，初始為圖A，并初始化最終結果MaxC為空集，遞歸算法的具體實現過程包括以下子步驟：

(a)如果集合S中點的數量與C中著色的點的顏色種類數量之和小于|MaxC|+1和θ+1的最大值，則返回0，并執行步驟(d)，否則執行(b)，其中，|MaxC|表示MaxC中頂點的數量；

(b)如果C為空集，則對于S中任意的點u，如果它的正鄰居數量與負鄰居數量之差大于等于θ，則將MaxC更新為S，并返回1，否則返回0，并執行步驟(d)；

(c)如果C不為空集，對于S中的某點u，如果u的正鄰居數量與u的正鄰居著色的點的顏色種類數量之和小于u的負鄰居數量與θ之和，則返回0，并執行步驟(d)；

(d)設置flag為0，將C中的每個點根據其擁有的鄰居數量進行升序排序，在完成升序排序后，依次遍歷排序后的點；對于遍歷的點v，將輸入參數S更新為在S中加入點v，將輸入參數C更新為點v在C中的鄰居集合，并返回執行步驟(a)-(c)，將flag更新為當前flag值與返回結果相加，并將v從C中移除，執行步驟(e)-(f)；

(e)若flag等于0，則對于S中任意的點u，如果u的正鄰居數量與負鄰居數量之差小于θ，則返回1，并執行步驟(d)，否則執行步驟(f)；

(f)若S中點的數量大于|MaxC|，則將MaxC更新為S，并返回1，否則返回0，并執行步驟(d)。

4.一種計算機設備，包括存儲器和處理器，所述存儲器中存儲有計算機可讀指令，所述計算機可讀指令被所述處理器執行時，使得所述處理器執行如權利要求1-3中任一項所述的方法。

5.一種存儲有計算機可讀指令的存儲介質，所述計算機可讀指令被一個或多個處理器執行時，使得一個或多個處理器執行如權利要求1-3中任一項所述的方法。