[發(fā)明專利]基于最小生成樹的社交網(wǎng)絡(luò)層次化社區(qū)發(fā)現(xiàn)方法及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201810320793.3
• 申請日: 2018-04-10
• 公開（公告）號: CN108737158B
• 公開（公告）日: 2021-09-28
• 發(fā)明（設(shè)計）人: 王志曉;牛強;袁冠;席景科;孟凡榮;芮曉彬;侯夢男
• 申請（專利權(quán)）人: 中國礦業(yè)大學
• 主分類號: H04L12/24
• 分類號: H04L12/24;G06Q50/00
• 代理公司: 北京天達知識產(chǎn)權(quán)代理事務所(普通合伙) 11386
• 代理人: 龔頤雯;龐許倩

本發(fā)明涉及一種基于最小生成樹的社交網(wǎng)絡(luò)層次社區(qū)發(fā)現(xiàn)方法及系統(tǒng)，屬于網(wǎng)絡(luò)分析技術(shù)領(lǐng)域，通過計算給定社交網(wǎng)絡(luò)所有相鄰節(jié)點間連接強度來構(gòu)建微社區(qū)；計算所有微社區(qū)間的緊密度，構(gòu)造最小生成樹，得到社交網(wǎng)絡(luò)的層次社區(qū)結(jié)構(gòu)。本發(fā)明的最小生成樹構(gòu)造復雜度低，能夠有效處理大規(guī)模社交網(wǎng)絡(luò)數(shù)據(jù)，無需任何人為參數(shù)設(shè)置，能夠準確、高效地發(fā)現(xiàn)社交網(wǎng)絡(luò)的層次社區(qū)結(jié)構(gòu)。

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

本發(fā)明涉及網(wǎng)絡(luò)分析技術(shù)領(lǐng)域，尤其是一種基于最小生成樹的社交網(wǎng)絡(luò)層次化社區(qū)發(fā)現(xiàn)方法及系統(tǒng)。

背景技術(shù)

社區(qū)發(fā)現(xiàn)是社交網(wǎng)絡(luò)分析的一項重要內(nèi)容，對于分析社交網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，理解復雜系統(tǒng)的功能，發(fā)現(xiàn)社交網(wǎng)絡(luò)中的隱藏規(guī)律、演化趨勢以及預測社交網(wǎng)絡(luò)的行為等都具有重要的意義。真實社交網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)往往呈現(xiàn)出顯著的層次性，大的社區(qū)內(nèi)部可以包含小的社區(qū)，小社區(qū)可以包含更小的社區(qū)。

最小生成樹法是層次社區(qū)發(fā)現(xiàn)的一個重要分支，現(xiàn)有的基于最小生成樹的層次社區(qū)發(fā)現(xiàn)方法存在以下不足：(1)構(gòu)造最小生成樹的時間復雜度為O(nlogn)，復雜度較高，不適合大規(guī)模網(wǎng)絡(luò)。(2)需要事先設(shè)定多個控制參數(shù)，不同的參數(shù)設(shè)置導致不同的結(jié)果，給社交網(wǎng)絡(luò)層次社區(qū)劃分帶來了不確定性。

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

鑒于上述的分析，本發(fā)明旨在提供一種基于最小生成樹的社交網(wǎng)絡(luò)層次化社區(qū)發(fā)現(xiàn)方法及系統(tǒng)，解決現(xiàn)有基于最小生成樹的社交網(wǎng)絡(luò)層次社區(qū)發(fā)現(xiàn)方法中存在的最小生成樹構(gòu)造時間復雜度高以及需要人為設(shè)定多個參數(shù)等問題。

本發(fā)明的目的主要是通過以下技術(shù)方案實現(xiàn)的：

一種基于最小生成樹的社交網(wǎng)絡(luò)層次社區(qū)發(fā)現(xiàn)方法，包括：

計算給定社交網(wǎng)絡(luò)所有相鄰節(jié)點間的連接強度；

根據(jù)相鄰節(jié)點間的連接強度構(gòu)建微社區(qū)；

計算所有微社區(qū)間的緊密度；

構(gòu)造最小生成樹，得到社交網(wǎng)絡(luò)的層次社區(qū)結(jié)構(gòu)。

進一步地，所述節(jié)點間連接強度的計算公式為：

其中，Sim_node(i,j)為節(jié)點i與相鄰節(jié)點j之間的連接強度，Γ(i)為節(jié)點i及其鄰居節(jié)點的集合，Γ(j)為節(jié)點j及其鄰居節(jié)點的集合；D(i)為節(jié)點i的度，D(j)為節(jié)點j的度。

進一步地，所述微社區(qū)的構(gòu)建包括：

從每個社交網(wǎng)絡(luò)節(jié)點的鄰居節(jié)點中選擇與所述節(jié)點連接強度最大的鄰居節(jié)點，將所述兩個節(jié)點作為密集對；

合并所有存在共同節(jié)點的密集對，直到密集對之間不存在共同節(jié)點，合并后的密集對構(gòu)成一個微社區(qū)。

進一步地，所述微社區(qū)間緊密度的計算公式為：

其中，Sim_com(c_i,c_j)為微社區(qū)c_i和c_j之間的緊密度，e(c_i,c_j)為微社區(qū)c_i和c_j之間的連接邊數(shù)，e(c_i,c_i)是微社區(qū)c_i內(nèi)部邊數(shù)，e(c_j,c_j)是微社區(qū)c_j內(nèi)部邊數(shù)，e(c_i)、e(c_j)表示微社區(qū)c_i、c_j的外部邊數(shù)。

進一步地，最小生成樹的構(gòu)造方法為Prim方法，其中，將微社區(qū)作為初始節(jié)點，微社區(qū)間緊密度的倒數(shù)作為初始節(jié)點間的權(quán)重。