Search Advanced

Message Board

Dear readers, authors and reviewers,you can add a message on this page. We will reply to you as soon as possible!

2023 Volume 45 Issue 8
Article Contents
Previous Article Next Article

YANG Zhixiang, XU Xiaoke, XIAO Jing. Community Detection in Signed Network Based on High-Order Information Local Search Strategy[J]. Journal of Southwest University Natural Science Edition, 2023, 45(8): 31-47. doi: 10.13718/j.cnki.xdzk.2023.08.004
Citation: YANG Zhixiang, XU Xiaoke, XIAO Jing. Community Detection in Signed Network Based on High-Order Information Local Search Strategy[J]. Journal of Southwest University Natural Science Edition, 2023, 45(8): 31-47. doi: 10.13718/j.cnki.xdzk.2023.08.004
shu

Community Detection in Signed Network Based on High-Order Information Local Search Strategy

  • College of Information and Communication Engineering, Dalian Minzu University, Dalian Liaoning 116600, China

More Information
  • Corresponding author: XIAO Jing
  • Received Date: 07/06/2023
    Available Online: 20/08/2023

  • MSC: TP391

  • In existing signed network community detection methods, the local search strategy serves as an important component of the signed network community detection algorithm and can accelerate the convergence rate of the algorithm. However, most of the local search strategies in signed networks only utilize low-order structural information such as edges and nodes, thereby, neglecting the deeper and richer high-order structure that can be mined from signed networks. To enhance the performance of the existing signed network community detection local search strategy, this article proposes a local search strategy based on signed motifs. A new method based on signed motif for community migration was designed, which extends the traditional community numbering migration between binary tuples to ternary tuples. By comprehensively utilizing the low-order and high-order topological structural information of the signed network, the structural balance of nodes is further optimized, thereby, improving the convergence rate and detection performance of the algorithm. Experiments on synthetic and real-world networks demonstrated that the designed local search strategy exhibited good accuracy and quality.

  • 加载中
  • [1] HEIDER F. Attitudes and Cognitive Organization[J]. The Journal of Psychology, 1946, 21(1): 107-112. doi: 10.1080/00223980.1946.9917275

    CrossRef Google Scholar

    [2] NEWMAN M E J. Detecting Community Structure in Networks[J]. The European Physical Journal B, 2004, 38(2): 321-330. doi: 10.1140/epjb/e2004-00124-y

    CrossRef Google Scholar

    [3] XIA Z Y, BU Z. Community Detection Based on a Semantic Network[J]. Knowledge-Based Systems, 2012, 26: 30-39. doi: 10.1016/j.knosys.2011.06.014

    CrossRef Google Scholar

    [4] PARISIEN C, ANDERSON C H, ELIASMITH C. Solving the Problem of Negative Synaptic Weights in Cortical Models[J]. Neural Computation, 2008, 20(6): 1473-1494. doi: 10.1162/neco.2008.07-06-295

    CrossRef Google Scholar

    [5] CHEN Y R, KANG Q M, DUAN W Q, et al. An Iterated Local Search Algorithm for Community Detection in Signed Networks[J]. International Journal of Modern Physics C, 2022, 33(8): 2250105. doi: 10.1142/S0129183122501054

    CrossRef Google Scholar

    [6] AREF S, NEAL Z. Detecting Coalitions by Optimally Partitioning Signed Networks of Political Collaboration[J]. Scientific Reports, 2020, 10(1): 1506. doi: 10.1038/s41598-020-58471-z

    CrossRef Google Scholar

    [7] KUNEGIS J, SCHMIDT S, LOMMATZSCH A, et al. Spectral Analysis of Signed Graphs for Clustering, Prediction and Visualization[C] //Proceedings of the 2010 SIAM International Conference on Data Mining. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2010: 559-570.

    Google Scholar

    [8] CHIANG K Y, HSIEH C J, NATARAJAN N, et al. Prediction and Clustering in Signed Networks: A Local to Global Perspective[J]. The Journal of Machine Learning Research, 2014, 15(1): 1177-1213.

    Google Scholar

    [9] ZHAO X H, YANG B, LIU X Y, et al. Statistical Inference for Community Detection in Signed Networks[J]. Physical Review E, 2017, 95(4): 042313. doi: 10.1103/PhysRevE.95.042313

    CrossRef Google Scholar

    [10] LI Y D, LIU J, LIU C L. A Comparative Analysis of Evolutionary and Memetic Algorithms for Community Detection from Signed Social Networks[J]. Soft Computing, 2014, 18(2): 329-348. doi: 10.1007/s00500-013-1060-4

    CrossRef Google Scholar

    [11] MOSCATO P. On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts-Towards Memetic Algorithms[J]. Caltech Concurrent Computation Program, 1989, 826(10): 79-158.

    Google Scholar

    [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. doi: 10.1142/S0218213016500214

    CrossRef Google Scholar

    [13] CHE S W, YANG W, WANG W. A Memetic Algorithm for Community Detection in Signed Networks[J]. IEEE Access, 2020, 8: 123585-123602. doi: 10.1109/ACCESS.2020.3006108

    CrossRef Google Scholar

    [14] BENSON A R, GLEICH D F, LESKOVEC J. Higher-Order Organization of Complex Networks[J]. Science, 2016, 353(6295): 163-166. doi: 10.1126/science.aad9029

    CrossRef Google Scholar

    [15] MILO R, SHEN-ORR S, ITZKOVITZ S, et al. Network Motifs: Simple Building Blocks of Complex Networks[J]. Science, 2002, 298(5594): 824-827. doi: 10.1126/science.298.5594.824

    CrossRef Google Scholar

    [16] HUANG J Y, HOU Y N, LI Y S. Efficient Community Detection Algorithm Based on Higher-Order Structures in Complex Networks[J]. Chaos: an Interdisciplinary Journal of Nonlinear Science, 2020, 30(2): 023114. doi: 10.1063/1.5130523

    CrossRef Google Scholar

    [17] YANG B, CHEUNG W, LIU J M. Community Mining from Signed Social Networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(10): 1333-1348. doi: 10.1109/TKDE.2007.1061

    CrossRef Google Scholar

    [18] NEWMAN M E J. Analysis of Weighted Networks[J]. Physical Review E, 2004, 70(5): 056131. doi: 10.1103/PhysRevE.70.056131

    CrossRef Google Scholar

    [19] GÓMEZ S, JENSEN P, ARENAS A. Analysis of Community Structure in Networks of Correlated Data[J]. Physical Review E, 2009, 80(1): 016114. doi: 10.1103/PhysRevE.80.016114

    CrossRef Google Scholar

    [20] LANCICHINETTI A, FORTUNATO S, RADICCHI F. Benchmark Graphs for Testing Community Detection Algorithms[J]. Physical Review E, 2008, 78(4): 046110. doi: 10.1103/PhysRevE.78.046110

    CrossRef Google Scholar

    [21] DOREIAN P, MRVAR A. A Partitioning Approach to Structural Balance[J]. Social Networks, 1996, 18(2): 149-168. doi: 10.1016/0378-8733(95)00259-6

    CrossRef Google Scholar

    [22] HARARY F. On the Measurement of Structural Balance[J]. Behavioral Science, 1959, 4(4): 316-323.

    Google Scholar

    [23] FERLIGOJ A, KRAMBERGER A. An Analysis of the Slovene Parliamentary Parties Network[J]. Developments in Statistics and Methodology, 1996, 12: 209-216.

    Google Scholar

    [24] READ K E. Cultures of the Central Highlands, New Guinea[J]. Southwestern Journal of Anthropology, 1954, 10(1): 1-43. doi: 10.1086/soutjanth.10.1.3629074

    CrossRef Google Scholar

    [25] ODA K, MATSUOKA Y, FUNAHASHI A, et al. A Comprehensive Pathway Map of Epidermal Growth Factor Receptor Signaling[J]. Molecular Systems Biology, 2005, 1(1): 1-17.

    Google Scholar

    [26] ODA K, KIMURA T, MATSUOKA Y, Et Al. Molecular Interaction Map of a Macrophage[J]. AfCS Research Reports, 2004, 2(14): 1-12.

    Google Scholar

    [27] SHEN-ORR S S, MILO R, MANGAN S, et al. Network Motifs in the Transcriptional Regulation Network of Escherichia Coli[J]. Nature Genetics, 2002, 31(1): 64-68. doi: 10.1038/ng881

    CrossRef Google Scholar

    [28] LESKOVEC J, KREVL A. SNAP Datasets: Stanford Large Network Dataset Collection[EB/OL]. http://snap.stanford.edu/data .

    Google Scholar

    [29] JIA G B, CAI Z X, MUSOLESI M, et al. Community Detection in Social and Biological Networks Using Differential Evolution[C] //International Conference onLearningandIntelligentOptimization. Berlin, Heidelberg: Springer, 2012: 71-85.

    Google Scholar

    [30] XIAO J, WANG C, XU X K. Community Detection Based on Symbiotic Organisms Search and Neighborhood Information[J]. IEEE Transactions on Computational Social Systems, 2019, 6(6): 1257-1272. doi: 10.1109/TCSS.2019.2941988

    CrossRef Google Scholar

    [31] PIZZUTI C. GA-Net: A Genetic Algorithm for Community Detection in Social Networks[C] //Proceedings of the 10th International Conference on Parallel Problem Solving from Nature: PPSN X, 2008: 1081-1090.

    Google Scholar

    [32] ZHANG C, HEI X H, YANG D D, et al. A Memetic Particle Swarm Optimization Algorithm for Community Detection in Complex Networks[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2016, 30(2): 1659003. doi: 10.1142/S0218001416590035

    CrossRef Google Scholar

    [33] GONG M G, FU B, JIAO L C, et al. Memetic Algorithm for Community Detection in Networks[J]. Physical Review E, 2011, 84(5): 056101.

    Google Scholar

  • 加载中
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Figures(13)  /  Tables(6)

Export Citation
PDF
XML

Article Metrics

Article views(1150) PDF downloads(175) Cited by(0)

Access History

Other Articles By Authors

Community Detection in Signed Network Based on High-Order Information Local Search Strategy

    Corresponding author: XIAO Jing
  • Received Date: 07/06/2023
  • Available Online: 20/08/2023

Abstract: 

In existing signed network community detection methods, the local search strategy serves as an important component of the signed network community detection algorithm and can accelerate the convergence rate of the algorithm. However, most of the local search strategies in signed networks only utilize low-order structural information such as edges and nodes, thereby, neglecting the deeper and richer high-order structure that can be mined from signed networks. To enhance the performance of the existing signed network community detection local search strategy, this article proposes a local search strategy based on signed motifs. A new method based on signed motif for community migration was designed, which extends the traditional community numbering migration between binary tuples to ternary tuples. By comprehensively utilizing the low-order and high-order topological structural information of the signed network, the structural balance of nodes is further optimized, thereby, improving the convergence rate and detection performance of the algorithm. Experiments on synthetic and real-world networks demonstrated that the designed local search strategy exhibited good accuracy and quality.

    HTML

  • 开放科学(资源服务)标志码(OSID)：

  • 现实世界中很多复杂系统都可以用复杂网络模型来表示，例如：社交网络[1]、生物网络[2]、协作网络[3]等. 符号网络作为复杂网络中一种特殊的网络，是指边具有正或负符号属性的网络，其中正边和负边分别表示积极和消极的关系. 例如：神经元之间存在促进和抑制关系[4]; 社交关系中存在信任和不信任[5-6]. 因此，符号网络可以更好地描述节点之间的关系，符号网络相关研究具有重要的实际意义.

    由于负边的存在，使得符号网络中的社区检测和无符号网络中的社区检测具有明显区别. 在无符号网络中，社区结构定义为一组节点，这些节点在簇内具有密集连接，在簇之间具有稀疏连接. 对于符号网络，社区结构不仅由连接密度定义，也由连接的符号定义. 也就是说，社区内部的正链接密集而负链接稀疏，社区之间的负链接密集而正链接稀疏. 然而，在现实符号网络中，往往社区内部存在一些负链接，同样社区间也存在一些正链接，这也使符号网络社区检测面临巨大的挑战.

    目前针对符号网络社区检测问题的方法大致分为如下几类：基于谱聚类的方法[7-8]、基于概率生成模型的方法[9]、基于模块度优化的方法[10]等. 其中模块度优化是最典型的复杂网络社区检测方法之一，由于其高精确度和强可移植性等优点被广泛应用. 模因算法作为解决组合优化问题的一个非常强大的工具，适合于解决模块度优化的NP难问题，已被普遍应用于符号网络社区检测中. 它的灵感来源于自然系统模型，该模型将种群的进化适应与个体在其成员生命周期内的学习相结合[11]. 模因算法是一种基于群体的元启发式算法，它融合了不同的搜索策略，即全局搜索策略和局部搜索策略，在解决优化问题方面，模因算法已被证明比传统进化算法更高效[10].

    局部搜索策略作为模因算法中重要组成部分之一，它能极大地提高全局搜索算法寻找全局最优解的速度，并辅助提升全局最优化性能. 近年来，局部搜索策略常被学者们用于加速全局算法的收敛. 如Li等[10]提出并比较了EA-SN和CSA-SN两种进化算法，以及EAHC-SN和CSAHC-SN两种模因算法. 模因算法在进化算法基础上使用了爬山策略，仅对最优种群个体进行局部搜索操作，每次迭代都使用贪婪算法对每个节点选择最优适应度，实验表明模因算法优于进化算法. Amelio等[12]提出了一种结合遗传算法和局部搜索的符号网络多目标社区检测方法，其局部搜索策略在爬山策略的基础上增加了仅将节点移动至正相连的邻居节点社区的限定条件，若符号模块度增加则保留移动，反之则不移动. Che等[13]提出了一种新颖的模因算法(MACD-SN)，其中结合了一种新的局部搜索算法，能够以一定的概率跳出局部最佳结果，并快速接近全局最优值.

    上述方法仅简单地利用节点和连边等低阶结构信息进行局部搜索操作，忽略了网络中广泛存在且具有统计意义的高阶组织结构，如网络模体[14-15]等，因此对于提升符号网络社区检测性能相对有限. 模体是复杂网络中的基本拓扑和功能单元[14-16]，而符号模体作为一种连边具有正或负符号属性的特殊模体，可展现出符号网络节点间更丰富且有意义的拓扑连接关系，对于局部搜索操作具有很强的指导性意义.

    针对上述问题，本研究提出了一种基于符号模体的三元组局部搜索策略(Triad Local Search，TLS). 设计了一种基于符号模体进行社区迁移的新方法，将传统社区编号在二元组之间的迁移扩展到了三元组，综合利用符号网络低阶和高阶拓扑结构信息，进一步优化节点的结构平衡性，提升算法收敛速度. 为验证局部策略的有效性，TLS算法同差分进化策略构建成模因算法DE-SN，实验结果表明TLS算法在社区划分的精确性和质量性表现出一定优势. 将TLS算法迁移至元启发式优化算法为共生生物搜索算法和遗传算法的模因算法中，在模型网络和实证网络上均验证了新算法的通用性.

1.   基础概念和数据集

    1.1.   符号网络定义

  • 符号网络社区检测旨在挖掘社区内部正链接密且社区之间负链接密集的社区划分结构. 本研究主要考虑无向符号网络. 一个符号网络可以抽象为一个图G=(V，E)，其中V={v1，v2，…，vn}代表节点(顶点)集合，E={(vi，vj)|vi，vj∈V∩i≠j}代表边(链接)集合. 图G还可以表示成加权邻接矩阵A=(Aij)n×n，其中n代表节点数目，若节点vi和vj之间存在正边(负边)相连，则Aij=1(Aij=-1); 若节点vi和vj之间不存在连边，则Aij=0. 图G的一个社区划分可表示为C={C1，C2，…，Ck}且Ci⊂V，其中k代表社区数目，表示由一组节点组成的第i个社区. 符号网络上的社区检测问题可以定义为公式(1)的形式[17].

    式中：p，q=1，2，…，k，且p≠q.

    • 1.2.   评价指标

    1.2.1.   符号模块度QS

  • 在无符号网络社区检测中，Newman等[18]定义的模块度函数是最常用的指标之一，但由于符号网络中存在负边，因此原始的模块度Q无法直接应用于符号网络. Gómez等[19]基于正边和负边的贡献，改进了模块度定义，使其扩展到符号网络. 本研究中，将符号模块度QS作为目标函数，符号网络模块度QS定义为：

    式中：w+和w-分别为图G中所有正链接和负链接的权重总和; wij为节点i和节点j之间连边的权重; wi+(wj+)为节点i(j)的正权重总和; wi-(wj-)为节点i(j)的负权重总和; Ci(Cj)为节点i(j)所属社区，i，j=1，2，…，k; δ(Ci，Cj)为罚函数，若节点i和节点j同属于一个社区，则δ(Ci，Cj)=1，否则为0.

    • 1.2.2.   归一化互信息

  • 归一化互信息(Normalized Mutual Information，NMI)[20]可用于评估算法检测结果的精确性. 假设A和B是一个网络的两个划分，那么归一化互信息定义为：

    式中：N为网络的节点数量; C为混淆矩阵; Cij为同时隶属于A中的第i个社区和B中第j个社区的节点数量; CA和CB分别为划分A和B中的社区数量; Ci和Cj分别为C中第i行和第j列元素的和. NMI取值范围为[0, 1]，越接近1，表示两个划分越相似.

    • 1.2.3.   节点Frustration指数

  • Frustration指数[21-22]是目前衡量符号网络结构平衡最广泛的指标之一，它统计的是社区内部的负链接数量与社区之间的正链接数量的总数，表示社区的不平衡程度，Frustration指数越低代表社区划分越稳定. Frustration指数(Frustration of Node，FN)可定义为：

    式中：vi为对象节点i; Ci为节点i所属社区; δ(Ci，Cj)为罚函数; FN(vi)表示节点i的连边中在社区内部的负链接数量与社区之间的正链接数量的总数，它代表节点i的不平衡程度，值越小节点i越稳定，当FN=0时，节点i达到结构平衡.

    • 1.3.   数据集

    1.3.1.   模型网络

  • 选择Yang等[17]设计的随机生成符号网络模型，生成实验使用的合成符号网络，该模型可以描述为：

    式中：c为网络中社区的数量; n为每个社区包含的节点数量; k为每个节点的度; pin为每个节点连接同一社区中其他节点的概率; p-为负链接出现在社区内的概率; p+为正链接出现在社区之间的概率. 为模拟现实世界中不平衡网络结构，并且控制生成的社区内部和社区之间的连边概率相同，因此pin取值为0.5，本研究中生成了以下3种不同的不平衡网络对各局部策略进行评估.

    ① SG(4，32，32，0.5，0，p+)：p+以0.1为间隔在[0, 1]范围内取值. 该网络由128个节点构成，分成4个社区，每个社区包含32个节点. 每个节点的度为32，分别以0.5的比率连接社区内部和社区外部的节点. 社区内部负链接出现的概率为0，社区之间相连以p+比率为正链接.

    ② SG(4，32，32，0.5，p-，0)：p-以0.1为间隔在[0, 1]范围内取值. 该网络社区之间正链接出现的概率为0，社区内部相连以p-比率为负链接.

    ③ SG(4，32，32，0.5，p-，p+)：p-和p+分别以0.1为间隔在[0，0.5]范围内取值. 该网络社区内部相连以p-比率为负链接，社区之间相连以p+比率为正链接.

    • 1.3.2.   实证网络

  • 为检验算法在现实世界网络中的可行性及性能优势，选择2个社交网络和4个生物网络作为实验数据. 社交网络包括描述斯洛文尼亚议会关系的网络(Slovene Parliamentary Party，SPP)[23]和描述新几内亚高地的网络(Gahuku-Gama Subtribes，GGS)[24]. 生物网络分别为EGFR网络[25](表皮生长因子受体途径网络)、Macrophage网络[26](巨噬细胞网络)、Yeast网络[15](酵母网络)和Ecoli网络[27](大肠杆菌的基因调控网络). 以上实证网络都从SNAP[28]中获得，具体信息如表 1所示.

2.   算法描述

  • 本节首先介绍现有符号网络中具有代表性的局部搜索算法，再重点阐述提出的三元组局部搜索策略TLS. 局部搜索策略是模因算法优于传统进化算法的主要原因之一，以其收敛速度快、扩展性强等优势，常被用于提高求解效率和精度. 如图 1所示的模因算法流程包括生成初始种群、计算所有个体适应度值、元启发式优化算法、更新个体适应度值和局部搜索策略，本研究提出了一种三元组局部搜索策略(Triad Local Search，TLS)应用于模因框架，旨在提升其在符号网络社区检测的性能. 为了展示提出策略的优越性，在模因框架中选取了差分进化算法[29](Differential Evolution，DE)作为元启发式优化算法，与TLS策略构成DE-SNTLS框架进行实验验证. 同时，又在模因框架中选取了共生生物搜索[30](Symbiotic Organisms Search，SOS)和遗传算法[31] (Genetic Algorithm，GA)作为元启发式优化算法，与TLS策略构成SOS-SNTLS和GA-SNTLS框架，验证本研究提出策略的通用性.

    • 2.1.   基于低阶信息的局部搜索算法

  • 现有符号网络上代表性的局部搜索算法有以下几种：爬山算法[32-33]、利用正边信息的改进爬山算法[12]以及模因算法MACD-SN[13]中具有概率跳出局部最优的局部搜索策略.

    • 2.1.1.   爬山算法

  • 爬山算法(Hill Climbing，HC)是一种局部择优的启发式方法，核心思想是贪婪地寻找每个节点局部最优适应度，缺点是极易陷入局部最优. 它是一种经典的局部搜索算法，被广泛使用于无符号网络社区检测和符号网络社区检测，如Gong等[33]将爬山策略与算法相结合实现无符号网络社区检测，Li等[10]在其基础上将爬山策略应用于符号网络.

    HC算法的详细说明如图 2所示，9个节点对应6个社区的结构示例图为EGFR网络提取的一个子图. 在一次局部搜索操作过程中，节点A被选作中心节点(对象节点)，其对应的社区编号为1. 初始子图中，中心节点有一个负边相连的邻居节点B和4个正边相连的邻居节点{C，E，G，H}，其社区编号分别对应为{2，3，4，5，6}，故节点A有4条不平衡连边(图中红色连边)，即节点A初始的FN值为4. 在HC操作中，首先将中心节点所有邻居节点的社区作为候选社区(满足条件的邻居社区)，然后分别计算节点A归属于每个候选社区后的符号模块度，最后选择符号模块度最大的候选社区作为迁移社区. 图中当中心节点的社区为6时取得QS最大值为0.143，因此社区编号6作为迁移社区从迁移节点(被选中的候选节点)迁移至中心节点，即实现了社区编号在二元组之间的迁移.

    HC操作后中心节点A的社区编号更改为6，节点A的FN值降至3，QS从0.087优化至0.143，达到HC操作的最优结果. HC算法未利用符号信息，而是贪婪地寻找符号模块度最大的迁移社区，此操作极易使算法陷入局部最优，并且HC算法缺少跳出局部最优的操作.

    • 2.1.2.   改进爬山算法

  • Amelio等[12]提出算法中使用的局部搜索策略是在爬山策略的基础上，增加了仅将节点移动至正相连的邻居节点社区的限定条件. 改进爬山策略(Hill Climbing Using Positive，HC-P)简单利用了符号信息，使爬山策略更适用于符号网络.

    HC-P算法详细说明如图 3所示，唯一与HC算法操作不同之处在于中心节点只考虑将正边相连的邻居社区{3，4，5，6}作为候选社区，而负边相连的邻居社区2不做考虑，最后从候选社区中选择符号模块度最大社区作为迁移社区. HC-P操作后中心节点A的社区同样更改为6，节点A的FN值也降至3，QS从0.087优化至0.143，达到HC-P操作的最优结果. HC-P算法利用符号信息对候选社区进行筛选，相较于HC算法的效率和性能有所提升，但HC-P算法并未对爬山策略极易陷入局部最优的缺陷进行改进.

    • 2.1.3.   MACD-SN中的局部搜索策略

  • Che等[13]提出的符号网络社区检测算法中使用了局部搜索策略(Local Seek，LS)，使用作者自定义的算子(社区失衡度CID，表示同社区内节点的平均Frustration值)作为局部优化目标. LS算法结合了符号信息，并引入概率ρ，一定概率接受较差的个体，有利于算法跳出局部最优解.

    LS算法的详细说明如图 4所示，在同一个子图上，节点A初始的FN值为4. 首先，LS算法将正边相连的邻居社区{3，4，5，6}作为候选社区，若无正边相连的邻居社区，才会将负边相连的邻居社区作为候选社区. 其次，选择CID最小的候选社区6再对比前后QS，若QS增大或者存在一定概率ρ情况下，则将该候选社区作为迁移社区; 反之，不进行社区迁移，中心节点社区保持不变. 由于节点A的社区改为6时，QS增大至0.143，因此，LS操作后节点A的社区更换为6，且FN值为3，达到LS操作的最优结果.

    但对于真实社区划分为社区间正边数量较多的网络，受局部优化目标影响，LS算法容易将正边相连不同社区的节点划分成同一社区，从而导致社区划分质量不佳.

    • 2.2.   基于高阶信息的局部搜索算法

  • 上一小节中的3种基于低阶信息的局部搜索算法，社区只在二元组之间进行迁移，即从迁移节点迁移至中心节点，这种迁移方式的效率不高，每次操作只对中心节点进行社区调整，中心节点邻域内的不合理连边调整缓慢. 此外，单纯关注局部目标来选择局部优化最佳的候选社区(候选节点)作为迁移对象，往往会陷入局部最优的社区划分.

    为解决上述问题，提出一种基于符号模体的三元组局部搜索算法(Triad Local Search，TLS)，可以有效提高收敛速度和局部性能. 核心思想为通过综合利用符号网络低阶和高阶拓扑结构信息，优化节点的不平衡程度，尽可能达到节点的结构平衡，从而提升社区划分质量. TLS算法对符号网络高阶和低阶信息的利用，分别体现在基于三阶符号模体进行三元组社区迁移和依据低阶连边符号信息选择候选节点. 三元组社区迁移是将迁移节点迁移至中心节点的社区编号再传递给其他候选节点，为更准确表示该迁移模式并探索更深层的规律，本研究使用三阶符号模体表示三元组社区迁移，并从中挖掘高阶结构信息，进一步指导局部搜索操作.

    下面详细介绍TLS算法具体实现. 研究中主要考虑无向的三阶符号模体，如图 5所示一共有7个三阶的无向符号模体，其中S1，S2和S3只有两条连边. 符号模体上的社区迁移需要满足以下2个条件：

    1) 根据正链接和负链接的符号属性，社区迁移只发生在节点间的正链接，而社区不可以在负链接进行迁移.

    2) 模体中的社区迁移只能通过中心节点进行，两个都为非中心节点，无法进行社区迁移.

    图 5中的7种符号模体依据中心节点位置的不同，将会有12种不同的符号模体. 然而，研究发现并非12种符号模体都能够满足符号模体的社区迁移条件，只有图 6中的3种符号模体满足迁移条件，其中红色节点表示中心节点，将该模体命名为中心节点符号模体，并做如下定义：

    定义1   中心节点符号模体(Central Node Signed Motif，SC). 满足中心节点职能的符号模体称为中心节点符号模体，即中心节点符号模体可以让中心节点实现社区信息的接收和传递.

    由于非中心节点符号模体不满足社区迁移条件，即不参与社区迁移，因此在TLS算法中只需要关注3种中心节点符号模体以提高计算效率. 算法1为TLS算法伪代码，主要步骤如下：

    1) 随机选择目标个体的若干个节点进行优化，获得中心节点正边相连的邻居节点(作为候选节点)及对应社区编号(第1行至第4行);

    2) 中心节点在候选节点中随机选择一个节点作为迁移节点，并将迁移节点的迁移社区传递给中心节点，实现二元组之间的社区迁移(第5行至第6行);

    3) 寻找所有包含中心节点和迁移节点的中心节点符号模体，为加快代码执行效率，可将寻找模体的操作简化为求中心节点正边相连且不同社区的邻居节点. 在进行社区迁移时进行条件判断，若传递后的符号模块度大于原符号模块度或在一定阈值ρ内，则确认传递，邻居节点社区编号替换为中心节点的社区编号，从而实现了社区编号在三元组(模体)之间的迁移. 否则，传递失败，邻居节点社区编号保持不变(第7行至第16行).

    算法1    TLS算法
    输入：目标个体X，邻接矩阵A，阈值参数ρ
    输出：优化后新个体Xnew
    1.     nrand=random(1，n)
    2.      for Nc=1 to nrand do
    3.        neighborsp=get neighbors positive(Nc)
    4.        commID(neighborsp)=X[neighborsp]
    5.        Nm=random(neighborsp)
    6.        commID(Nc)=commID(Nm)
    7.        for each np∈neighborsp do
    8.          if commID(np)≠commID(Nc) then
    9.            QSold=compute QS
    10.            QSnew=compute QS
    11.            if QSnew＞QSold or random number r≤ρ then
    12.              commID(np)=commID(Nc)
    13.            end if
    14.          end if
    15.        end for
    16.      end for
    17.      输出优化后新个体Xnew

    TLS算法的详细说明如图 7所示，同样以EGFR网络子图为例，在一次随机选择若干个节点进行局部搜索操作时，节点A被选作中心节点，其对应的社区编号为1. 在节点A进行TLS操作时，初始的FN值为4. 首先，检查中心节点所有邻居节点，可以发现有一个负边相连的邻居节点B和4个正边相连的邻居节点{C，E，G，H}，其社区编号分别对应为{2，3，4，5，6}. 其次，将正边相连的邻居节点作为候选节点，并随机选择一个候选节点E作为迁移节点，迁移节点E将迁移社区4传递给中心节点A，此时节点A的FN值减小至3，QS降为0.066. 然后，寻找所有包含中心节点和迁移节点的中心节点符号模体，并逐个进行社区迁移. 如图有3个满足条件的符号模体，分别为S1(E，A，C)，S4(E，A，G)和S5(E，A，H). 三元组社区迁移是否成功在于迁移后的符号模块度是否增大，并存在概率ρ接受较差情况. 因为不同模体的判别顺序不影响最终结果，所以先对S1(E，A，C)进行判别，发现节点C社区更改为4后，FN值减小至2，QS增大至0.092，符合判别条件，即接受社区迁移. 再对S4(E，A，G)进行判别，节点G社区更改为4后，FN值减小至1，QS增大至0.184，接受社区迁移. 最后对S5(E，A，H)进行判别，若节点H的社区更改为4，则QS降至0.002，假设此时未能达到概率ρ，即不接受这个较差的情况，那么最终TLS操作将以QS为0.184的个体输出.

    上述操作不难发现，TLS算法与传统的局部策略截然不同. TLS算法不依赖局部目标随机选择候选社区(候选节点)方式，有助于扩大解空间，避免陷入局部最优解. 虽然随机选择候选社区会获得更差的社区结构，如图 7中QS不升反降. 但在TLS操作后期，以节点的结构平衡(FN=0)为优化方向的三元组社区迁移，能够加速中心节点及邻域收敛至的最优社区划分. 以EGFR网络子图为例，TLS算法能够获得3种对比算法都无法获得的社区划分，并且相较于三者的社区划分质量更优.

    • 2.3.   算法复杂度分析

  • HC算法、HC-P算法和LS算法的平均时间复杂度都为O(n*d)，其中d代表网络G中节点的平均度. 在最差的情况下，网络G为完全图，因此3种算法的时间复杂度为O(n2). TLS算法平均时间复杂度同样为O(n*d)，最差时间复杂度为O(n2)，但不同于其他3种算法，并不是对一个目标个体的所有节点都进行局部操作，而是随机选择若干个节点，实际运行效率会更高.

