基于多目標(biāo)優(yōu)化的符號(hào)網(wǎng)絡(luò)社區(qū)檢測(cè)算法

譚玉玲，肖媛娥

基于多目標(biāo)優(yōu)化的符號(hào)網(wǎng)絡(luò)社區(qū)檢測(cè)算法

*譚玉玲1，肖媛娥2

（1. 羅定職業(yè)技術(shù)學(xué)院信息工程系，廣東，羅定 527200；2. 井岡山大學(xué)網(wǎng)絡(luò)信息中心，江西，吉安 343009）

符號(hào)網(wǎng)絡(luò)可以描述實(shí)體之間的多種關(guān)系，對(duì)符號(hào)網(wǎng)絡(luò)中的社團(tuán)檢測(cè)可以挖掘出其中的有效信息。同時(shí)考慮連接密度和連接符號(hào)，將社團(tuán)發(fā)現(xiàn)問(wèn)題建模為一個(gè)多目標(biāo)優(yōu)化問(wèn)題，基于MOEA/D框架，提出一種改進(jìn)的符號(hào)網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法，設(shè)計(jì)了基于字符串的編碼方式、預(yù)分區(qū)策略、交叉合并策略、變異方式等。實(shí)驗(yàn)結(jié)果表明，本算法可以有效檢測(cè)出社團(tuán)結(jié)構(gòu)。

復(fù)雜網(wǎng)絡(luò)；符號(hào)網(wǎng)絡(luò)；社團(tuán)結(jié)構(gòu)；多目標(biāo)優(yōu)化

0 引言

現(xiàn)實(shí)生活中存在很多的復(fù)雜網(wǎng)絡(luò)，對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行社團(tuán)結(jié)構(gòu)挖掘可以揭示復(fù)雜網(wǎng)絡(luò)的特性，具有重要的研究?jī)r(jià)值。傳統(tǒng)的社區(qū)檢測(cè)算法大致可分為圖劃分方法、基于層次聚類(lèi)的算法、基于進(jìn)化的算法等，主要是針對(duì)無(wú)符號(hào)網(wǎng)絡(luò)進(jìn)行的[1]。在實(shí)際應(yīng)用中，很多網(wǎng)絡(luò)是具有正負(fù)關(guān)系的，即符號(hào)網(wǎng)絡(luò)，如社交網(wǎng)、人際關(guān)系網(wǎng)等。有符號(hào)網(wǎng)絡(luò)是由正關(guān)系和負(fù)關(guān)系構(gòu)成的。因?yàn)槿撕徒M織之間的關(guān)系具有雙面性，具有正值的有符號(hào)網(wǎng)絡(luò)的連接可以被描述為“友好”、“喜歡”等，而具有負(fù)值的連接被描述為“敵對(duì)”、“不喜歡”等[2]。因此，要將無(wú)符號(hào)網(wǎng)絡(luò)的社區(qū)的定義擴(kuò)展到有符號(hào)網(wǎng)絡(luò)中，必須同時(shí)考慮連接密度和連接符號(hào)這兩個(gè)指標(biāo)[3]。

在基于多目標(biāo)的社區(qū)檢測(cè)方面，文獻(xiàn)[4]引入社區(qū)分?jǐn)?shù)(CS)作為目標(biāo)函數(shù)，采用進(jìn)化算法進(jìn)行優(yōu)化；文獻(xiàn)[5]引入了社區(qū)適應(yīng)度(CF)，采用NSGA-II算法同時(shí)優(yōu)化CS和CF兩個(gè)目標(biāo)函數(shù)；文獻(xiàn)[6]提出了同時(shí)優(yōu)化連接度和分隔度兩個(gè)目標(biāo)函數(shù)，采用MOEA/D多目標(biāo)框架優(yōu)進(jìn)行優(yōu)化，取得了良好的結(jié)果。在符號(hào)網(wǎng)絡(luò)的多目標(biāo)研究方面，文獻(xiàn)[7]DWI-SN算法和文獻(xiàn)[8]SNMOGA算法分別利用MOEA/D和NSGAII的框架來(lái)挖掘有符號(hào)網(wǎng)絡(luò)中的社區(qū); 文獻(xiàn)[9]提出了可同時(shí)適合于無(wú)符號(hào)網(wǎng)絡(luò)和符號(hào)網(wǎng)絡(luò)的社區(qū)檢測(cè)算法。然而該算法在相似性指標(biāo)的選取的環(huán)節(jié)中考慮的條件因素不夠完善，導(dǎo)致社區(qū)劃分后擬合結(jié)果不夠精確。

