基于中心差異度迭代調(diào)整機(jī)制的網(wǎng)絡(luò)社區(qū)搜尋算法研究

陶 碩

?

基于中心差異度迭代調(diào)整機(jī)制的網(wǎng)絡(luò)社區(qū)搜尋算法研究

陶 碩

(馬鞍山職業(yè)技術(shù)學(xué)院電子信息系，安徽，馬鞍山 243031)

為解決當(dāng)前網(wǎng)絡(luò)社區(qū)搜尋算法存在的節(jié)點(diǎn)聚類形成困難，搜尋迭代過于復(fù)雜，難以實(shí)現(xiàn)社區(qū)歸屬的二次更新等不足，提出了一種基于中心差異度迭代調(diào)整機(jī)制的網(wǎng)絡(luò)社區(qū)搜尋算法。首先，通過領(lǐng)袖節(jié)點(diǎn)重疊度來實(shí)現(xiàn)初次社區(qū)搜尋裁決，有效降低了重復(fù)搜尋的概率，且根據(jù)加入節(jié)點(diǎn)與領(lǐng)袖節(jié)點(diǎn)差異度進(jìn)行聚類匹配；隨后，通過待加入節(jié)點(diǎn)與領(lǐng)袖節(jié)點(diǎn)之間的交互熱度方式進(jìn)行基于熱度機(jī)制的聚類遞歸，實(shí)現(xiàn)對(duì)搜尋誤差的二次校正。仿真實(shí)驗(yàn)表明，與當(dāng)前網(wǎng)絡(luò)社區(qū)搜尋算法中常用的差分迭代閾值裁決機(jī)制，混沌度一體化成型迭代機(jī)制相比，本文算法具有更高的首次成功率，以及更小的搜尋次數(shù)與迭代周期，具有很強(qiáng)的實(shí)際部署價(jià)值。

網(wǎng)絡(luò)社區(qū)搜尋；節(jié)點(diǎn)聚類；領(lǐng)袖節(jié)點(diǎn)；熱度機(jī)制；聚類匹配；首次成功率

0 引言

人的本質(zhì)，不過是各種社會(huì)關(guān)系的總和，隨著大數(shù)據(jù)技術(shù)的不斷發(fā)展，這種社會(huì)關(guān)系日趨呈現(xiàn)媒體化、網(wǎng)絡(luò)化、聚類化的發(fā)展趨勢[1]?；陉P(guān)系大數(shù)據(jù)的用戶行為訪問數(shù)據(jù)常常以聚合的形式集中為網(wǎng)絡(luò)社區(qū)，這些網(wǎng)絡(luò)社區(qū)的用戶一般具有近似教育背景、類同生活習(xí)慣，常常形成特征一致的社區(qū)節(jié)點(diǎn)：區(qū)域內(nèi)節(jié)點(diǎn)聯(lián)系密切，區(qū)域外節(jié)點(diǎn)聯(lián)系稀疏；特別是在電子商務(wù)中，往往能夠起到相當(dāng)程度的商業(yè)資源發(fā)掘及流動(dòng)性提升的作用[2]。

