[發(fā)明專利]一種選取種子節(jié)點的合著網(wǎng)絡(luò)社區(qū)劃分方法

在審

• 申請?zhí)枺?/td>: 201710166346.2
• 申請日: 2017-03-20
• 公開（公告）號: CN107103551A
• 公開（公告）日: 2017-08-29
• 發(fā)明（設(shè)計）人: 吳渝;常雨簫;李紅波;艾偉東
• 申請（專利權(quán)）人: 重慶郵電大學(xué)
• 主分類號: G06Q50/00
• 分類號: G06Q50/00
• 代理公司: 重慶市恒信知識產(chǎn)權(quán)代理有限公司50102
• 代理人: 劉小紅

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

本發(fā)明涉及學(xué)術(shù)作者權(quán)威度和社區(qū)劃分領(lǐng)域，具體是一種能夠展示復(fù)雜合著網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的社區(qū)劃分算法。

背景技術(shù)

1994年以來，IEEE和ACM等大型數(shù)字圖書館出現(xiàn)以來，國內(nèi)外的一些學(xué)者就開始關(guān)注和研究合著網(wǎng)絡(luò)。其主要原因在于：對合著網(wǎng)絡(luò)的當(dāng)前狀態(tài)和結(jié)構(gòu)進(jìn)行觀察可以提供許多有價值的數(shù)據(jù)。合著網(wǎng)絡(luò)屬于一種典型的社會復(fù)雜網(wǎng)絡(luò)，它具有其擁有的一些結(jié)構(gòu)特征，如小世界特征、網(wǎng)絡(luò)中存在內(nèi)聚傾向以及無標(biāo)度特征等等。因此，一些分析社會復(fù)雜網(wǎng)絡(luò)的工具和方法同樣可應(yīng)用于合著網(wǎng)絡(luò)，以深入挖掘合著網(wǎng)絡(luò)潛藏的有用信息。這些工具和方法已成為當(dāng)前研究合著網(wǎng)絡(luò)的主要手段。

錢振華等人在《北京科技大學(xué)學(xué)報》第27卷第4期提出一種合著網(wǎng)絡(luò)中的社區(qū)劃分方法，以若干個不同的局部帶有影響力的節(jié)點為核心，并使節(jié)點的影響力從核心逐層向外均勻擴(kuò)散，最終形成了以影響力最大的節(jié)點為核心，逐層擴(kuò)展中節(jié)點的影響力不斷衰減，它們之間相互關(guān)聯(lián)形成一個局部區(qū)域，擴(kuò)展到方法的停止，節(jié)點影響力很小，到達(dá)該局部區(qū)域的網(wǎng)絡(luò)邊緣。該文章提出的方法，僅有的一個劃分階段導(dǎo)致節(jié)點之間存在過度合并的現(xiàn)象，且社區(qū)劃分中逐層擴(kuò)展的做法導(dǎo)致迭代時間過長，算法效率也很低。

申請?zhí)枮?01410650818.8的中國專利描述了一種基于層次聚類的復(fù)雜網(wǎng)絡(luò)社區(qū)劃分方法，從全局中心節(jié)點建立初始社區(qū)，再根據(jù)聯(lián)系緊密程度一層一層地擴(kuò)展社區(qū)，最后把一些過小的社區(qū)融合到大社區(qū)中。初始化社區(qū)過程為：選取度數(shù)最大的k個節(jié)點，按照節(jié)點的相似度合成若干個社區(qū)。擴(kuò)展社區(qū)過程首先標(biāo)記所有節(jié)點的層數(shù)，然后根據(jù)節(jié)點與社區(qū)的鏈接強(qiáng)度把節(jié)點分到相應(yīng)的社區(qū)中。融合小社區(qū)過程首先要確定小社區(qū)的大小，計算小社區(qū)中的每個節(jié)點v的相鄰節(jié)點與每個大社區(qū)C的公共節(jié)點個數(shù)，將v重新劃分到公共節(jié)點數(shù)最大的社區(qū)中。選取最優(yōu)結(jié)果過程要做10次試驗，根據(jù)擴(kuò)展模塊度選出最終結(jié)果。本發(fā)明不需要預(yù)先知道社區(qū)數(shù)目，時間復(fù)雜度為O(m)，可以處理大型復(fù)雜網(wǎng)絡(luò)，提高了社區(qū)劃分的準(zhǔn)確度。但是，該專利只能泛性的分析復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，沒有針對不同種類復(fù)雜網(wǎng)絡(luò)精確挑選包含重要社區(qū)結(jié)構(gòu)信息的節(jié)點進(jìn)行劃分，最終的劃分結(jié)果無法準(zhǔn)確反映不同種類的社交網(wǎng)絡(luò)中的社交行為。

