[發(fā)明專利]一種基于社區(qū)度和結(jié)構(gòu)洞的影響力最大化方法

在審

• 申請?zhí)枺?/td>: 202110890795.8
• 申請日: 2021-08-04
• 公開（公告）號: CN113592663A
• 公開（公告）日: 2021-11-02
• 發(fā)明（設(shè)計）人: 許國艷;莊天益;黃靜;張琦睿
• 申請（專利權(quán)）人: 河海大學(xué)
• 主分類號: G06Q50/00
• 分類號: G06Q50/00;G06Q10/04
• 代理公司: 南京蘇高專利商標事務(wù)所(普通合伙) 32204
• 代理人: 張華蒙

本發(fā)明公開了一種基于社區(qū)度和結(jié)構(gòu)洞的影響力最大化方法，屬于社區(qū)邊界節(jié)點篩選技術(shù)領(lǐng)域，該方法包括：根據(jù)社區(qū)聚集系數(shù)劃分社區(qū)，識別并選取社區(qū)間的邊界連接節(jié)點；(1)在社區(qū)內(nèi)部：篩選部分種子節(jié)點，以網(wǎng)絡(luò)效率反映的聯(lián)通效率和節(jié)點自身度中心性以及受關(guān)注節(jié)點提升的影響力，共同衡量節(jié)點的最終影響力，以此來篩選種子節(jié)點；(2)在社區(qū)邊界：從邊界點中篩選剩余部分的種子節(jié)點，算法在篩選社區(qū)邊界節(jié)點中的種子節(jié)點時，在基于社區(qū)度的評價標準中加入了改進的結(jié)構(gòu)洞評價指標，提高篩選節(jié)點的準確性。本發(fā)明的益處是降低了算法的時間復(fù)雜度，對于影響力不大但處于重要位置的節(jié)點篩選更有針對性。

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

本發(fā)明屬于社區(qū)邊界節(jié)點篩選技術(shù)領(lǐng)域，具體涉及一種基于社區(qū)度和結(jié)構(gòu)洞 的影響力最大化方法。

背景技術(shù)

隨著信息化進程的加快，社交網(wǎng)絡(luò)中的數(shù)據(jù)規(guī)模將會對節(jié)點篩選操作造成極 大的阻礙，將社交網(wǎng)絡(luò)分區(qū)處理必將成為主流，而當前大部分算法在選取社區(qū)的 邊界節(jié)點時參考要素簡單，未能根據(jù)節(jié)點連接社區(qū)數(shù)量以及自身在社交網(wǎng)絡(luò)中的 拓撲位置。

早期基于社區(qū)結(jié)構(gòu)來解決IM問題，主要考慮的是兩個稀疏的網(wǎng)絡(luò)，因而對 于大規(guī)模的密集網(wǎng)絡(luò)處理效果不夠理想。從社區(qū)角度出發(fā)，挖掘社區(qū)影響力并進 行排序，之后再從個體角度出發(fā)在社區(qū)內(nèi)部篩選不同數(shù)量的種子節(jié)點數(shù)，篩選數(shù) 量通過社區(qū)規(guī)模在總網(wǎng)絡(luò)比例計算，這樣篩選出的種子節(jié)點僅僅考慮了社區(qū)內(nèi)部 的種子節(jié)點，未考慮影響力不大但連接多個社區(qū)的節(jié)點。考慮到邊界節(jié)點中存在 重要種子節(jié)點，用邊界節(jié)點連接社區(qū)數(shù)目來判斷節(jié)點的影響力。通過結(jié)合邊界節(jié) 點度、邊界節(jié)點連接的社區(qū)數(shù)和社區(qū)規(guī)模三個要素，將社區(qū)度作為評判節(jié)點影響 力大小的標準，但是該評判標準過度強調(diào)邊界節(jié)點的作用，且在后續(xù)的篩選種子 節(jié)點中使用貪心算法導(dǎo)致耗時巨大。

為了能夠在劃分后的社區(qū)中選取更加精準的種子節(jié)點，將劃分后的社區(qū)網(wǎng)絡(luò) 類比為資源分配問題，但是該算法卻忽略了社區(qū)間的連通性，從而導(dǎo)致篩選出的 節(jié)點各自獨立，在信息傳播中無法達到最大影響力范圍。如何選取社區(qū)的核心節(jié) 點和社區(qū)間的邊界節(jié)點，同時考慮節(jié)點對于整體網(wǎng)絡(luò)的作用，避免社區(qū)間節(jié)點的 孤立，是社區(qū)影響力研究的重要課題。

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

發(fā)明目的：針對現(xiàn)有技術(shù)中的不足，本發(fā)明提供了一種基于社區(qū)度和結(jié)構(gòu)洞 的影響力最大化方法，用于解決篩選種子節(jié)點時遺漏節(jié)點影響力不高卻有著連通 社區(qū)功能的社區(qū)邊界節(jié)點的問題。

技術(shù)方案：為實現(xiàn)上述發(fā)明目的，本發(fā)明的技術(shù)方案如下：一種基于社區(qū)度 和結(jié)構(gòu)洞的影響力最大化方法，包括如下步驟：

(1)社區(qū)劃分：將初始社交網(wǎng)絡(luò)定義為G(V,E)，定義社區(qū)個數(shù)為S作為初 始的種子節(jié)點集；根據(jù)社區(qū)聚集系數(shù)劃分社區(qū)，識別并選取社區(qū)間的邊界連接節(jié) 點；

(2)社區(qū)內(nèi)種子節(jié)點篩選：在社區(qū)內(nèi)部：通過算法篩選部分種子節(jié)點，以 網(wǎng)絡(luò)效率反映的聯(lián)通效率和節(jié)點自身度中心性以及受關(guān)注節(jié)點提升的影響力，共 同衡量節(jié)點的最終影響力，以此來篩選種子節(jié)點；

(3)社區(qū)邊界種子節(jié)點篩選：從邊界點中篩選剩余部分的種子節(jié)點，算法 在篩選社區(qū)邊界節(jié)點中的種子節(jié)點時，在基于社區(qū)度的評價標準中加入了改進的 結(jié)構(gòu)洞評價指標，用以提高篩選節(jié)點的準確性，并將兩次篩選的種子節(jié)點合并加 入到最終的種子節(jié)點集合；

(4)選取種子節(jié)點；若在網(wǎng)絡(luò)中選取k個節(jié)點，在社區(qū)中選取的種子節(jié)點 數(shù)為(k×α)，選取k′個影響力最高的社區(qū)邊界種子節(jié)點，則k′＝k-k×α，社區(qū) 中選取的種子節(jié)點和社區(qū)邊界選取的種子節(jié)點共同構(gòu)成種子節(jié)點集。

進一步地，所述的步驟(1)，包括如下步驟：

步驟1.1：社區(qū)的劃分以社區(qū)的聚集系數(shù)作為參考標準，社區(qū)的聚集系數(shù)取 決于該社區(qū)內(nèi)所有節(jié)點的聚集系數(shù)的和除以社區(qū)節(jié)點數(shù)的比值；社區(qū)的聚集系數(shù)：

g(i)為節(jié)點的聚集系數(shù)，公式為：