網(wǎng)絡(luò)社區(qū)搜尋算法能夠起到迅速發(fā)掘相似社區(qū)聚類的功能，近幾年來隨著用戶大數(shù)據(jù)的崛起，研究者取得了相當(dāng)多的研究成果。Zeng等人[3]基于領(lǐng)袖節(jié)點(diǎn)聚類發(fā)掘機(jī)制，提出了一種嶄新的網(wǎng)絡(luò)社區(qū)搜尋算法，該機(jī)制通過周期性挖掘的方式，不斷歸納當(dāng)前網(wǎng)絡(luò)社區(qū)中的熱點(diǎn)，且將相似熱度的熱點(diǎn)進(jìn)行自適應(yīng)聚類建模，能夠迅速地刷新網(wǎng)絡(luò)熱點(diǎn)，并構(gòu)建基于領(lǐng)袖節(jié)點(diǎn)的社區(qū)聚類，具有實(shí)現(xiàn)機(jī)制簡便易行的特點(diǎn)。但該算法需要對(duì)網(wǎng)絡(luò)中幾乎全部節(jié)點(diǎn)進(jìn)行信息捕捉，難以適應(yīng)節(jié)點(diǎn)數(shù)目動(dòng)態(tài)變化的情形。Zhang等人[4]基于分層聚類算法，提出了一種基于分層重疊機(jī)制的網(wǎng)絡(luò)社區(qū)搜尋算法，該算法通過隨機(jī)選取初始熱點(diǎn)的方式，根據(jù)分層算法進(jìn)行分叉擴(kuò)張，直到網(wǎng)絡(luò)負(fù)載達(dá)到固定差異度為止，具有管理便捷且收斂速度較快的特點(diǎn)。但是，該算法對(duì)網(wǎng)絡(luò)搜尋精度要求較高，若初始熱點(diǎn)選取出現(xiàn)失誤，則極易發(fā)生分層分叉故障，導(dǎo)致得到的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)出現(xiàn)嚴(yán)重的混亂。Wang等人[5]鑒于直接分叉容易出現(xiàn)的失誤現(xiàn)象，提出了一種基于標(biāo)簽-鄰居節(jié)點(diǎn)糾錯(cuò)機(jī)制的網(wǎng)絡(luò)社區(qū)搜尋算法，該算法主要通過定義正確-失誤標(biāo)簽，并默認(rèn)相鄰節(jié)點(diǎn)與本節(jié)點(diǎn)具有強(qiáng)相關(guān)聯(lián)的特性，實(shí)現(xiàn)對(duì)錯(cuò)誤分叉進(jìn)行自糾，具有搜尋精確度高的特性。然而該算法實(shí)現(xiàn)機(jī)理比較復(fù)雜，社區(qū)節(jié)點(diǎn)數(shù)量較多時(shí)將很難起到應(yīng)有的收斂程度。

針對(duì)當(dāng)前常見算法存在的不足，設(shè)計(jì)了一種基于中心差異度迭代調(diào)整機(jī)制的網(wǎng)絡(luò)社區(qū)搜尋算法。該算法由兩個(gè)部分構(gòu)成：通過獲取領(lǐng)袖節(jié)點(diǎn)的重疊度進(jìn)行社區(qū)歸屬判斷，并通過該重疊度裁決待加入節(jié)點(diǎn)與領(lǐng)袖節(jié)點(diǎn)間差異度的方式，實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)社區(qū)的初步定位。通過獲取待加入節(jié)點(diǎn)與領(lǐng)袖節(jié)點(diǎn)間熱度進(jìn)行交互程度判斷，并結(jié)合裁決差異度，進(jìn)一步提升社區(qū)發(fā)現(xiàn)和更新的精度。最后通過仿真實(shí)驗(yàn)，驗(yàn)證了本文算法的有效性。

1 網(wǎng)絡(luò)社區(qū)搜尋模型概述

由于網(wǎng)絡(luò)社區(qū)需要處理的是用戶及用戶行為大數(shù)據(jù)的集合[6]，實(shí)踐中將網(wǎng)絡(luò)、用戶析構(gòu)為圖點(diǎn)，圖點(diǎn)之間的有向邊為用戶行為，見圖1，表現(xiàn)形式如下：

其中，G為圖點(diǎn)，V為用戶，E為用戶行為。

在網(wǎng)絡(luò)社區(qū)搜尋過程中，(V)能夠顯著體現(xiàn)第個(gè)節(jié)點(diǎn)與相鄰節(jié)點(diǎn)的交互程度：若一個(gè)節(jié)點(diǎn)的權(quán)值越大，說明該節(jié)點(diǎn)與其它節(jié)點(diǎn)間交互程度也十分密切。此外，不同節(jié)點(diǎn)之間的覆蓋范圍可能有若干重疊之處，見圖2。若某個(gè)節(jié)點(diǎn)的權(quán)值較高，則具備被選為領(lǐng)袖節(jié)點(diǎn)的價(jià)值，能夠承擔(dān)社區(qū)的組建任務(wù)。

