[發(fā)明專利]一種社交網(wǎng)絡(luò)重要用戶發(fā)現(xiàn)的實(shí)現(xiàn)方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201510732810.0
• 申請(qǐng)日: 2015-10-30
• 公開（公告）號(hào): CN105335892A
• 公開（公告）日: 2016-02-17
• 發(fā)明（設(shè)計(jì)）人: 朱梓嫣;顧亦然;孟繁榮
• 申請(qǐng)（專利權(quán)）人: 南京郵電大學(xué)
• 主分類號(hào): G06Q50/00
• 分類號(hào): G06Q50/00
• 代理公司: 南京知識(shí)律師事務(wù)所 32207
• 代理人: 汪旭東

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

本發(fā)明涉及一種社交網(wǎng)絡(luò)重要用戶發(fā)現(xiàn)的實(shí)現(xiàn)方法，屬于網(wǎng)絡(luò)通信技術(shù)領(lǐng)域。

背景技術(shù)

重要節(jié)點(diǎn)是相比網(wǎng)絡(luò)中其他節(jié)點(diǎn)而言，對(duì)整個(gè)網(wǎng)絡(luò)的結(jié)構(gòu)和功能夠能產(chǎn)生巨大作用的少量節(jié)點(diǎn)。近年來(lái)，學(xué)者在重要節(jié)點(diǎn)排序上提出了很多指標(biāo)和算法，主要有以下幾個(gè)方面：1.基于節(jié)點(diǎn)鄰居節(jié)點(diǎn)的排序方法，如在文獻(xiàn)BonacichP《Factoringandweightingapproachestostatusscoresandcliqueidentification》(JournalofMathematicalSociology.1972,2(1):113-120)提出度中心性(degreecentrality)，即節(jié)點(diǎn)的鄰居節(jié)點(diǎn)越多其影響力越大，其缺點(diǎn)是僅僅考慮了節(jié)點(diǎn)的局部信息；2.基于路徑的排序方法，如文獻(xiàn)FreemanLC《Centralityinsocialnetworksconceptualclarification》(SocialNetworks,1978,1(3):215–239)提出接近中心性(closenesscentrality)，通過(guò)計(jì)算節(jié)點(diǎn)與網(wǎng)絡(luò)中其他所有節(jié)點(diǎn)距離平均值來(lái)衡量節(jié)點(diǎn)的重要性，缺點(diǎn)是時(shí)間復(fù)雜度比較高；3.基于特征向量的排序方法，如文獻(xiàn)BrinS《TheAnatomyofaLarge-ScaleHypertextualWebSearchEngine》(ComputerNetworks&IsdnSystems,1998,30(98):107–117)提出PageRank算法，該算法認(rèn)為每一個(gè)節(jié)點(diǎn)的重要性取決于指向它的其他節(jié)點(diǎn)的數(shù)量和質(zhì)量，缺點(diǎn)是容易陷入懸掛節(jié)點(diǎn)。文獻(xiàn)LüL《LeadersinSocialNetworks,theDeliciousCase》(PlosOne,2011,6(6):e21202)和文獻(xiàn)LiQ《IdentifyinginfluentialspreadersbyweightedLeaderRank》(PhysicaAStatisticalMechanics&ItsApplications,2014,404(24):47-55)提出LeaderRank算法在PageRank算法的基礎(chǔ)上，通過(guò)加入了一個(gè)背景節(jié)點(diǎn)，該節(jié)點(diǎn)與網(wǎng)絡(luò)的所有節(jié)點(diǎn)雙向連接，來(lái)替代PageRank算法中跳轉(zhuǎn)概率s，從而提高了算法的收斂速度和魯棒性。4.基于節(jié)點(diǎn)的移除和收縮的排序方法,通過(guò)移除節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)的破壞性來(lái)衡量節(jié)點(diǎn)的重要性，但其計(jì)算復(fù)雜度高。現(xiàn)有的算法大多考慮節(jié)點(diǎn)在全局中的重要性或者局部重要性，忽略了節(jié)點(diǎn)間相互作用對(duì)整個(gè)網(wǎng)絡(luò)的影響。

SIR模型是傳染病模型中最經(jīng)典的模型，其中S代表易感者(Susceptible)，指未得病者，但缺乏免疫力，與感染者接觸后容易收到感染；I代表感染者(Infective)，指染上傳染病的人，它可以傳播給S類成員；R代表移除者(Removal)，指，指被隔離，或因病愈而具有免疫力的人。通常使用SIR傳播模型，來(lái)驗(yàn)證重要節(jié)點(diǎn)排序算法的有效性。一般情況下，所選擇節(jié)點(diǎn)的傳播速度越快，即一定時(shí)間內(nèi)I狀態(tài)節(jié)點(diǎn)個(gè)數(shù)增長(zhǎng)速度越快，節(jié)點(diǎn)越重要。而本發(fā)明能夠很好地解決上面的問(wèn)題。

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

本發(fā)明目的在于克服上述現(xiàn)有方法的不足，提供一種社交網(wǎng)絡(luò)重要用戶發(fā)現(xiàn)的實(shí)現(xiàn)方法，該方法基于LeaderRank算法和節(jié)點(diǎn)相似度的重要節(jié)點(diǎn)發(fā)現(xiàn)算法，提高網(wǎng)絡(luò)的魯棒性，減少迭代次數(shù)，并且可以解決如PageRank算法在節(jié)點(diǎn)隨機(jī)游走的情況下陷入懸掛節(jié)點(diǎn)的問(wèn)題。

本發(fā)明解決其技術(shù)問(wèn)題所采取的技術(shù)方案是：本發(fā)明應(yīng)用于社交網(wǎng)絡(luò)關(guān)注關(guān)系的網(wǎng)絡(luò)下，對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)進(jìn)行重要度排序，其直接的目的不是動(dòng)態(tài)的抓取網(wǎng)絡(luò)中的重要節(jié)點(diǎn)。本發(fā)明的方法結(jié)合現(xiàn)有的社交網(wǎng)絡(luò)，不是動(dòng)態(tài)的抓取現(xiàn)有的社交網(wǎng)絡(luò)中的關(guān)注關(guān)系，給出重要節(jié)點(diǎn)。

本發(fā)明的方法是基于固有的社交網(wǎng)絡(luò)，并采用MATLAB平臺(tái)作為可視化軟件，將網(wǎng)絡(luò)的重要節(jié)點(diǎn)排序結(jié)果給出。

本發(fā)明在計(jì)算節(jié)點(diǎn)重要度時(shí)，充分考慮節(jié)點(diǎn)的全局和局部特征，考慮節(jié)點(diǎn)對(duì)相互作用的力度不同，即存在親疏遠(yuǎn)近的關(guān)系，從而給出重要度計(jì)算方法。

方法流程：

步驟1：對(duì)要求分析的社交網(wǎng)絡(luò)通過(guò)關(guān)注關(guān)系構(gòu)建信息收聽網(wǎng)絡(luò)Aij，采用LeaderRank算法，計(jì)算得到每個(gè)節(jié)點(diǎn)的全局重要度；

步驟2：采用定義的相似度計(jì)算兩兩節(jié)點(diǎn)的相似度，作為節(jié)點(diǎn)局部相互作用；

步驟3：采用SimRank算法，計(jì)算得到節(jié)點(diǎn)的重要度，對(duì)其進(jìn)行排序；

步驟4：采用SIR傳播模型，對(duì)比其他經(jīng)典算法，驗(yàn)證有效性。