[發(fā)明專利]一種基于k核的公平社區(qū)挖掘方法

在審

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

本發(fā)明公開了一種基于k核的公平社區(qū)挖掘方法，包括如下步驟：S1：核分解，尋找colorful?(k?1)?核；S2：公平團(tuán)枚舉，對核分解后產(chǎn)生的節(jié)點屬性圖，采用枚舉方法尋找k?公平團(tuán)；S3：輸出結(jié)果集合，輸出的所有k?公平團(tuán)即為公平社區(qū)。本發(fā)明采用上述結(jié)構(gòu)的基于k核的公平社區(qū)挖掘方法，解決了在社區(qū)挖掘中，屬性圖中極大團(tuán)節(jié)點屬性的不均衡問題，提高了搜索效率。

技術(shù)領(lǐng)域

本發(fā)明涉及大圖數(shù)據(jù)分析技術(shù)領(lǐng)域，尤其是涉及一種基于k核的公平社區(qū)挖掘方法。

背景技術(shù)

近年來，隨著信息技術(shù)的發(fā)展，各種大數(shù)據(jù)技術(shù)普遍應(yīng)用于研究中，例如社交網(wǎng)絡(luò)，Web網(wǎng)絡(luò)，生物網(wǎng)絡(luò)等。從這些網(wǎng)絡(luò)中提取出隱含的稠密子結(jié)構(gòu)是網(wǎng)絡(luò)分析的一個基本問題，例如從社交網(wǎng)絡(luò)中挖掘出社交圈子，在Web網(wǎng)絡(luò)中發(fā)現(xiàn)關(guān)鍵重要的網(wǎng)站，以及在生物網(wǎng)絡(luò)找出蛋白絡(luò)合物。目前人們在圖網(wǎng)絡(luò)挖掘的領(lǐng)域中提出了許多模型來提取網(wǎng)絡(luò)中的稠密子圖，其中比較經(jīng)典的模型為極大團(tuán)模型，極大團(tuán)表示圖中的極大完全圖，也就是說每兩個點之間都要有邊相連。

屬性圖是一種帶有屬性的圖，屬性可以具體分為節(jié)點屬性以及邊屬性。屬性的存在增加的圖的信息維度，使挖掘出來的社區(qū)具有更加豐富的含義。如果在屬性圖中簡單地尋找極大團(tuán)，找到的極大團(tuán)常常帶有非常不均勻的屬性。以性別作為屬性為例，普通的極大團(tuán)枚舉方法可能找到屬性全為“男性”或“女性”的社區(qū)，這樣的社區(qū)是不公平的，因為不同性別的節(jié)點數(shù)量有很大的差距。為了解決這個問題，我們提出了“公平團(tuán)”的概念以及挖掘“公平團(tuán)”的方法。

現(xiàn)有的普通極大團(tuán)枚舉方法也可以用來尋找公平團(tuán)，但是由于沒有充分地利用節(jié)點的屬性信息，因此不得不首先找到所有的團(tuán)，然后根據(jù)公平團(tuán)的條件來進(jìn)行篩選，效率低下。

發(fā)明內(nèi)容

在挖掘社區(qū)時，本發(fā)明通過使用公平團(tuán)挖掘方法，代替極大團(tuán)挖掘方法，解決了社區(qū)挖掘的不公平性以及枚舉效率低的問題。

為實現(xiàn)上述目的，本發(fā)明提供了如下技術(shù)方案：

一種基于k核的公平社區(qū)挖掘方法，包括如下步驟：

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

S2：公平團(tuán)枚舉，對核分解后產(chǎn)生的節(jié)點屬性圖，采用枚舉方法尋找k-公平團(tuán)；

S3：輸出結(jié)果集合，輸出的所有k-公平團(tuán)即為公平社區(qū)；

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

優(yōu)選的，所述S1步驟包括：

S11：對節(jié)點圖進(jìn)行貪心著色；

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

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

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

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

優(yōu)選的，所述S2步驟包括：

S21：對核分解后的節(jié)點屬性圖進(jìn)行節(jié)點遍歷，分別尋找當(dāng)前節(jié)點的連通分量；

S22：初始化結(jié)果集合、候補(bǔ)集合和篩選集合，結(jié)果集合代表驗證通過的節(jié)點集合，候補(bǔ)集合用于擴(kuò)展結(jié)果集合，篩選集合內(nèi)記錄的是與當(dāng)前結(jié)果集合里的所有節(jié)點都有邊相連的節(jié)點集合；初始化后的結(jié)果集合、篩選集合為空，候選集合為S21步驟中的連通分量里的節(jié)點集合；