為提高社區(qū)檢測的效率與精度,提出一種隨機并行的局部搜索算法。用圖模型結(jié)構(gòu)表示復(fù)雜系統(tǒng),將頂點劃分成簇。構(gòu)建貪婪隨機自適應(yīng)搜索過程與路徑重連過程,以解決加權(quán)圖的模塊最大化問題。引入一種{0,1}矩陣類特征并定義聚類的距離函數(shù),從而進行頂點的鄰域搜索,實現(xiàn)社區(qū)的高精度檢測識別。實驗結(jié)果表明,該算法的F₁值與NMI指標(biāo)值均較高。 

【文章來源】：計算機工程. 2019,45(06)北大核心CSCD

【文章頁數(shù)】：7 頁

【部分圖文】：

隨機圖H的構(gòu)造過程示例可利用頂點集V(H)=V(G)和如下的邊集概

計算機工程2019年6月15日圖4所示為4種網(wǎng)絡(luò)模型，其參數(shù)數(shù)據(jù)分別對應(yīng)表1中的第1行、第3行，表2中的第1行、第3行。圖4人工生成網(wǎng)絡(luò)模型3．2穩(wěn)健性實驗本節(jié)對各社區(qū)發(fā)現(xiàn)算法的F1值進行對比測試，F(xiàn)1值的取值范圍是0～1，其值越大，表明分類模型的穩(wěn)健性越高。F1評價指標(biāo)定義為:F1=2PRP+R=2TP+FP+FNTP(31)其中，F(xiàn)P指實際為正但檢測為負(fù)的樣本，F(xiàn)N指實際為負(fù)但檢測為正的樣本，TP指實際為正且檢測為正的樣本，P為準(zhǔn)確率，R為召回率。本次實驗選取的對比算法為文獻(xiàn)［14］算法和文獻(xiàn)［15］算法。前者是一種社會網(wǎng)絡(luò)中線性時間重疊的社區(qū)檢測方法，其采用增量式的社區(qū)檢測算法，具有較強的社區(qū)檢測能力和較高的社區(qū)檢測速度;后者是一種基于社區(qū)檢測質(zhì)量的算法，具有較高的社區(qū)檢測精度。在圖4所示的4種網(wǎng)絡(luò)模型中，3種算法的F1值對比結(jié)果如圖5所示。由圖5可以看出，3種算法的F1值都隨著社區(qū)數(shù)量的增加而降低，即模型的穩(wěn)健性降低。其中，與2種對比算法相比，本文算法的F1值均較大，這體現(xiàn)了其在社區(qū)發(fā)現(xiàn)穩(wěn)健性上的優(yōu)勢。圖53種算法的F1值對比結(jié)果3．3準(zhǔn)確性實驗本節(jié)選取NMI指標(biāo)度量2個聚類結(jié)果的相近程度，以評價社區(qū)發(fā)現(xiàn)算法的準(zhǔn)確性。NMI的值域是0～1，值越高代表算法準(zhǔn)確性越高。對于2種社區(qū)類型A、B，其NMI指標(biāo)定義為:NMI=－2∑CAi=1∑CBj=1Cij·lbCijNCiC()j∑CAi=1Ci·lbCi．()N+∑CBj=1Cij·lbC．j(

【參考文獻(xiàn)】：
期刊論文
[1]基于KL散度及多尺度融合的顯著性區(qū)域檢測算法[J]. 羅會蘭,萬成濤,孔繁勝.  電子與信息學(xué)報. 2016(07)
[2]基于用戶聚類的異構(gòu)社交網(wǎng)絡(luò)推薦算法[J]. 陳克寒,韓盼盼,吳健.  計算機學(xué)報. 2013(02)
[3]一種改進的加權(quán)復(fù)雜網(wǎng)絡(luò)聚類方法[J]. 郭陶,張琨,郭文娟,莊克琛,賀定龍,李配配.  計算機科學(xué). 2012(S1)
[4]一種基于修正的最小生成樹及其鄰接譜的特征匹配算法[J]. 宣善立,梁棟,朱明,范益政,王年.  電子學(xué)報. 2010(02)



本文編號：3443148