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

有效

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

本發明公開了一種識別屬性設施網絡關鍵結構的方法。為了找到稠密且穩定的屬性設施網絡，本發明在屬性設施網絡上提出了一種新的識別屬性設施網絡模型，即屬性設施網絡的關鍵結構。本發明首先通過縮小需要選擇的設施選擇空間，減少最后需要選擇的設施的計算量。同時考慮到非平衡圖形結構和屬性設施網絡的屬性，本發明提出了新的剪枝方法，將選擇出的可能需要被移除的設施進行進一步的考察，快速排除不滿足要求的設施，從而能在大型屬性設施網絡中迅速找到屬性設施網絡的關鍵結構。本發明方法的應用對屬性設施網絡關鍵結構的識別有著極大的效益，對現實生活中屬性設施網絡的選擇有著極大的幫助。

技術領域

本發明屬于設施網絡據探測技術領域，尤其涉及一種識別屬性設施網絡關鍵結構的方法。

背景技術

在現實生活中，設施網絡與我們密不可分，例如共享單車位置的投放，電動汽車充電樁的分布，公共滅火設施的分布等。隨著社會的不斷發展與網絡規模的不斷擴大，各種設施網絡也在顯著的增長。在設施網路中，每個設施與其他設施間都有一定的關聯，有些設施間可能起著互相促進的作用，例如同平臺不同位置的共享單車，它們能夠幫助周邊的使用者快速解決最后一公里問題。但有些設施間仍存在互斥的作用，例如已經老化的設施，這些設施會與其他設施存在一些沖突，導致我們真正使用公共設施時卻不能及時獲取。我們將有促進作用的設施間的關系記為正邊，有消極互斥作用的設施間的關系記為負邊，從而在設施網絡的基礎上得到屬性設施網絡。

對設施網絡的研究，一般將現有的設施之間的關系默認為積極關系，即它們都是相互促進的作用。但在實際生活中，仍存在互斥的設施，如果將這些設施都認為有相互促進的作用，可能會存在得到的設施網絡中有不穩定的結構，例如當我們急需使用共享單車或者充電樁時，不能在附近區域找到合適的設施。但如果將互斥之間的設施直接從設施網絡中移除，則會得到一個非常小的設施網絡。

同時，為了獲取用戶真正需要的屬性設施網絡，我們需要獲得屬性設施網絡的關鍵結構。對于識別屬性設施網絡的關鍵結構，許多研究者對其進行深入探討，然而，許多研究者在研究屬性設施網絡時將其中的邊默認為正邊，而這不能真實反映出設施間的關系，這與用戶的生活狀況脫離了緊密的聯系，不能夠很好的找到稠密且穩定的屬性設施網絡。同時在識別屬性設施網絡的關鍵結構中，現有算法效率較低，不能夠快速的識別出用戶需要的屬性設施網絡。

發明內容

本發明的目的在于針對現有技術的不足，提供一種識別屬性設施網絡關鍵結構的方法。

本發明的目的是通過以下技術方案實現的：一種識別屬性設施網絡關鍵結構的方法，該方法包括以下步驟：

步驟一：給定真實的屬性設施網絡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后而不滿足正設施網絡的關鍵結構的條件，從而被移除的所有設施的數目。