[發(fā)明專利]一種網(wǎng)絡(luò)局部社團(tuán)挖掘方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201810141629.6
• 申請(qǐng)日: 2018-02-11
• 公開（公告）號(hào): CN108427724A
• 公開（公告）日: 2018-08-21
• 發(fā)明（設(shè)計(jì)）人: 徐小龍;胡楠
• 申請(qǐng)（專利權(quán)）人: 南京郵電大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 南京經(jīng)緯專利商標(biāo)代理有限公司 32200
• 代理人: 姜慧勤

本發(fā)明公開了一種網(wǎng)絡(luò)局部社團(tuán)挖掘方法，該方法能夠基于網(wǎng)絡(luò)中給定的初始種子節(jié)點(diǎn)，挖掘出網(wǎng)絡(luò)中包含這些種子節(jié)點(diǎn)的局部社團(tuán)，并最終給出這些局部社團(tuán)中所有節(jié)點(diǎn)的集合。本發(fā)明方法具有很好的普適性，能夠適用于社交、科研、生物、商品等各個(gè)領(lǐng)域的網(wǎng)絡(luò)；而且本發(fā)明方法具有良好的擴(kuò)展性，可以適應(yīng)于分布式環(huán)境中的局部社團(tuán)挖掘。

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

本發(fā)明涉及一種網(wǎng)絡(luò)局部社團(tuán)挖掘方法，屬于復(fù)雜網(wǎng)絡(luò)應(yīng)用技術(shù)領(lǐng)域。

背景技術(shù)

目前主流的挖掘局部社團(tuán)的方法是先將網(wǎng)絡(luò)進(jìn)行全局的社團(tuán)劃分，然后根據(jù)種子節(jié)點(diǎn)在全部劃分結(jié)果中查詢局部社團(tuán)節(jié)點(diǎn)。不同于現(xiàn)有主流的基于全局社團(tuán)劃分的局部社團(tuán)挖掘方法，基于局部信息的局部社團(tuán)挖掘算法更加符合現(xiàn)實(shí)中的應(yīng)用場(chǎng)景，而且能夠避免大量的全局迭代計(jì)算過程，節(jié)約計(jì)算資源。此外，目前的局部社團(tuán)挖掘方法并未給出分布式環(huán)境的計(jì)算模型，對(duì)于基于分布式環(huán)境的大規(guī)模網(wǎng)絡(luò)挖掘計(jì)算的適用性還不確定。

局部社團(tuán)挖掘算法的評(píng)價(jià)指標(biāo)主要包括準(zhǔn)確率、召回率以及綜合前兩者計(jì)算出的F值。其中，準(zhǔn)確率是指算法找出的節(jié)點(diǎn)集合中真正與種子節(jié)點(diǎn)從屬于同一局部社團(tuán)節(jié)點(diǎn)部分所占比例；召回率是指算法正確找出的節(jié)點(diǎn)數(shù)量占真正的所有和種子節(jié)點(diǎn)從屬于同一局部社團(tuán)的節(jié)點(diǎn)數(shù)量的比例；準(zhǔn)確率和召回率雖然能夠直觀的給出算法的挖掘效果，但是二者都存在一定的片面性，F(xiàn)值是一種綜合準(zhǔn)確率與召回率的評(píng)價(jià)指標(biāo)，計(jì)算方式為：

上述公式中，P_re為準(zhǔn)確率，R_ec為召回率。現(xiàn)有的局部社團(tuán)挖掘算法多是基于節(jié)點(diǎn)的度數(shù)確定節(jié)點(diǎn)的影響力，但是節(jié)點(diǎn)的度數(shù)并不能準(zhǔn)確的衡量該節(jié)點(diǎn)與社團(tuán)中其他節(jié)點(diǎn)的聯(lián)系緊密程度，而且存在“僵尸粉”這種人為手段增加節(jié)點(diǎn)的度數(shù)，干擾算法對(duì)節(jié)點(diǎn)在社團(tuán)中重要程度的準(zhǔn)確判斷，從而在對(duì)種子節(jié)點(diǎn)進(jìn)行位置微調(diào)時(shí)出現(xiàn)較大偏差。

