[發(fā)明專利]基于k核識(shí)別社交網(wǎng)絡(luò)中傾向性社區(qū)的方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202110793102.3
• 申請(qǐng)日: 2021-07-14
• 公開（公告）號(hào): CN113378077A
• 公開（公告）日: 2021-09-10
• 發(fā)明（設(shè)計(jì)）人: 盧旭峰;陳晨;張夢(mèng)琪;王瀟楊;孫仁杰
• 申請(qǐng)（專利權(quán)）人: 浙江工商大學(xué)
• 主分類號(hào): G06F16/9536
• 分類號(hào): G06F16/9536;G06Q50/00
• 代理公司: 杭州求是專利事務(wù)所有限公司 33200
• 代理人: 劉靜

1.一種基于k核識(shí)別社交網(wǎng)絡(luò)中傾向性社區(qū)的方法，其特征在于，所識(shí)別的傾向性社區(qū)為極大錨定傾斜k核，滿足三個(gè)條件：社區(qū)中任意一個(gè)頂點(diǎn)的鄰居數(shù)量需大于或等于k，即滿足k核；是極大的，即任何它的超圖都不是錨定傾斜k核；社區(qū)的傾斜分?jǐn)?shù)是最大的；該方法包括：

通過三種修剪策略過濾圖G中不必要的點(diǎn)和邊，包括：

引理1：用P(k-1)表示剝離頂點(diǎn)集合，即P(k-1)等于k-1核的頂點(diǎn)除去k核的頂點(diǎn)；給定圖G，如果一個(gè)頂點(diǎn)u被錨定，它的所有跟隨者都來自P(k-1)，所述跟隨者為原本不滿足k核，由于錨定頂點(diǎn)而留在k核中的頂點(diǎn)；

引理2：用f⁺(u)表示錨定頂點(diǎn)u得到的社區(qū)的傾斜分?jǐn)?shù)的上界，等于圖G中頂點(diǎn)u的朋友數(shù)量，這些朋友屬于u所在的連通分量；如果f⁺(u)小于等于當(dāng)前最佳社區(qū)的傾斜分?jǐn)?shù)，則不能將頂點(diǎn)u視為錨定頂點(diǎn)；

引理3：根據(jù)刪除P(k-1)中度數(shù)小于k的頂點(diǎn)時(shí)的順序，將P(k-1)中的頂點(diǎn)遞歸地劃分為不同的層，每刪除一層不滿足要求的頂點(diǎn)時(shí)，將本次刪除記為第i次刪除，刪除的頂點(diǎn)集合記為M(i)；從第一次刪除開始到最后一次刪除結(jié)束，所有刪除的頂點(diǎn)集合構(gòu)成剝離層結(jié)構(gòu)M，即M＝P(k-1)；同時(shí)，使用p(x)來表示頂點(diǎn)x的層索引，即p(x)＝i；

給定一個(gè)錨定頂點(diǎn)u，存在一條從u到頂點(diǎn)x的階梯路徑，記為u-x，其中1)這條路徑上的所有頂點(diǎn)都屬于M；2)對(duì)于沿著這條路徑的每?jī)蓚€(gè)連續(xù)頂點(diǎn)v和w，需滿足p(v)p(w)；對(duì)于給定圖G，如果對(duì)于錨定頂點(diǎn)u至少存在一條階梯路徑u-x，則u至少有一個(gè)跟隨者x；

通過極大錨定傾斜k核貪心啟發(fā)算法，進(jìn)行b輪迭代貪心得到最優(yōu)點(diǎn)集A，從而在社交網(wǎng)絡(luò)中迅速找到極大錨定傾斜k核，每一輪迭代的具體步驟如下：

(1)初始化當(dāng)前最佳社區(qū)的傾斜分?jǐn)?shù)為負(fù)無窮；計(jì)算圖G中每個(gè)頂點(diǎn)的上界分?jǐn)?shù)f⁺(u)及圖G的剝離層結(jié)構(gòu)M；

(2)根據(jù)引理3，遍歷剝離層結(jié)構(gòu)M的頂點(diǎn)，對(duì)M中的頂點(diǎn)u，判斷u是否存在一條階梯路徑，若存在則執(zhí)行步驟(3)；

(3)根據(jù)引理2，如果頂點(diǎn)u的上界分?jǐn)?shù)f⁺(u)大于當(dāng)前最佳社區(qū)的傾斜分?jǐn)?shù)α，并且u不屬于最優(yōu)點(diǎn)集A，則執(zhí)行步驟(4)，否則返回步驟(2)繼續(xù)遍歷M的下一個(gè)頂點(diǎn)；

(4)根據(jù)引理1及基于廣度優(yōu)先的輻射搜索方法，計(jì)算錨定頂點(diǎn)u的跟隨者集合，基于預(yù)設(shè)的朋友集合和敵人集合，得到跟隨者中朋友的數(shù)量f和敵人的數(shù)量e，從而計(jì)算錨定頂點(diǎn)u的傾斜分?jǐn)?shù)Score(u)＝f-e，如果Score(u)大于當(dāng)前最佳社區(qū)的傾斜分?jǐn)?shù)α，則讓?duì)恋扔赟core(u)，并將該錨定頂點(diǎn)記為u*；

(5)將得到的u*放入最優(yōu)點(diǎn)集A中，更新并返回步驟(1)開始下一輪迭代，直至完成b輪迭代找出預(yù)設(shè)的b個(gè)錨定頂點(diǎn)為止，返回b個(gè)錨定頂點(diǎn)構(gòu)成的最優(yōu)點(diǎn)集A，最終輸出錨定b個(gè)頂點(diǎn)得到的傾斜分?jǐn)?shù)最高的最佳傾向性社區(qū)。

2.根據(jù)根據(jù)權(quán)利要求1所述的一種基于k核識(shí)別社交網(wǎng)絡(luò)中傾向性社區(qū)的方法，其特征在于，所述步驟(1)包括：計(jì)算圖G的k-1核和k核，根據(jù)引理1求得剝離頂點(diǎn)集合P(k-1)，從而得到剝離層結(jié)構(gòu)M等于P(k-1)。