在本研究中，采用MOEA/D框架[10]，選擇了新的相似性度量指標(biāo)，設(shè)計(jì)出新的節(jié)點(diǎn)更新預(yù)分區(qū)策略，同時(shí)，在預(yù)分區(qū)后設(shè)計(jì)了交叉合并操作符合并社區(qū)，用特殊突變算子對(duì)邊界節(jié)點(diǎn)進(jìn)行重新劃分，提高了社區(qū)劃分的精準(zhǔn)度。

1 復(fù)雜網(wǎng)絡(luò)社區(qū)檢測(cè)的多目標(biāo)優(yōu)化模型

對(duì)于有符號(hào)網(wǎng)絡(luò)，要求社區(qū)內(nèi)部的正邊緣和社區(qū)內(nèi)部的負(fù)邊緣都是緊密相連的。一般采用社區(qū)內(nèi)部的正邊緣密度和負(fù)邊緣密度來(lái)評(píng)價(jià)社區(qū)內(nèi)部和社區(qū)之間的連通程度[7-9]。因此，采用一種邊緣密度(Edge Density, ED)的函數(shù)，用于度量有符號(hào)網(wǎng)絡(luò)的社區(qū)連通程度：

此外，要優(yōu)化的第二個(gè)目標(biāo)是有符號(hào)的模塊度SQ。SQ可定義為：

因此，符號(hào)網(wǎng)絡(luò)的多目標(biāo)優(yōu)化模型如下：

2 算法具體設(shè)計(jì)

2.1 編碼方法

本算法選用基于字符串的編碼模式[11]。該編碼方式很容易獲取相應(yīng)的網(wǎng)絡(luò)分區(qū)，然后為每個(gè)節(jié)點(diǎn)設(shè)置出不同的標(biāo)簽，通過(guò)其鄰居的標(biāo)簽對(duì)其標(biāo)簽進(jìn)行更新，最后使用相同的標(biāo)簽更新屬于相同社區(qū)的節(jié)點(diǎn)。在本算法中，社區(qū)劃分的過(guò)程即為標(biāo)記進(jìn)化的過(guò)程。假設(shè)我們有不同的8個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)間的關(guān)系、更新進(jìn)化的過(guò)程和解碼的過(guò)程如圖1所示。

圖1 解的編碼和更新過(guò)程

首先通過(guò)鄰居標(biāo)簽自身標(biāo)簽進(jìn)行更新，劃分集群后進(jìn)行解碼，最終網(wǎng)絡(luò)中產(chǎn)生了兩個(gè)劃分好的社區(qū)。

2.2 種群預(yù)劃分

在種群初始化階段之后，對(duì)網(wǎng)絡(luò)進(jìn)行預(yù)分區(qū)的處理。用節(jié)點(diǎn)相似性函數(shù)，對(duì)輸入網(wǎng)絡(luò)的鄰矩陣進(jìn)行處理，得到一個(gè)相似矩陣。為了獲得節(jié)點(diǎn)的聚集，進(jìn)一步在相似矩陣的基礎(chǔ)上規(guī)劃了New-k節(jié)點(diǎn)更新預(yù)分區(qū)策略[12]。

1）節(jié)點(diǎn)相似函數(shù)

對(duì)于有符號(hào)網(wǎng)絡(luò)，可以計(jì)算其公共鄰居數(shù)量，選用了Jaccard指數(shù)作為節(jié)點(diǎn)相似性的度量指標(biāo)[12]，在上述計(jì)算的基礎(chǔ)上添加一個(gè)懲罰項(xiàng)，構(gòu)造出新的相似性度量方法：

