[發明專利]一種基于k核的公平社區挖掘方法

在審

• 申請號: 202110520761.X
• 申請日: 2021-05-13
• 公開（公告）號: CN113127756A
• 公開（公告）日: 2021-07-16
• 發明（設計）人: 潘敏佳;李榮華;王國仁;金福生;秦宏超
• 申請（專利權）人: 北京理工大學
• 主分類號: G06F16/9536
• 分類號: G06F16/9536;G06F16/26
• 代理公司: 北京圣州專利代理事務所(普通合伙) 11818
• 代理人: 劉巖

1.一種基于k核的公平社區挖掘方法，其特征在于，包括如下步驟：

S1：核分解，尋找colorful-(k-1)-核；

S2：公平團枚舉，對核分解后產生的節點屬性圖，采用枚舉方法尋找k-公平團；

S3：輸出結果集合，輸出的所有k-公平團即為公平社區；

對于一個節點屬性圖和一個閾值k，符合以下條件的團C被稱為k-公平團：(1)對于任意屬性值，團C內該屬性值節點的數量不小于k；(2)不存在一個團C’包含C還滿足條件(1)。

2.根據權利要求1所述的基于k核的公平社區挖掘方法，其特征在于：所述S1步驟包括：

S11：對節點圖進行貪心著色；

S12：計算節點圖中每個節點的最小色彩度，將色彩度小于k-1的節點刪除，并放入刪除隊列中；

S13：彈出刪除隊列中的節點，在圖中找到彈出節點的鄰居節點；

S14：更新鄰居節點的最小色彩度，并進行判斷；若鄰居節點最小色彩度小于k-1，則放入刪除隊列中；

S15：重復S13-S14，直至刪除隊列為空，最后剩余節點構成的節點屬性圖即為colorful-(k-1)-核。

3.根據權利要求1所述的基于k核的公平社區挖掘方法，其特征在于：所述S2步驟包括：

S21：對核分解后的節點屬性圖進行節點遍歷，分別尋找當前節點的連通分量；

S22：初始化結果集合、候補集合和篩選集合，結果集合代表驗證通過的節點集合，候補集合用于擴展結果集合，篩選集合內記錄的是與當前結果集合里的所有節點都有邊相連的節點集合；初始化后的結果集合、篩選集合為空，候選集合為S21步驟中的連通分量里的節點集合；

S23：判斷候補集合、篩選集合是否均為空，若均為空則輸出結果集合；

S24：若候補集合不為空，彈出候補集合的一個節點u并加入結果集合中，結合公平團定義對結果集合進行檢查；初始化新的結果集合、候補集合和篩選集合，其中，新的候補集合為當前候補集合中所有與u有邊相連的節點，新的篩選集合為當前篩選集合中所有與u有邊相連的節點；利用新的集合進行下一層的搜索，搜索完畢，將彈出節點u加入篩選集合內；

S25：重復S23-S24步驟，直至候補集合遍歷完成；

S26：更換節點，重復S21-S25步驟，直至核分解后的節點屬性圖遍歷完成。

4.根據權利要求1所述的基于k核的公平社區挖掘方法，其特征在于：所述S2步驟中枚舉方法基于深度優先遍歷順序完成。

5.根據權利要求3所述的基于k核的公平社區挖掘方法，其特征在于：所述S22步驟中還包括候補集合的優先排序，按照最小色彩度對候補集合內節點進行排列。

6.根據權利要求3所述的基于k核的公平社區挖掘方法，其特征在于：所述S24步驟中檢查包括節點數量的檢查以及屬性值擁有節點數量的檢查。