3.   实验结果与分析

  • 本节将对提出TLS算法的性能进行验证，与现有典型的局部搜索算法进行对比，分别从不同正负边比例的模型网络和实证网络的实验来检验分析.

    • 3.1.   实验设置

    3.1.1.   对比策略

  • 为检验DE-SN算法在符号网络中的性能，并重点验证提出的三元组局部搜索算法TLS与其他局部策略相比更具优势，将DE-SN算法中的局部策略分别替换为HC算法、HC-P算法、LS算法，从而可以得到DE-SNHC，DE-SNHC-P，DE-SNLS 3种对比算法.

    • 3.1.2.   参数设置

  • 上述搜索策略参数设置均采用原文献中的推荐值，其中DE算法中变异因子F取值为0.9，交叉因子CR取值为0.3. DE-SN算法设置种群规模NP为100，最大迭代次数tmax为100. 为保持种群个体多样性及探索能力，防止算法过早收敛，仅选择模块度值较为优异的前10%个体作为目标个体进行局部操作. 另外，以下实验中LS局部搜索策略参数ρ使用原文推荐值0.15.

    • 3.2.   模型网络性能测试

  • 首先，为检验社区之间的正边对DE-SN算法检测性能的影响，在SG(4，32，32，0.5，0，p+)网络集合上，对DE-SN算法与各对比算法进行性能测试. TLS算法的阈值参数ρ取值为0进行测试. 所有算法在模型网络上的实验结果如图 8a所示，图中数据点代表各算法分别在11个SG(4，32，32，0.5，0，p+)网络上独立运行20次得出社区划分NMI值的平均值.

    从图 8a所示结果中可知，当p+取值为[0，0.5]时，DE-SNTLS，DE-SNHC和DE-SNHC-P算法在SG(4，32，32，0.5，0，p+)网络上均能够稳定地检测得到全局最优社区划分，对应NMI平均值均达到1.0. 当p+取值为[0.6，1]时，DE-SNHC和DE-SNHC-P算法NMI平均值接近1.0. p+为0.8时，DE-SNTLS的NMI值为1. 然而DE-SNLS算法的性能表现相对不佳，当p+≤0.3时，DE-SNLS算法的性能逐渐下降. 当p+＞0.3时，性能趋于相对平衡. DE-SNTLS算法在SG(4，32，32，0.5，0，p+)网络上的检测精度显著优于DE-SNLS算法，且与DE-SNHC和DE-SNHC-P算法检测精度大致相同.

    其次，为检验社区内部的负边对DE-SN算法检测性能的影响，在SG(4，32，32，0.5，p-，0)网络集合上，同样进行各DE-SN算法的测试及对比分析. TLS算法的阈值参数ρ取值为0.15进行测试. 图 8b中数据点代表各算法分别在11个SG(4，32，32，0.5，p-，0)网络上独立运行20次所得社区划分NMI值的平均值.

    从图 8b所示结果可以看出，DE-SNTLS在SG(4，32，32，0.5，p-，0)网络上能够获得相对最优的NMI，与其他对比算法相比具有较为明显的性能优势. DE-SNHC在p-＞0.2时，NMI值下降趋势最为明显，且逐渐趋于0. DE-SNTLS，DE-SNHC-P和DE-SNLS在p-＞0.3时，所检测得NMI值开始逐渐下降，而DE-SNTLS整体检测性能下降最为缓慢，对于任意p-的取值，都能够优于其他算法.

    最后，为检验社区之间的正边和社区内部的负边同时存在对DE-SN算法检测性能的影响. 在SG(4，32，32，0.5，p-，p+)网络集合上，进行各DE-SN算法的测试及对比分析. 此时，TLS算法的阈值参数ρ取值为0进行测试. 各图中数据点代表各算法在36个网络上独立运行20次所得社区划分NMI值的平均值.

    如图 9所示，每张热力子图的每一小块表示对应p-和p+取值，算法20次检测得到NMI均值. DE-SNTLS与DE-SNHC和DE-SNHC-P算法检测结果十分相近，但仔细观察可以发现，在(p-，p+)=(0.4，0)，(p-，p+)=(0.4，0.1)，(p-，p+)=(0.5，0)和(p-，p+)=(0.5，0.1)4个块的检测精确度要显著高于DE-SNHC和DE-SNHC-P算法检测精确度. 然而，DE-SNLS的检测结果相对较差，仅在(p-，p+)=(0，0)和(p-，p+)=(0.1，0)时，检测得NMI值为1.0，在(p-，p+)=(0.2，0)和(p-，p+)=(0.3，0)时，检测得NMI值接近1.

    以上模型网络的实验表明，TLS算法相较于其他代表性局部搜索算法，在精确性和稳定性上能够表现出一定优势.

    • 3.3.   实证网络性能测试

  • 将DE-SN算法在表 1所示2个具有真实社区划分的符号社交网络和4个没有真实社区划分的符号生物网络上进行测试，并与算法进行对比，社交网络和生物网络实验结果分别如表 2和表 3所示. 此时，TLS算法的阈值参数ρ取值为0，同时为确保生物网络检测尽可能达到收敛，迭代次数tmax取值为200. 表 3中数据为各算法在每个网络上独立运行20次，所得社区划分对应符号模块度QS的平均值和NMI的平均值.

    表 3中的实验结果表明，DE-SNTLS能够在社交网络上达到最优社区划分的同时，能在所有生物网络上获得比对比算法更优的QS平均值. TLS算法相比较于其他典型代表性的局部搜索算法，具有较好的质量性和稳定性.