其中C表示各領(lǐng)袖節(jié)點(diǎn)覆蓋范圍內(nèi)重疊節(jié)點(diǎn)的總和，獲取方式如下：

()表示單位階躍函數(shù)，當(dāng)且僅當(dāng)某個(gè)節(jié)點(diǎn)處于覆蓋范圍時(shí)取1：

2 本文網(wǎng)絡(luò)社區(qū)搜尋算法設(shè)計(jì)

考慮到當(dāng)前網(wǎng)絡(luò)社區(qū)搜尋算法存在諸如差異度機(jī)制弱反饋效應(yīng)強(qiáng)[9]、收斂時(shí)間短等不足問題[10]，本文構(gòu)造了中心差異度迭代調(diào)整機(jī)制來實(shí)現(xiàn)網(wǎng)絡(luò)社區(qū)的準(zhǔn)確搜尋，主要分為兩個(gè)過程：①基于重疊度-差異度篩選機(jī)制的初始搜尋，該過程主要通過獲取領(lǐng)袖節(jié)點(diǎn)間重疊度來計(jì)算差異度，對(duì)待加入節(jié)點(diǎn)進(jìn)行初始社區(qū)搜尋。②基于差異度-交互熱度的節(jié)點(diǎn)精度二次搜尋，該過程主要針對(duì)節(jié)點(diǎn)與領(lǐng)袖節(jié)點(diǎn)之間數(shù)據(jù)交互的差異度-熱度進(jìn)行綜合裁決，以便對(duì)錯(cuò)誤社區(qū)進(jìn)行二次修正，降低節(jié)點(diǎn)搜尋網(wǎng)絡(luò)社區(qū)過程中存在的誤差。

2.1 基于重疊度-差異度篩選機(jī)制的初始搜尋

其中C表示該聚類中已含的領(lǐng)袖節(jié)點(diǎn)。

圖2 基于重疊度-差異度篩選機(jī)制的初始搜尋

2.2 基于差異度-交互熱度的社區(qū)歸屬二次搜尋

通過重疊度-差異度篩選機(jī)制的初始搜尋雖然能夠?qū)崿F(xiàn)對(duì)網(wǎng)絡(luò)社區(qū)的初步搜尋，但當(dāng)領(lǐng)袖節(jié)點(diǎn)數(shù)量較多時(shí)，該方法難以實(shí)現(xiàn)網(wǎng)絡(luò)社區(qū)的精確化，因此，本文基于差異度-交互熱度，構(gòu)建了節(jié)點(diǎn)精度二次搜尋，過程如下：

圖3 基于差異度-交互熱度的節(jié)點(diǎn)精度二次搜尋的過程

2.3 復(fù)雜度分析

3 仿真實(shí)驗(yàn)

3.1 仿真環(huán)境參數(shù)設(shè)置

為便于對(duì)本文算法的優(yōu)越性進(jìn)行仿真，采取MATLAB仿真實(shí)驗(yàn)環(huán)境，針對(duì)當(dāng)前網(wǎng)絡(luò)社區(qū)搜尋算法中常用的差分迭代閾值裁決機(jī)制[11]（Differential Iterative Threshold Decision Mechanism，DITD機(jī)制），混沌度一體化成型迭代機(jī)制[12]（Chaos Integration Forming Iterative Mechanism，CIFI機(jī)制）進(jìn)行仿真對(duì)比。從首次成功率、搜尋次數(shù)、迭代周期、聚集度四個(gè)指標(biāo)進(jìn)行仿真對(duì)比，詳細(xì)參數(shù)如下：

