[發(fā)明專利]一種基于(k,p)-core的快速高效社群發(fā)現(xiàn)方法及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201911042151.2
• 申請日: 2019-10-30
• 公開（公告）號(hào): CN112818178B
• 公開（公告）日: 2022-10-25
• 發(fā)明（設(shè)計(jì)）人: 林學(xué)民;張琛;張帆;張穎;張文杰
• 申請（專利權(quán)）人: 華東師范大學(xué);君爍（上海）信息科技有限公司
• 主分類號(hào): G06F16/901
• 分類號(hào): G06F16/901;G06Q50/00
• 代理公司: 上海德禾翰通律師事務(wù)所 31319
• 代理人: 陳艷娟

1.一種基于(k,p)-core的快速高效社群發(fā)現(xiàn)方法，其特征在于，挖掘新型密集子圖模型(k,p)-core，以進(jìn)行社群挖掘和網(wǎng)絡(luò)分解分析，包括以下步驟：

步驟A：對(duì)網(wǎng)絡(luò)和社群進(jìn)行建模；具體包括：

(a)用圖結(jié)構(gòu)表示網(wǎng)絡(luò)，其中每個(gè)節(jié)點(diǎn)代表一個(gè)實(shí)體，每條邊代表節(jié)點(diǎn)之間的連接關(guān)系；

(b)將圖中的(k,p)-core定義為一個(gè)節(jié)點(diǎn)的集合，其中每個(gè)節(jié)點(diǎn)在這個(gè)集合中的鄰點(diǎn)數(shù)至少有k個(gè)，且在這個(gè)集合中的鄰點(diǎn)數(shù)占其總鄰點(diǎn)數(shù)的比例大于等于p；

步驟B：進(jìn)行(k,p)-core的分解；具體包括：對(duì)于k值從1到圖的簡并度，計(jì)算每一個(gè)節(jié)點(diǎn)的p值；所述步驟B包括：首先對(duì)圖中所有的點(diǎn)做k-core的分解，然后對(duì)k值從1到圖的簡并度，每次計(jì)算一個(gè)p的最小值，從圖中刪掉這個(gè)點(diǎn)，把其p值設(shè)為當(dāng)前計(jì)算的值，依次刪除其他不滿足k值和p值要求的點(diǎn)，再計(jì)算下一個(gè)最小p值；

步驟C：計(jì)算每一個(gè)k，p值對(duì)，并使用索引進(jìn)行存儲(chǔ)，便于查詢。

2.如權(quán)利要求1所述的基于(k,p)-core的快速高效社群發(fā)現(xiàn)方法，其特征在于，所述步驟C包括：計(jì)算每一個(gè)k值以及其計(jì)算過程中產(chǎn)生的p值對(duì)，并對(duì)其中的點(diǎn)進(jìn)行索引。

3.一種基于(k,p)-core的快速高效社群發(fā)現(xiàn)系統(tǒng)，其特征在于，采用如權(quán)利要求1或2所述的基于(k,p)-core的快速高效社群發(fā)現(xiàn)方法，所述系統(tǒng)包括：

建模模塊，其用于對(duì)網(wǎng)絡(luò)和社群進(jìn)行建模；

分解模塊，其用于進(jìn)行(k,p)-core的分解；具體包括：對(duì)于k值從1到圖的簡并度，計(jì)算每一個(gè)節(jié)點(diǎn)的p值；

存儲(chǔ)模塊，其用于計(jì)算每一個(gè)k，p值對(duì)，并使用索引進(jìn)行存儲(chǔ)，便于查詢。