現(xiàn)有的合著網(wǎng)絡(luò)社區(qū)劃分方法存在以下缺點：(1)沒有結(jié)合合著網(wǎng)絡(luò)中的特性進(jìn)行深度的社區(qū)劃分研究；(2)算法效率低，運行時間長。

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

本發(fā)明旨在解決以上現(xiàn)有技術(shù)的問題。提出了一種算法效率提高的方法。本發(fā)明的技術(shù)方案如下：

一種選取種子節(jié)點的合著網(wǎng)絡(luò)社區(qū)劃分方法，其包括以下步驟：首先，根據(jù)作者各自發(fā)表的文章數(shù)和合著發(fā)表文章數(shù)，采用薩頓法計算作者之間的合作強(qiáng)度，將計算得出的合作強(qiáng)度值賦值給節(jié)點之間的邊，構(gòu)建合著網(wǎng)絡(luò)，其中每個作者作為合著網(wǎng)絡(luò)的節(jié)點；其次，根據(jù)作者之間的合作強(qiáng)度計算節(jié)點的學(xué)術(shù)社團(tuán)中心度，其中不單考慮作者自身權(quán)威度，還考慮了相鄰的學(xué)者對其的影響；最后，根據(jù)節(jié)點的學(xué)術(shù)社團(tuán)中心度作為選取種子節(jié)點的依據(jù)，采用改進(jìn)的社區(qū)發(fā)現(xiàn)算法，在改進(jìn)的社區(qū)發(fā)現(xiàn)算法的階段一與魯文算法的階段一相同，結(jié)果為網(wǎng)絡(luò)圖G中的節(jié)點最終被劃分成社區(qū)集合C；并將其融入到Louvain社區(qū)劃分算法的第二階段，即種子節(jié)點間不進(jìn)行合并，非種子節(jié)點應(yīng)盡量合并到種子節(jié)點所屬的社區(qū)。

進(jìn)一步的，所述采用Salton法計算作者之間的合作關(guān)系強(qiáng)度，將計算得出的值賦值給節(jié)點之間的邊，構(gòu)建合著網(wǎng)絡(luò)，合作關(guān)系強(qiáng)度公式如下：

式中，rs_ij為作者i和作者j的合作關(guān)系強(qiáng)度，h_ij為作者i和作者j合作發(fā)表的文章數(shù)，h_i和h_j分別表示作者i和作者j各自發(fā)表的文章數(shù)。

進(jìn)一步的，所述根據(jù)作者之間的合作強(qiáng)度計算節(jié)點的學(xué)術(shù)社團(tuán)中心度包括：

根據(jù)計算出的作者合作強(qiáng)度，根據(jù)以下公式計算節(jié)點的學(xué)術(shù)社團(tuán)中心度：

CD(i)＝(1-d)*deg(i)+d∑_jrs_ij*CD(j)*w(i，j)

式中，CD(i)為節(jié)點i的學(xué)術(shù)社團(tuán)中心度，deg(i)為節(jié)點i的度數(shù)，rs_ij為節(jié)點i和j間的合作強(qiáng)度，w(i，j)為節(jié)點j對節(jié)點i的權(quán)威貢獻(xiàn)程度，d表示收斂系數(shù)。

進(jìn)一步的，所述Louvain社區(qū)劃分算法的第二階段具體包括步驟：