表1 仿真參數(shù)

3.2 首次成功率

圖4顯示了本文算法與DITD機(jī)制、CIFI機(jī)制的首次成功率的測試數(shù)據(jù)。由圖可知，在不同的領(lǐng)袖節(jié)點(diǎn)數(shù)量下，本文算法的首次成功率始終處于較高的水平，當(dāng)節(jié)點(diǎn)數(shù)量為60個(gè)時(shí)，其成功率達(dá)到90.12%左右。而DITD機(jī)制、CIFI機(jī)制的首次成功率始終要低于本文算法。這是由于本文通過重疊度-差異度篩選機(jī)制的初始搜尋流程，能夠顯著地降低節(jié)點(diǎn)歸屬到領(lǐng)袖節(jié)點(diǎn)重疊區(qū)域的可能，且可以采取差異度的方式對(duì)初始社區(qū)進(jìn)行進(jìn)一步搜尋。此外，本文算法基于熱度思想，對(duì)初始搜尋過程中的錯(cuò)誤進(jìn)行二次修正，能夠顯著減少誤搜尋的可能性，因而首次成功率較高。DITD機(jī)制雖然對(duì)搜尋過程采取基于差分迭代的方式降低搜尋失敗的概率，然而該機(jī)制實(shí)現(xiàn)過程比較復(fù)雜，且差分迭代過程中需要網(wǎng)絡(luò)環(huán)境保持平穩(wěn)狀態(tài)，若網(wǎng)絡(luò)發(fā)生抖動(dòng)，將會(huì)導(dǎo)致算法搜尋的成功率受到很大的影響。CIFI機(jī)制主要采用一次成型機(jī)制，沒有設(shè)計(jì)精度提升流程對(duì)搜尋過程進(jìn)行精度提升，因此首次成功率較低。

圖4 首次成功率仿真

3.3 搜尋次數(shù)

圖5顯示了本文算法與DITD機(jī)制、CIFI機(jī)制在領(lǐng)袖節(jié)點(diǎn)不斷增加的情況下搜尋次數(shù)測試結(jié)果。由圖可知，本文算法的搜尋次數(shù)始終處于較低的水平，DITD機(jī)制、CIFI機(jī)制需要更多的搜尋次數(shù)才能達(dá)到性能的穩(wěn)定。這是由于本文算法的首次成功率較高，且通過差異度方式對(duì)初始社區(qū)進(jìn)行進(jìn)一步搜尋，精度要好于對(duì)照組算法，因此需要搜尋的次數(shù)較低。DITD機(jī)制搜尋過程比較復(fù)雜，對(duì)環(huán)境的適應(yīng)性較差，需要更多的搜尋次數(shù)才能實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)社區(qū)的精確搜尋。CIFI機(jī)制雖然能夠進(jìn)行一次成型，然而由于該算法沒有二次精度提升機(jī)制，一旦發(fā)生搜尋錯(cuò)誤將會(huì)再次進(jìn)行搜尋流程，因此搜尋次數(shù)要高于本文算法。

圖5 搜尋次數(shù)仿真

3.4 迭代周期

圖6顯示了本文算法與DITD機(jī)制、CIFI機(jī)制在領(lǐng)袖節(jié)點(diǎn)不斷增加的情況下迭代周期測試結(jié)果。由圖可知，本文算法的迭代周期要顯著低于對(duì)照組算法，這是由于本文算法的首次成功率及搜尋次數(shù)均要顯著好于對(duì)照組算法，因此成功搜尋社區(qū)過程中的迭代周期較短。DITD機(jī)制、CIFI機(jī)制由于在首次成功率及搜尋次數(shù)性能上要低于本文算法，DITD機(jī)制由于搜尋過程非常復(fù)雜，迭代過程準(zhǔn)確度較差，因此迭代周期較長。CIFI機(jī)制雖然能夠一次性地實(shí)現(xiàn)社區(qū)搜尋，然而由于該算法精度較低，迭代過程中需要不斷修正社區(qū)，因此迭代周期較本文算法遜色。

