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

有效

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

本發(fā)明提出了一種基于(k,p)?core的快速高效社群發(fā)現(xiàn)方法，挖掘新型密集子圖模型(k,p)?core，以進行社群挖掘和網(wǎng)絡分解分析，包括以下步驟：步驟A：對網(wǎng)絡和社群進行建模；具體包括：(a)用圖結(jié)構表示網(wǎng)絡，其中每個節(jié)點代表一個實體，每條邊代表節(jié)點之間的連接關系；(b)將圖中的(k,p)?core定義為一個節(jié)點的集合，其中每個節(jié)點在這個集合中的鄰點數(shù)至少有k個，且該點在這個集合中的鄰點數(shù)占其總鄰點數(shù)的比例大于等于p；步驟B：進行(k,p)?core的分解；具體包括：對于k值從1到圖的簡并度，計算每一個節(jié)點的p值；步驟C：計算每一個k，p值對，并使用索引進行存儲，便于查詢。

技術領域

本發(fā)明涉及圖網(wǎng)絡數(shù)據(jù)上的社群發(fā)掘技術領域，為一種基于(k,p)-core的快速高效社群發(fā)現(xiàn)方法及系統(tǒng)。

背景技術

圖被廣泛應用于對社交網(wǎng)絡，萬維網(wǎng)，協(xié)作網(wǎng)絡，以及生物網(wǎng)絡的建模。其中，有一類問題致力于尋找一些高度連接的點，被稱為緊密子圖的挖掘。這類問題對于圖結(jié)構的分析有著重要的作用，同時，很多緊密子圖的模型也被提出，最早被提出的模型是clique，也被稱為完全圖，它要求一個子圖中的任意兩個點之間都有一條邊。因為clique的定義十分嚴格，所以一些其他的基于clique的模型也被提出，包括，n-cliques，k-plex，quasi-clique，n-club，n-clan。以上提到的這些模型的計算都是NP難的。

同時，k-core模型的提出吸引到了更多對緊密子圖的挖掘的注意力，因為k-core模型有著優(yōu)秀的結(jié)構屬性，并且可以在線性時間內(nèi)計算完成。下面給出k-core的定義，給定一個圖，k-core被定義為這個圖上的一個子圖，且在這個子圖中，每個點都要至少與k個其他的點相連接。k-core在許多實際問題中得到了廣泛的應用，例如社區(qū)檢測，網(wǎng)絡聚類，網(wǎng)絡拓撲分析，網(wǎng)絡可視化和蛋白質(zhì)網(wǎng)絡的分析。K-core在圖論界也是非常受歡迎的，它可以作為解決困難的問題的子問題，如n-cliques的計算。最近的研究表明，一個圖中點的效用隨時間的增加或減少主要基于的是它與社區(qū)中其他點的連接數(shù)，這使得k-core成為理解和解釋用戶參與度，用戶合作過程和社交網(wǎng)絡中的信息傳播的強大工具。

在最近的社會科學著作中指出，用戶的度越大，在這個網(wǎng)絡中，他就需要更多的朋友/鄰居采取某個行動，使他也能采取同樣的行動。K-core模型分配一個統(tǒng)一閾值的k給圖中的所有頂點，因此，這個模型并不能表明，一個度較大的頂點只有在其多數(shù)鄰點成員的參加某個活動的情況下才加入這個活動。

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

本發(fā)明的目的是為了解決現(xiàn)有技術的缺陷，提供了一種基于(k,p)-core的快速高效社群發(fā)現(xiàn)方法，挖掘新型密集子圖模型(k,p)-core，以進行社群挖掘和網(wǎng)絡分解分析，包括以下步驟：

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

(a)用圖結(jié)構表示網(wǎng)絡，其中每個節(jié)點代表一個實體，每條邊代表節(jié)點之間的連接關系，；(b)將圖中的(k,p)-core定義為一個節(jié)點的集合，其中每個節(jié)點在這個集合中的鄰點數(shù)至少有k個，且他在這個集合中的鄰點數(shù)占總鄰點數(shù)的比例大于等于p。

步驟B：進行(k,p)-core的分解；具體包括：對于k值從1到圖的簡并度，計算每一個節(jié)點的p值。

具體做法為，首先對圖中所有的點做k-core的分解，然后對k值從1到圖的簡并度，每次計算一個p的最小值，從圖中刪掉這個點把其p值設為當前計算的值，依次刪除其他不滿足k值和p值要求的點，再計算下一個最小p值。

步驟C：計算每一個k，p值對，并使用索引進行存儲，便于查詢；具體包括：

計算每一個k值以及其計算過程中產(chǎn)生的p值對，并對其中的點進行索引。

本發(fā)明提出的基于(k,p)-core的快速高效社群發(fā)現(xiàn)方法，在給定k和p時，設計了一個時間復雜度為O(|G|)的算法來計算(k,p)-core，其中|G|是圖G中的頂點和邊的數(shù)量。