選用Jaccard指數(shù)作為節(jié)點(diǎn)相似性的度量指標(biāo)計(jì)算出任意兩個(gè)節(jié)點(diǎn)的相似性，并得到相似性矩陣，然后根據(jù)提出的基于結(jié)構(gòu)平衡理論的相似性函數(shù)設(shè)計(jì)變異算子。

2）New-k節(jié)點(diǎn)更新預(yù)分區(qū)策略

為了有效地管理預(yù)劃分后的種群，本文采用了一種基于相似矩陣的交叉算子——交叉合并算子和變異算子。

2.3 基于本地節(jié)點(diǎn)集的交叉合并算子

2.4 基于相似矩陣的變異算子

該算子的設(shè)計(jì)中一方面消除了相似向量中的零元素，減少了噪點(diǎn)的干擾，避免了搜索空間中的無(wú)用搜索；另一方面，不僅簡(jiǎn)單地將相似性最高的鄰居節(jié)點(diǎn)標(biāo)簽配給到待定節(jié)點(diǎn)，而且根據(jù)相似性值的比例來(lái)選擇這種方法，使得相似性較小的節(jié)點(diǎn)有機(jī)會(huì)更新待定節(jié)點(diǎn)。該算法避免了過(guò)度收斂，提升了算法在搜索空間中的局部搜索能力。由于在內(nèi)部節(jié)點(diǎn)上操作沒(méi)有意義，變異算子只在邊界節(jié)點(diǎn)上運(yùn)行。

2.5 算法的總體框架

本文設(shè)計(jì)的基于多目標(biāo)優(yōu)化的符號(hào)網(wǎng)絡(luò)社區(qū)檢測(cè)算法如下：

算法輸出：最佳網(wǎng)絡(luò)社團(tuán)分區(qū)；

步驟1初始化；

1.2）初始化隨機(jī)生成的第一代種群pop，采用上述算法處理種群；

步驟2 更新：

2.1）迭代次數(shù)= 1；

2.2）當(dāng)（迭代次數(shù)<= maxgen）；

2.3）for i = 1：popsize；

2.5）if rand_number

2.7）else if rand_number

2.9）end if；

2.12）for j= l：length(child)；

2.14）end for；

2.15）end for；

2.16）迭代次數(shù) = 迭代次數(shù) + 1；

2.17）end while；

3 實(shí)驗(yàn)結(jié)果與分析

3.1 評(píng)價(jià)指標(biāo)

為了評(píng)估所提出的算法的優(yōu)越性和劣勢(shì)，選擇了歸一化互信息（NMI）[13-14]作為評(píng)估指標(biāo)。假設(shè)A是真實(shí)網(wǎng)絡(luò)分區(qū)，B是檢測(cè)到的算法分區(qū)?；煜仃囉煞謪^(qū)A和B共同構(gòu)成。NMI的表述為：

3.2 參數(shù)設(shè)置

為驗(yàn)證本文所提算法N-GMOEA-net的有效性，與MODPSO[7]，SNMOGA[8]和MEAs-SN[9]算法進(jìn)行對(duì)比。MODPSO是一種用于網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的多目標(biāo)離散粒子群優(yōu)化算法，能處理小規(guī)模有符號(hào)網(wǎng)絡(luò)。SNMOGA是一種基于NSGAII的多目標(biāo)符號(hào)網(wǎng)絡(luò)社區(qū)檢測(cè)算法。MEAs-SN是一個(gè)基于MOEA / D框架的網(wǎng)絡(luò)社區(qū)檢測(cè)算法。為了驗(yàn)證算法的優(yōu)越性，上述算法均采用相關(guān)文獻(xiàn)中推薦的參數(shù)進(jìn)行配置，見(jiàn)表1。

表1 算法的參數(shù)設(shè)置

Table 1 Parameter settings of the algorithm

算法PopmaxgenPcPmNT MOGA-net3001000.80.2× MODPSO100100×0.140 MEAs-SN1001000.71.020 SNMOGA1001000.80.2×