圖6 迭代周期仿真

3.5 聚集度

圖7（a）為初始信源，圖7（b）-（d）為本文算法、DITD機(jī)制、CIFI機(jī)制在聚集度上測試結(jié)果。為對(duì)領(lǐng)袖節(jié)點(diǎn)進(jìn)行仿真，采取文獻(xiàn)[13]使用的廣義熵的模糊聚類生成初始信源，錯(cuò)誤節(jié)點(diǎn)以噪聲形式進(jìn)行掩蓋，而正確的領(lǐng)袖節(jié)點(diǎn)以初始信源上像素點(diǎn)的形式存在，見圖7(a)。迭代時(shí)間設(shè)定為2h。由圖可知，本文算法保持了初始信源的大部分特征，無色彩失真，只存在輕微的噪聲，見圖7(b)。而DITD機(jī)制雖然細(xì)節(jié)清晰，但其色彩信息出現(xiàn)較大的失真，見圖7(c)。CIFI機(jī)制的聚集度不理想，其輸出圖像較為模糊，丟失了部分細(xì)節(jié)，見圖7(d)。這顯示了所提方案具有良好的聚集度性能。這是由于本文算法搜尋成功度較高，且通過差異度-交互熱度的節(jié)點(diǎn)精度二次搜尋流程能夠迅速聚集熱點(diǎn)并進(jìn)行精度提升，因此聚集度高。DITD機(jī)制采用差分機(jī)制，迭代過程復(fù)雜，且出現(xiàn)錯(cuò)誤的情況下難以聚集熱點(diǎn)，因而聚集度較低，圖樣出現(xiàn)了扭曲變形現(xiàn)象。CIFI機(jī)制僅采取一次成型機(jī)制，無法對(duì)錯(cuò)誤的搜尋點(diǎn)進(jìn)行過濾，因而聚集度也要低于本文算法，圖樣顯示了嚴(yán)重的模糊現(xiàn)象。

圖7 不同算法的聚集度測試結(jié)果

4 結(jié)束語

考慮到當(dāng)前網(wǎng)絡(luò)社區(qū)搜尋算法存在一些不足之處，提出了一種全新的基于中心差異度迭代調(diào)整機(jī)制的網(wǎng)絡(luò)社區(qū)搜尋算法，該算法通過重疊度-差異度篩選機(jī)制的初始搜尋流程，能夠?qū)崿F(xiàn)較高的首次成功率，且迭代周期短，搜尋次數(shù)低。此外，本算法針對(duì)當(dāng)前機(jī)制均存在二次更新困難的不足，通過差異度-交互熱度的節(jié)點(diǎn)精度二次搜尋流程，大大提高了社區(qū)歸屬的準(zhǔn)確度。仿真實(shí)驗(yàn)也表明本文算法對(duì)DITD機(jī)制、CIFI機(jī)制具有較大的優(yōu)勢。

下一步，針對(duì)本文算法對(duì)流動(dòng)性強(qiáng)的環(huán)境適應(yīng)性不足的問題，該問題主要是由于節(jié)點(diǎn)高速流動(dòng)狀態(tài)時(shí)拓?fù)浣Y(jié)構(gòu)發(fā)生劇烈變化，特別是在聚類變動(dòng)較快的情況下存在成功率下降，將通過引入超混沌流動(dòng)性一體化控制機(jī)制，改善本文算法在高流動(dòng)性條件下存在的精度不足的問題，進(jìn)一步提升本文算法的適應(yīng)性能。

[1] 喬少杰,郭俊,韓楠,等. 大規(guī)模復(fù)雜網(wǎng)絡(luò)社區(qū)并行發(fā)現(xiàn)算法[J]. 計(jì)算機(jī)學(xué)報(bào),2017,40(3):687-700.