局部社團(tuán)挖掘的目標(biāo)是通過網(wǎng)絡(luò)中的極少比例的種子節(jié)點(diǎn)獲取與這些種子節(jié)點(diǎn)從屬于同一個(gè)網(wǎng)絡(luò)社團(tuán)的其他所有節(jié)點(diǎn)的過程。局部社團(tuán)挖掘方法能夠用于在建模為網(wǎng)絡(luò)的復(fù)雜系統(tǒng)中挖掘具有特定特征的節(jié)點(diǎn)群體，而且能夠適應(yīng)于分布式計(jì)算環(huán)境下大規(guī)模網(wǎng)絡(luò)的挖掘，對(duì)于當(dāng)今網(wǎng)絡(luò)承載信息出現(xiàn)爆炸性增長的現(xiàn)狀具有重要的意義。

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

本發(fā)明所要解決的技術(shù)問題是：提供一種網(wǎng)絡(luò)局部社團(tuán)挖掘方法，通過給定網(wǎng)絡(luò)中少量的種子節(jié)點(diǎn)，實(shí)現(xiàn)對(duì)包含這些種子節(jié)點(diǎn)的局部社團(tuán)的挖掘，從而得到與種子節(jié)點(diǎn)在同一局部社團(tuán)的其他節(jié)點(diǎn)。

本發(fā)明為解決上述技術(shù)問題采用以下技術(shù)方案：

一種網(wǎng)絡(luò)局部社團(tuán)挖掘方法，包括如下步驟：

步驟1，對(duì)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)進(jìn)行編號(hào)，且每個(gè)節(jié)點(diǎn)的編號(hào)唯一，并將節(jié)點(diǎn)的編號(hào)作為自身的id；

步驟2，設(shè)定網(wǎng)絡(luò)中的部分節(jié)點(diǎn)為種子節(jié)點(diǎn)，并獲取各種子節(jié)點(diǎn)對(duì)應(yīng)的編號(hào)；

步驟3，針對(duì)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)，根據(jù)節(jié)點(diǎn)的度數(shù)和包含該節(jié)點(diǎn)的三角環(huán)數(shù)，計(jì)算每個(gè)節(jié)點(diǎn)的關(guān)系密度值；

步驟4，基于高斯模糊算法的思想，對(duì)于網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)，計(jì)算其自身的關(guān)系密度值和鄰居節(jié)點(diǎn)的關(guān)系密度值的加權(quán)平均值，將加權(quán)平均的結(jié)果作為該節(jié)點(diǎn)的社團(tuán)中心性值；

步驟5，在網(wǎng)絡(luò)中，通過有指導(dǎo)的隨機(jī)游走，從各種子節(jié)點(diǎn)出發(fā)尋找附近S步數(shù)內(nèi)社團(tuán)中心性值最大的節(jié)點(diǎn)，即各種子節(jié)點(diǎn)所在的局部社團(tuán)的中心節(jié)點(diǎn)，S為可調(diào)參數(shù)；

步驟6，從各局部社團(tuán)的中心節(jié)點(diǎn)出發(fā)，挖掘出與種子節(jié)點(diǎn)在同一局部社團(tuán)的其他節(jié)點(diǎn)，并輸出各種子節(jié)點(diǎn)所在的局部社團(tuán)中的所有節(jié)點(diǎn)。

作為本發(fā)明的一種優(yōu)選方案，步驟3所述關(guān)系密度值的計(jì)算公式為：

其中，R表示節(jié)點(diǎn)的關(guān)系密度值，t表示包含該節(jié)點(diǎn)的三角環(huán)數(shù)，d表示節(jié)點(diǎn)的度數(shù)。