[發(fā)明專利]一種識(shí)別屬性設(shè)施網(wǎng)絡(luò)關(guān)鍵結(jié)構(gòu)的方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202110049616.8
• 申請(qǐng)日: 2021-01-14
• 公開（公告）號(hào): CN112686574B
• 公開（公告）日: 2023-05-26
• 發(fā)明（設(shè)計(jì)）人: 王瀟楊;張夢(mèng)琪;盧旭峰;胡柯青;劉心如;孫仁杰;陳晨
• 申請(qǐng)（專利權(quán)）人: 浙江工商大學(xué)
• 主分類號(hào): G06Q10/0631
• 分類號(hào): G06Q10/0631;G06Q10/04
• 代理公司: 杭州求是專利事務(wù)所有限公司 33200
• 代理人: 劉靜

1.一種識(shí)別屬性設(shè)施網(wǎng)絡(luò)關(guān)鍵結(jié)構(gòu)的方法，其特征在于，該方法包括以下步驟：

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

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

步驟二：計(jì)算正設(shè)施網(wǎng)絡(luò)的關(guān)鍵結(jié)構(gòu)，該關(guān)鍵結(jié)構(gòu)需滿足兩個(gè)條件：1.關(guān)鍵結(jié)構(gòu)中每個(gè)設(shè)施u至少有k條正邊，即設(shè)施u有k個(gè)正鄰居；2.關(guān)鍵結(jié)構(gòu)是極大的，即任何更大的關(guān)鍵結(jié)構(gòu)都不滿足每個(gè)設(shè)施至少有k個(gè)正鄰居；

步驟三：將屬性設(shè)施網(wǎng)絡(luò)G中存在負(fù)鄰居的設(shè)施放入候選刪除設(shè)施集C中；

步驟四：對(duì)于每個(gè)候選刪除設(shè)施集C，計(jì)算C中設(shè)施的關(guān)鍵結(jié)構(gòu)群，關(guān)鍵結(jié)構(gòu)群滿足以下條件：1.關(guān)鍵結(jié)構(gòu)群中的每個(gè)設(shè)施的鄰居數(shù)為k；2.在關(guān)鍵結(jié)構(gòu)群中，對(duì)某一設(shè)施u，必定存在一個(gè)設(shè)施v≠u，滿足u和v在同一個(gè)關(guān)鍵結(jié)構(gòu)群中，并且v是u的正鄰居；

步驟五：計(jì)算候選刪除設(shè)施集C中每個(gè)設(shè)施的刪除成本，對(duì)于設(shè)施u的刪除成本，其定義為：在正設(shè)施網(wǎng)絡(luò)的關(guān)鍵結(jié)構(gòu)中，因刪除設(shè)施u后而不滿足正設(shè)施網(wǎng)絡(luò)的關(guān)鍵結(jié)構(gòu)的條件，從而被移除的所有設(shè)施的數(shù)目；

步驟六：獲取屬性設(shè)施網(wǎng)絡(luò)G的關(guān)鍵結(jié)構(gòu)，屬性設(shè)施網(wǎng)絡(luò)的關(guān)鍵結(jié)構(gòu)滿足以下條件：1.關(guān)鍵結(jié)構(gòu)中每個(gè)設(shè)施的正鄰居數(shù)量至少為k；2.關(guān)鍵結(jié)構(gòu)中不存在非平衡圖形結(jié)構(gòu)；3.關(guān)鍵結(jié)構(gòu)是極大的，即任何更大的關(guān)鍵結(jié)構(gòu)都不滿足條件1和條件2；

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

2.根據(jù)權(quán)利要求1所述的一種識(shí)別屬性設(shè)施網(wǎng)絡(luò)關(guān)鍵結(jié)構(gòu)的方法，其特征在于，所述步驟一中，如果設(shè)施u和設(shè)施v之間有積極關(guān)系，則將兩個(gè)設(shè)施的邊記為正邊，設(shè)施v稱為設(shè)施u的正鄰居；如果設(shè)施u和設(shè)施v之間有消極關(guān)系，則將兩個(gè)設(shè)施的邊記為負(fù)邊，設(shè)施v稱為設(shè)施u的負(fù)鄰居。

3.根據(jù)權(quán)利要求1所述的一種識(shí)別屬性設(shè)施網(wǎng)絡(luò)關(guān)鍵結(jié)構(gòu)的方法，其特征在于，所述步驟一中獲取正設(shè)施網(wǎng)絡(luò)具體為：訪問屬性設(shè)施網(wǎng)絡(luò)G中設(shè)施集合V中的某個(gè)設(shè)施u，將設(shè)施u和設(shè)施u的正邊加入新的屬性設(shè)施網(wǎng)絡(luò)中，訪問完某個(gè)設(shè)施u的所有邊后再繼續(xù)訪問V中的其他設(shè)施，直到所有設(shè)施訪問完畢，所得到的新的屬性設(shè)施網(wǎng)絡(luò)為正設(shè)施網(wǎng)絡(luò)。

4.根據(jù)權(quán)利要求1所述的一種識(shí)別屬性設(shè)施網(wǎng)絡(luò)關(guān)鍵結(jié)構(gòu)的方法，其特征在于，所述步驟二中，計(jì)算正設(shè)施網(wǎng)絡(luò)的關(guān)鍵結(jié)構(gòu)具體為：查詢正設(shè)施網(wǎng)絡(luò)中某個(gè)設(shè)施u，若設(shè)施u的正邊數(shù)量小于k，則迭代地刪除設(shè)施u和u的正邊，直到不存在可以刪除的設(shè)施，剩余的正設(shè)施網(wǎng)絡(luò)為關(guān)鍵結(jié)構(gòu)。

5.根據(jù)權(quán)利要求1所述的一種識(shí)別屬性設(shè)施網(wǎng)絡(luò)關(guān)鍵結(jié)構(gòu)的方法，其特征在于，所述步驟三中，為了打破屬性設(shè)施網(wǎng)絡(luò)中的非平衡圖形結(jié)構(gòu)，將G中存在負(fù)鄰居的設(shè)施放入候選刪除設(shè)施集C中，候選刪除設(shè)施集C不再為屬性設(shè)施網(wǎng)絡(luò)G中的所有設(shè)施。