4.   通用性和鲁棒性检验

  • 为深入验证TLS算法可提升符号网络社区检测的局部搜索性能，并检验TLS算法在不同优化策略的模因算法上的通用性. 基于模因算法框架，选择共生生物搜索和遗传算法分别作为模因算法中的元启发式算法进行全局搜索，TLS算法作为局部搜索策略，构建SOS-SN算法和GA-SN算法2个新的模因算法. 同上一节中的对比算法、参数设置和测试数据集对各算法进行实验.

    • 4.1.   SOS-SN算法检验分析

  • SOS-SN算法在模型网络上的实验结果如图 10a和10b所示. 从图 10a的实验结果发现，对于任意p+的取值，SOS-SNTLS与SOS-SNHC和SOS-SNHC-P大致相同，当p+取值为[0，0.5]时，3种算法检测得NMI均值都为1.0，当p+取值为[0.5，1]时，3种算法取得NMI均值近似1.0. 而SOS-SNLS的检测性能依旧随着p+的增大而整体呈现下降趋势. 从图 10b的实验结果发现，对于不同p-取值，SOS-SNTLS依旧能够保持相对最优的检测精度.

    如图 11检验社区之间的正边和社区内部的负边同时存在对SOS-SN算法检测性能的影响，SOS-SNTLS依旧能够明显的优于SOS-SNLS检测结果，并且在(p-，p+)=(0.4，0)，(p-，p+)=(0.4，0.1)，(p-，p+)=(0.5，0)和(p-，p+)=(0.5，0.1) 4个块的检测精确度依旧高于SOS-SNHC和SOS-SNHC-P法检测精确度.

    在实证网络上对SOS-SN算法进行性能检验，由于SPP网络和GGS网络相对简单，所有算法都能获得最优社区划分，故不再展示. 如表 4所示为各个SOS-SN算法在符号生物网络上的检测结果，TLS算法在生物网络上与对比算法相比依旧表现出明显的优势.

    • 4.2.   GA-SN算法检验分析

  • GA-SN算法在模型网络上的实验结果如图 12a和12b所示. 从图 12a的实验结果发现，GA-SNTLS，GA-SNHC和GA-SNHC-P在GA-SN算法上的实验结果十分相近. 而GA-SNLS的检测性能依旧较差，当p+取值为[0，0.5]时，检测精度缓慢下降，但当p+＞0.5时，GA-SNLS的检测性能下降明显. 从图 12b的实验结果发现，GA-SNTLS的检测性能依旧能够保持相对最优. 如图 13为4种算法的热力图所示，GA-SNTLS依旧能够在大多数的区块上优于其他算法的检测结果. 同样在符号生物网络上对GA-SN算法进行性能检验. 如表 5符号生物网络上，除了在Macrophage网络上，GA-SNLS的质量性检测结果要优于GA-SNTLS. 在其他生物网络上，GA-SNTLS的检测结果都要优于其他对比算法.

    根据以上所有实验结果表明，在SOS-SN算法和GA-SN算法中，TLS算法辅助全局搜索算法的社区检测性能依旧普遍优于其他对比局部搜索策略. 本研究提出的TLS算法可以与不同全局搜索算法相结合，并辅助算法获得更优的社区划分结果，从而验证了TLS算法拥有较好的通用性和鲁棒性.