其中，算法中不需要的參數(shù)用“×”表示。其中Pop為隨機(jī)生成的第一代種群，Maxgen為終止進(jìn)化的迭代次數(shù)，Pc為交叉發(fā)生的概率，Pm為變異發(fā)生的概率，NT為每個(gè)權(quán)重向量鄰居權(quán)重向量的數(shù)量。

3.3 人工網(wǎng)絡(luò)和合成網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果

為了驗(yàn)證本算法的性能，使用兩個(gè)人工網(wǎng)絡(luò)和兩個(gè)真實(shí)網(wǎng)絡(luò)進(jìn)行測(cè)試。其中兩個(gè)有符號(hào)網(wǎng)絡(luò)分別使用IS1和IS2表示，另外兩個(gè)有符號(hào)網(wǎng)絡(luò)分別為Slovene Parliamentary Party Network (SPP)和Gahuku-Gama Subtribes network(GGS)[9,15]。這些網(wǎng)絡(luò)的相關(guān)特征見(jiàn)表2。

表2 四個(gè)小規(guī)模符號(hào)網(wǎng)絡(luò)的信息

Table 2 Information on four small-scale symbol networks

網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)邊緣數(shù)正向邊緣負(fù)向邊緣真實(shí)社區(qū)數(shù) IS1284230123 IS2284930193 SPP104518272 GGS164829293

在這之中，這四種算法的聚類(lèi)結(jié)果見(jiàn)表3。

表3 小規(guī)模有符號(hào)網(wǎng)絡(luò)的檢測(cè)結(jié)果

Table 3 Test results of small-scale signed network

網(wǎng)絡(luò)指標(biāo) MODPSOMEAs-SNSNMOGA本文算法 IS1NMI1.00000.48301.00001.0000 0.98770.48301.00001.0000 0.03880.00000.00000.0000 IS2NMI0.92230.42991.00001.0000 0.88110.42991.00001.0000 0.02410.00000.00000.0000 SPPNMI1.00001.00001.00001.0000 0.98471.00001.00001.0000 0.04830.00000.00000.0000 GGSNMI1.00000.68831.00001.0000 1.00000.52761.00001.0000 0.00000.18660.00000.0000

由于這四種網(wǎng)絡(luò)的規(guī)模小、結(jié)構(gòu)易于識(shí)別，除MEAs-SN算法外，其他算法在準(zhǔn)確性方面表現(xiàn)良好。其中本算法和SNMOGA給出了完全正確的網(wǎng)絡(luò)分區(qū)。而MODPSO的性能略低于SNMOGA和本文算法。

3.4 有符號(hào)現(xiàn)實(shí)網(wǎng)絡(luò)生成的實(shí)驗(yàn)結(jié)果

圖3 SLFR比較結(jié)果-

圖4 SLFR比較結(jié)果-

根據(jù)以上SLFR網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果可知，本文提出的算法在精度和穩(wěn)定性方面明顯優(yōu)于SNMOGA和MEAs-SN。

圖6 SLFR比較結(jié)果-

4 結(jié)論

本文設(shè)計(jì)了一種用于符號(hào)網(wǎng)絡(luò)社區(qū)檢測(cè)的多目標(biāo)優(yōu)化算法，詳細(xì)介紹了其關(guān)鍵實(shí)現(xiàn)技術(shù)。實(shí)驗(yàn)結(jié)果表明，本文算法具有較高的檢測(cè)效率。下一步將探索一種混合算法，可以同時(shí)適用于非符號(hào)網(wǎng)絡(luò)和符號(hào)網(wǎng)絡(luò)的社區(qū)檢測(cè)。

[1] Cai Q, Ma L J ,Gong M G .A survey on network community detection based onevolutionary computation[J]. Int. J. Bio-Inspired Computation, 2016,8(2):84-98.

[2] Shang R H, Zhang W T, Jiao L C. Circularly searching core nodes based label propagation algorithm for community detection[J] Int. J. Pattern Recognit. Artif. Intell. 2016,30 (8): 1659024.

[3] Gong M G, Ma L J, Zhang Q F, et al. Community detection in networks by using multi-objective evolutionary algorithm with decomposition[J]. Physica A: Statistical Mechanics and its Applications, 2012, 391(15): 4050-4060.

