[發明專利]一種識別屬性設施網絡關鍵結構的方法

有效

• 申請號: 202110049616.8
• 申請日: 2021-01-14
• 公開（公告）號: CN112686574B
• 公開（公告）日: 2023-05-26
• 發明（設計）人: 王瀟楊;張夢琪;盧旭峰;胡柯青;劉心如;孫仁杰;陳晨
• 申請（專利權）人: 浙江工商大學
• 主分類號: G06Q10/0631
• 分類號: G06Q10/0631;G06Q10/04
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 劉靜

1.一種識別屬性設施網絡關鍵結構的方法，其特征在于，該方法包括以下步驟：

步驟一：給定真實的屬性設施網絡G(V,E)，其中V代表G中所有的設施集合，E代表G中所有設施間的邊；從中獲取V中的所有設施和E中的所有正邊，構成正設施網絡；

定義屬性設施網絡G中的非平衡圖形結構X(R,S)，其滿足以下條件：對V中的某些子設施集合R，R中的所有設施和它們所有的邊S能夠圍成多邊形，并且所有的邊中正邊數量小于負邊數量；

步驟二：計算正設施網絡的關鍵結構，該關鍵結構需滿足兩個條件：1.關鍵結構中每個設施u至少有k條正邊，即設施u有k個正鄰居；2.關鍵結構是極大的，即任何更大的關鍵結構都不滿足每個設施至少有k個正鄰居；

步驟三：將屬性設施網絡G中存在負鄰居的設施放入候選刪除設施集C中；

步驟四：對于每個候選刪除設施集C，計算C中設施的關鍵結構群，關鍵結構群滿足以下條件：1.關鍵結構群中的每個設施的鄰居數為k；2.在關鍵結構群中，對某一設施u，必定存在一個設施v≠u，滿足u和v在同一個關鍵結構群中，并且v是u的正鄰居；

步驟五：計算候選刪除設施集C中每個設施的刪除成本，對于設施u的刪除成本，其定義為：在正設施網絡的關鍵結構中，因刪除設施u后而不滿足正設施網絡的關鍵結構的條件，從而被移除的所有設施的數目；

步驟六：獲取屬性設施網絡G的關鍵結構，屬性設施網絡的關鍵結構滿足以下條件：1.關鍵結構中每個設施的正鄰居數量至少為k；2.關鍵結構中不存在非平衡圖形結構；3.關鍵結構是極大的，即任何更大的關鍵結構都不滿足條件1和條件2；

獲取過程具體為：選擇候選刪除設施集C中刪除成本最小的設施u，如果u存在某關鍵結構群中，則將該關鍵結構群中的所有設施從G中刪除，否則只需在G中刪除u；若刪除設施后得到的屬性設施網絡G*滿足屬性設施網絡關鍵結構的條件，則輸出該屬性設施網絡G*作為屬性設施網絡的關鍵結構，否則返回步驟四。

2.根據權利要求1所述的一種識別屬性設施網絡關鍵結構的方法，其特征在于，所述步驟一中，如果設施u和設施v之間有積極關系，則將兩個設施的邊記為正邊，設施v稱為設施u的正鄰居；如果設施u和設施v之間有消極關系，則將兩個設施的邊記為負邊，設施v稱為設施u的負鄰居。

3.根據權利要求1所述的一種識別屬性設施網絡關鍵結構的方法，其特征在于，所述步驟一中獲取正設施網絡具體為：訪問屬性設施網絡G中設施集合V中的某個設施u，將設施u和設施u的正邊加入新的屬性設施網絡中，訪問完某個設施u的所有邊后再繼續訪問V中的其他設施，直到所有設施訪問完畢，所得到的新的屬性設施網絡為正設施網絡。

4.根據權利要求1所述的一種識別屬性設施網絡關鍵結構的方法，其特征在于，所述步驟二中，計算正設施網絡的關鍵結構具體為：查詢正設施網絡中某個設施u，若設施u的正邊數量小于k，則迭代地刪除設施u和u的正邊，直到不存在可以刪除的設施，剩余的正設施網絡為關鍵結構。

5.根據權利要求1所述的一種識別屬性設施網絡關鍵結構的方法，其特征在于，所述步驟三中，為了打破屬性設施網絡中的非平衡圖形結構，將G中存在負鄰居的設施放入候選刪除設施集C中，候選刪除設施集C不再為屬性設施網絡G中的所有設施。