[發(fā)明專利]基于動力距離更新的社區(qū)檢測方法

在審

• 申請?zhí)枺?/td>: 201711403013.3
• 申請日: 2017-12-22
• 公開（公告）號: CN108280771A
• 公開（公告）日: 2018-07-13
• 發(fā)明（設(shè)計）人: 黃健斌;邊青全;周瑜
• 申請（專利權(quán)）人: 西安電子科技大學(xué)
• 主分類號: G06Q50/00
• 分類號: G06Q50/00
• 代理公司: 陜西電子工業(yè)專利中心 61205
• 代理人: 田文英;王品華

1.一種基于動力同步距離更新的社區(qū)檢測方法，其特征在于，該方法將每次迭代過程中每條邊的距離與社會網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)計算得到的值，作為下次迭代每條邊的距離，屬于同一社區(qū)的節(jié)點之間邊的距離會動態(tài)縮短，不屬于同一社區(qū)的節(jié)點之間邊的距離會動態(tài)增長，該方法包括如下步驟：

(1)構(gòu)建社會網(wǎng)絡(luò)：

(1a)將社交關(guān)系中的每一個用戶作為社會網(wǎng)絡(luò)中的一個對應(yīng)節(jié)點，并賦予一個唯一的節(jié)點標(biāo)號；

(1b)將社交關(guān)系中兩個用戶之間的關(guān)系作為社會網(wǎng)絡(luò)中對應(yīng)的邊，從而構(gòu)建出社會網(wǎng)絡(luò)中節(jié)點與節(jié)點之間連接的拓?fù)浣Y(jié)構(gòu)；

(2)初始化社會網(wǎng)絡(luò)中的社區(qū)：

將社會網(wǎng)絡(luò)中的每個節(jié)點初始化為一個對應(yīng)的社區(qū)，并且將節(jié)點標(biāo)號作為社區(qū)標(biāo)號；

(3)初始化社會網(wǎng)絡(luò)中相鄰節(jié)點之間邊的距離：

根據(jù)社會網(wǎng)絡(luò)中的拓?fù)浣Y(jié)構(gòu)，使用Jaccard距離計算公式，計算社會網(wǎng)絡(luò)中每條邊的距離，將計算的結(jié)果作為社會網(wǎng)絡(luò)中每條邊的初始距離；

(4)合并與分裂社區(qū)：

(4a)將社會網(wǎng)絡(luò)中的所有距離不大于0的邊的兩個端點所在的社區(qū)合并為一個社區(qū)；

(4b)將社會網(wǎng)絡(luò)中所有距離不小于1的邊的兩個端點所在的社區(qū)分裂開來；

(5)更新社會網(wǎng)絡(luò)中每條邊的距離：

(5a)對于社會網(wǎng)絡(luò)中距離介于0到1之間的每一條邊，將與其相鄰的所有節(jié)點分成三類集合；

(5b)根據(jù)當(dāng)前迭代過程中每條邊的距離，分別計算每類集合分別對每條邊距離產(chǎn)生的影響；

(5c)將三類集合分別對每條邊距離產(chǎn)生的影響與當(dāng)前迭代過程中每條邊的距離相加，用相加后的結(jié)果更新每條邊的距離；

(6)判斷社會網(wǎng)絡(luò)中每條邊的距離是否全部更新為0或者1，若是，則執(zhí)行步驟(7)；否則，執(zhí)行步驟(4)；

(7)確定最終社區(qū)：

求社會網(wǎng)路中所有距離為0的邊所構(gòu)成的最大聯(lián)通分量，將每一個最大聯(lián)通分量作為一個最終的社區(qū)。

2.根據(jù)權(quán)利要求1所述的基于動力同步距離更新的社區(qū)檢測方法，其特征在于，步驟(3)中所述的Jaccard距離計算公式如下：

其中，d(x,y)表示社會網(wǎng)絡(luò)中第x個節(jié)點與其相鄰的第y個節(jié)點所構(gòu)成邊的距離；N(x)表示由社會網(wǎng)絡(luò)中第x個節(jié)點與第x個節(jié)點相鄰的所有節(jié)點構(gòu)成的集合；N(y)表示由社會網(wǎng)絡(luò)中第y個節(jié)點與第y個節(jié)點相鄰的所有節(jié)點構(gòu)成的集合；∩表示求交集操作；∪表示求并集操作；| |表示求集合中元素的個數(shù)操作。

3.根據(jù)權(quán)利要求1所述的基于動力同步距離更新的社區(qū)檢測方法，其特征在于，步驟(4a)中所述的將社會網(wǎng)絡(luò)中的所有距離不大于0的邊的兩個端點所在的社區(qū)合并為一個社區(qū)是指，將所有位于上述邊的兩個端點所在社區(qū)之間的邊的距離置為0，將所含節(jié)點個數(shù)較少的社區(qū)內(nèi)的節(jié)點社區(qū)標(biāo)號改為所含節(jié)點個數(shù)較多的社區(qū)內(nèi)的節(jié)點社區(qū)標(biāo)號，以此合并兩個社區(qū)為同一個社區(qū)。

4.根據(jù)權(quán)利要求1所述的基于動力同步距離更新的社區(qū)檢測方法，其特征在于，步驟(4b)中所述的將社會網(wǎng)絡(luò)中所有距離不小于1的邊的兩個端點所在的社區(qū)分裂開來是指，將所有位于上述邊的兩個端點所在社區(qū)之間的邊的距離置為1。

5.根據(jù)權(quán)利要求1所述的基于動力同步距離更新的社區(qū)檢測方法，其特征在于，步驟(5a)中所述的三類集合是指，直接鄰居集合，公共鄰居集合，獨家鄰居集合三類集合；其中，

所述的直接鄰居集合是指社會網(wǎng)絡(luò)中每一條邊的兩個端點構(gòu)成的集合；

所述的公共鄰居集合是指同時與社會網(wǎng)絡(luò)中每一條邊的兩個端點都相鄰的所有節(jié)點構(gòu)成的集合；

所述的獨家鄰居集合是指與社會網(wǎng)絡(luò)中每一條邊的兩個端點中的一個端點相鄰，但與另一個不相鄰的所有節(jié)點構(gòu)成的集合。