[4] Pizzuti C. A multi-objective genetic algorithm to find communities in complex networks[J]. IEEE Transactions on Evolutionary Computation, 2012, 16(3): 418-430.

[5] Amelio A, Pizzuti C. An evolutionary and local refinement approach for community detection in signed networks[J]. International Journal on Artificial Intelligence Tools, 2016, 25(4): 1650021.

[6] 王聰,柴爭(zhēng)義.基于多目標(biāo)進(jìn)化的復(fù)雜網(wǎng)絡(luò)社區(qū)檢測(cè)[J].計(jì)算機(jī)技術(shù)與發(fā)展,2020,43(6):112-116.

[7] Gong M G, Cai Q, Chen X, et al. Complex network clustering by multi-objective discrete particle swarm optimization based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(1): 82-97.

[8] Liu C L, Liu J, Jiang Z Z. A multi-objective evolutionary algorithm based on similarity for community detection from signed social networks[J]. IEEE transactions on cybernetics, 2014, 44(12): 2274-2287.

[9] Shang R H, Liu H, Jiao L C. Multi-objective clustering technique based on k-nodes update policy and similarity matrix for mining communities in social networks[J].Physica A, 2017,486:1-24.

[10] Zhang Q, Li H. Moea/d: a multiobjective evolutionary algorithm based on decomposition[J]. IEEE Trans. Evol. Comput, 2007, 11(6):712-731.

[11] 李赫,印瑩,李源,等.基于多目標(biāo)演化聚類(lèi)的大規(guī)模動(dòng)態(tài)網(wǎng)絡(luò)社區(qū)檢測(cè)[J].計(jì)算機(jī)研究與發(fā)展,2019,65(2):10-15.

[12] Amelio A, Pizzuti C. An evolutionary and local refinement approach for community detection in signed networks[J]. International Journal on Artificial Intelligence Tools, 2016, 25(4): 1650021.

[13] 張清琪,劉漫丹.復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的多目標(biāo)五行環(huán)優(yōu)化算法[J].計(jì)算機(jī)科學(xué),2020,98(4):15-20.

[14] Zhang Y F, Liu Y Y , Ma X M. Community detection in signed networks by relaxing modularity optimization with orthogonal and nonnegative constraints[J].Neural Computing and Applications,2019,12(5): 116-122.

[15] Chen J R, Liu D W.Hao F ,et al. Community detection in dynamic signed network: an intimacy evolutionary clustering algorithm[J].Journal of Ambient Intelligence and Humanized Computing, 2020, 62(6):126-138.

SIGNED NETWORK COMMUNITY DISCOVERY ALGORITHM BASED ON MULTI-OBJECTIVE OPTIMIZATION

*TAN Yu-ling1，XIAO Yuan-e2

（1. Department of Information Engineering, Luoding Vocational and Technical College, Luoding, Guangdong 527200, China;2.Network Information Center , Jinggangshan University , Ji’an , Jiangxi 343009,China）

The signed network can describe a variety of relationships between entities, and the community detection in the signed network can dig out the effective information. At the same time, considering connection density and connection symbols, the community discovery problem is modeled as a multi-objective optimization problem. Based on the MOEA/D framework, an improved signed network community discovery algorithm is proposed, and a string-based encoding method and pre-partitioning strategy are designed. Also cross-merger strategy, mutation method are designed. The experimental results show that the algorithm can effectively detect the community structure.

complex network; signed network; community structure; multi-objective optimization

1674-8085（2022）01-0070-08

TP181

A

10.3969/j.issn.1674-8085.2022.01.012

2021-03-03；

2021-05-25

廣東省高職高專云計(jì)算與大數(shù)據(jù)專業(yè)委員會(huì)2019年度課題（GDYJ SKT19-05）；教育部科技發(fā)展中心“天誠(chéng)匯智”創(chuàng)新促教基金課題（2018E01020）

*譚玉玲(1976-)，女，廣東羅定人，副教授，碩士，主要從事智能算法和復(fù)雜網(wǎng)絡(luò)研究(E-mail:super_paper@126.com).