[發明專利]基于k核識別社交網絡中傾向性社區的方法

在審

• 申請號: 202110793102.3
• 申請日: 2021-07-14
• 公開（公告）號: CN113378077A
• 公開（公告）日: 2021-09-10
• 發明（設計）人: 盧旭峰;陳晨;張夢琪;王瀟楊;孫仁杰
• 申請（專利權）人: 浙江工商大學
• 主分類號: G06F16/9536
• 分類號: G06F16/9536;G06Q50/00
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 劉靜

本發明公開了一種基于k核識別社交網絡中傾向性社區的方法。為了找到一個朋友更多而敵人更少的社區，本發明在錨定k核的基礎上提出了一種新的識別傾向性社區的方法，即識別極大錨定傾斜k核，它滿足三個條件：社區中任意一個頂點的鄰居數量需大于或等于k；是極大的，即任何它的超圖都不是錨定傾斜k核；社區的傾斜分數是最大的。考慮到錨定k核中頂點的朋友/敵人性質，本發明提出新的修剪策略，從而更有效地縮減搜索空間。本發明結合新的修剪策略開發了高效的KSM算法，從而能夠在大型社交網絡上快速識別到所需的錨定傾斜k核。本發明方法的應用對識別社交網絡中傾向性社區有著極大的效益，對現實生活中識別社交網絡中傾向性社區有著極大的幫助。

技術領域

本發明涉及多媒體社交網絡技術領域，尤其涉及一種基于k核識別社交網絡中傾向性社區的方法。

背景技術

在現實生活中，人們的生活離不開社交網絡，例如微博、臉書、推特之類的社交網絡在我們生活中起到了至關重要的作用。在這些社交網絡中，一些關鍵用戶的參與可以顯著影響社交網絡的穩定性。研究表明，當個人的行為受到他或她的朋友的影響時，即當他或她的朋友都這樣做時，用戶傾向于向該社交網絡分享更多內容。同樣，用戶的離開也會影響他或她的朋友參與網絡的意愿。因為一些用戶的離開可能會導致一連串的其他人離開網絡。大多數現有研究簡單地將所有用戶視為朋友，卻不管他們的屬性如何。然而，敵人在社交網絡中也無處不在。而不考慮用戶與敵人的屬性，會導致用戶的參與度下降，敵人數量增加會導致用戶不愿意參與并在該社交網絡中分享，最終會導致用戶離開。因此，傳統的錨定k核問題不適用于許多現實生活中的社交網絡。

發明內容

為了找到一個朋友更多而敵人更少的社交網絡，本發明在錨定k核的基礎上提出了一種新的識別社交網絡中傾向性社區的方法，所識別的傾向性社區為極大錨定傾斜k核，滿足三個條件：1)社區中任意一個頂點的鄰居數量需大于或等于k；2)是極大的，即任何它的超圖都不是錨定傾斜k核；3)社區的傾斜分數是最大的。考慮到錨定k核的屬性，本發明提出新的修剪策略，從而更有效地縮減搜索空間。與此同時，本發明結合新的修剪策略開發了高效的KSM算法，從而能夠在大型社交網絡上快速識別到所需的錨定傾斜k核。

本發明的目的是通過以下技術方案實現的：一種基于k核識別社交網絡中傾向性社區的方法，該方法首先通過三種修剪策略過濾圖G中不必要的點和邊，包括：

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

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

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

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

然后通過極大錨定傾斜k核貪心啟發算法，進行b輪迭代貪心得到最優點集A，從而在社交網絡中迅速找到極大錨定傾斜k核，每一輪迭代的具體步驟如下：

(1)初始化當前最佳社區的傾斜分數為負無窮；計算圖G中每個頂點的上界分數f⁺(u)及圖G的剝離層結構M；