[2] 張皓,王明斐,陳艷浩. 基于Kullback-Leibler距離的二分網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法[J]. 計(jì)算機(jī)應(yīng)用研究,2017,34(5): 1480-1483.

[3] Zeng Z, Jiang x. Richard N. Discovering Causal Interactions Using Bayesian Network Scoring and Information Gain[J]. BMC Bioinformatics,2016,17(1): 1021-1036.

[4] Zhang S, Jin L, Lin L. Discovering Similar Chinese Characters in Online Handwriting with Deep Convolutional Neural Networks[J]. International Journal on Document Analysis and Recognition (IJDAR), 2016,19(3): 237-252.

[5] Wang T S, Lin H T, Wang P. Weighted-Spectral Clustering Algorithm for Detecting Community Structures in Complex networks[J]. Artificial Intelligence Review, 2017,47(4): 463-483.

[6] Yang J L, Huang T, Song W M. Discover the Network Mechanisms Underlying the Connections Between Aging and Age-Related Diseases.[J]. Scientific reports, 2016, 23(6): 32-56.

[7] Rocco C M, Moronta J, Ranmirez-Manque Z, et al. Effects of Multi-state Links in Network Community Detection[J]. Reliability Engineering and System Safety,2017,163(12): 46-56.

[8] Wei Z, Xiao K Z, Zhao K. Analysis of Associtivity and Community Structure in Mobile Social Networks[J]. Procedia Computer Science,2017,107(6): 630-635.

[9] Chen Y, Wang x, Xiang x, et al. Overlapping Community Detection in Weighted Networks Via a Bayesian Approach[J]. Physica A: Statistical Mechanics and its Applications, 2017,468(12): 790-801.

[10] 趙森嚴(yán). 基于移動(dòng)代理的無線傳感器網(wǎng)絡(luò)路由算法研究[J]. 井岡山大學(xué)學(xué)報(bào):自然科學(xué)版,2017,38(5):46-49.

[11] Lin C C, Kang J R, Chen J Y. An Integer Programming Approach and Visual Analysis for Detecting Hierarchical Community Structures in Social Networks[J]. Information Sciences, 2015, 299(3): 25-33.

[12] Zhang Z, Wang Z. Mining Overlapping and Hierarchical Communities in Complex Networks[J]. Physica A: Statistical Mechanics and its Applications,2015,421(41): 296-311.

The Research and Simulation of network community search algorithm based on central difference iteration adjustment mechanism

TAO Shuo

(Department of Electronic Information, Maanshan Technical College, Ma’anshan, Anhui 243031, China)

In order to solve the problems of node clustering in current network community search algorithms, such as the complexity of search iterations and the difficulty of secondary update of community ownership, a network community search algorithm based on the iterative adjustment mechanism of center difference degree is proposed. Firstly, the overlapping degree of leader nodes is used to decide the initial community search, and the difference between join nodes and leader nodes is matched to improve the speed of clustering formation and reduce the search iteration process. In order to improve the accuracy of community discovery, the method of constructing the interaction heat between the node to be added and the leader node is used to improve the accuracy of community discovery. Simulation results show that the proposed algorithm has higher first success rate in comparison with the Differential Iterative Threshold Decision Mechanism and Chaos Integration Forming Iterative Mechanism which are commonly used in current network community search algorithms. The advantages of fewer searches, shorter iteration period and clearer aggregation degree make it valuable for practical deployment.

network community search; node clustering; leader node; heat mechanism; clustering matching; first success rate

TP393

A

10.3969/j.issn.1674-8085.2019.02.011

1674-8085(2019)02-0058-06

2018-12-01；

2019-02-12

陶碩(1973-)，女，安徽樅陽人，講師，碩士，主要從事數(shù)據(jù)挖掘、社網(wǎng)絡(luò)分析、計(jì)算機(jī)應(yīng)用技術(shù)等方面的研究(E-mail: taoshuo1973@sina.com).