5.   结论

  • 本研究提出了一种基于符号模体的三元组局部搜索算法TLS. 该算法采用了一种基于符号模体进行社区迁移的新方法，将传统社区编号在二元组之间的迁移扩展到了三元组，综合利用了符号网络低阶和高阶拓扑结构信息，进一步优化节点的结构平衡性，提升算法收敛速度和检测性能. 为验证提出的局部搜索算法社区检测性能，将TLS算法同差分进化策略构建成模因算法DE-SN，在模型网络和不同规模及特性的实证网络上进行了检验，并分别将爬山策略HC、改进爬山策略HC-P和MACD-SN算法中使用的局部搜索方法LS作为对比局部策略进行对比分析. 实验结果表明，TLS算法能够在模型网络上获得更加精确和稳定的检测结果，并且在实证网络上同样表现出相对较好的质量性和稳定性. 此外，通过将TLS算法迁移至元启发式优化算法为共生生物搜索算法和遗传算法的模因算法中，分别构建了SOS-SN算法和GA-SN算法，在模型网络和实证网络上均验证了TLS算法的通用性.

    本研究提升了现有符号网络社区检测的局部搜索策略性能，拓展了模体理论的应用场景，有助于加深对网络结构和功能特性的理解. 未来研究中将扩展到有向符号网络和加权符号网络等，使提出的局部搜索算法能够适应更多不同类型复杂网络应用需求.

Figure (13)  Table (6) Reference (33)

Catalog

    Copyright Journal of Southwest University Natural Science Edition

    Address： Tel：023-68254576, 68252540, 68366165,68366917 E-mail：lkxb@swu.edu.cn

    Supported by:Beijing Renhe Information Technology Co. Ltd

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return