陶 碩

?

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

陶 碩

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

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

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

0 引言

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

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

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

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

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

其中，G為圖點，V為用戶，E為用戶行為。

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

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

()表示單位階躍函數(shù)，當且僅當某個節(jié)點處于覆蓋范圍時取1：

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

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

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

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

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

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

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

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

2.3 復雜度分析

3 仿真實驗

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

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

表1 仿真參數(shù)

3.2 首次成功率

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

圖4 首次成功率仿真

3.3 搜尋次數(shù)

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

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

3.4 迭代周期

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

圖6 迭代周期仿真

3.5 聚集度

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

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

4 結(jié)束語

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

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

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

[2] 張皓,王明斐,陳艷浩. 基于Kullback-Leibler距離的二分網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法[J]. 計算機應用研究,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] 趙森嚴. 基于移動代理的無線傳感器網(wǎng)絡(luò)路由算法研究[J]. 井岡山大學學報:自然科學版,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ò)分析、計算機應用技術(shù)等方面的研究(E-mail: taoshuo1973@sina.com).