《Computer Networks》：A-CLA: A Novel Adaptive Cellular Learning Automata Approach for Uncovering Communities in Complex Networks
编辑推荐：
社区检测算法研究：提出自适应细胞学习自动机（A-CLA），结合双反馈机制和节点自适应学习率，在复杂网络中有效检测社区结构，评估模块化、NMI、F1等指标，在模块化强的数据集表现优异但计算时间高于快速算法。
阿米尔侯赛因·法提纳维德（Amirhossein Fathinavid）| 阿米尔侯赛因·肖什塔里·塔瓦索利（Amirhossein Shoshtari Tavasoli）
伊朗哈马丹伊斯兰自由大学工程学院哈马丹分校计算机工程系
摘要
社区检测是复杂网络分析中的一个基本任务，旨在识别具有密集内部连接和稀疏外部连接的节点群体。传统算法往往难以在适应性、准确性和可扩展性之间取得平衡。我们提出了自适应细胞学习自动机（Adaptive Cellular Learning Automata，简称A-CLA），它是细胞学习自动机框架的扩展，结合了双重局部-全局反馈和节点特定的自适应学习率。这种设计使A-CLA能够在保持全局一致性的同时适应细粒度的局部结构。我们使用模块性、标准化互信息（Normalized Mutual Information，简称NMI）、F1分数、边密度和介数中心性等指标，在来自社会、生物和技术领域的十六个真实世界和合成网络上评估了A-CLA的性能。结果表明，A-CLA在模块性、稳定的NMI和适中的F1分数方面表现优异，并且在具有强模块结构的网络（例如Dolphin、Karate Club、Diseasome、NetScience）中显著提高了边密度和社区凝聚力。尽管收敛性稳定，但其运行时间比Louvain等快速启发式算法略长。总体而言，A-CLA为非重叠社区检测提供了一个灵活的框架，并为考虑重叠情况的扩展和大规模并行实现指明了有希望的方向。
引言
网络为建模各种现实世界系统提供了强大的框架，从社会互动[1]和技术基础设施[2,3]到生物过程[4]和生态系统[5]。从根本上说，网络由代表实体的节点或顶点以及代表它们之间关系的边或链接组成[6,7]。这种建模方法在社会科学[8]、生物学[9]、物理学[10]和计算机科学[11,12]等不同领域证明了其价值，因为在复杂系统中识别模式可以揭示其潜在的动态[13]。在各种类型的网络中，复杂网络特别引人注目[14]，因为它们具有独特的结构特征，如较短的平均路径长度、较高的聚类系数和不均匀的度分布[15,16]。这些网络捕捉到了复杂且往往不可预测的结构，包括小世界效应和无标度分布[17,18]。例如，Facebook和Twitter等社交媒体平台中，节点代表用户，边表示它们之间的互动。在这样的网络中，社区结构自然形成，即内部连接比与网络其他部分更密集的节点簇[19,20]。识别这些社区结构对于检测有影响力的节点、理解信息流动以及揭示网络中的隐藏模式至关重要[21]。社区检测专注于识别那些内部连接性强于外部连接性的节点群体。已经开发了多种算法来应对这一挑战，通过优化不同的标准。其中最广泛使用的方法是Louvain方法[22]，它最大化了模块性[23]，即社区内部和外部连接之间的密度差异。
其他社区检测算法，如GN[24]、Walktrap、标签传播算法（Label Propagation，简称LPA）[25]、主导特征向量方法（Leading Eigenvector method[26]、K-means[27]和随机游走算法[28,29]，也针对网络的特定特征进行了开发[30]。团簇渗透方法（Clique Percolation Method，简称CPM）[31]通过重叠团簇的链来识别社区，适用于密集网络，但在稀疏或大规模图上计算要求较高。说话者-听者标签传播算法（Speaker–Listener Label Propagation Algorithm，简称SLPA）[32]通过交替扮演说话者和听者的角色，能够在复杂网络中检测到重叠社区。Leiden算法[33]是对Louvain的改进，提高了分割的质量和稳定性，确保了社区的良好连接性。DEMON（Democratic Estimate of the Modular Organization of a Network）[34]利用局部自我网络来检测社区并将它们全局合并，为大型数据集提供了可扩展性。这些方法虽然有效，但通常优先考虑单一优化目标。例如，Louvain在模块性方面表现出色，但在噪声较大或异构网络中，在标准化互信息（NMI）或F1分数方面的表现可能较差。同样，生成网络模型[35]，如Watts–Strogatz[36]和Barabási-Albert[37]，也因其结构特性（包括边密度）而被研究，尽管它们并非主要为社区检测而设计。
常用于评估这些算法的基准数据集包括：Dolphin（一个基于频繁关联的62只海豚的社会网络）、C. elegans（一个表示C. elegans神经连接的有向加权网络）、Diseasome（一个连接疾病和疾病基因的网络）、Karate Club（一个大学空手道俱乐部34名成员之间的友谊网络）、Netscience（一个从事网络理论研究的科学家的合著网络）、Les Misérables（小说《悲惨世界》中角色共现的加权网络）、Yeast（酵母中的蛋白质-蛋白质相互作用网络[38]）、Candida（关注Candida物种中微卫星标记的遗传数据[39]）、Danio rerio（一个关注斑马鱼的遗传研究数据集[40]）。每个数据集都具有独特的结构特征，使得在不同条件下测试社区检测方法的稳健性和准确性变得有效。
基于优化的最新进展引入了学习自动机（Learning Automata，简称LA）作为社区检测的一个有前景的范式。与必须在网络修改后重新运行的传统算法不同，LA采用动态奖励-惩罚机制，使节点能够根据反馈迭代调整它们的社区分配[41]。在LA的基础上，细胞学习自动机（Cellular Learning Automata，简称CLA）[42]整合了局部互动，提高了在密集连接网络中的检测能力[43]。然而，之前的基于CLA的方法通常使用固定的学习率，并且仅依赖局部强化，这可能会减慢收敛速度并降低在异构或稀疏图中的稳健性。
在这项研究中，我们提出了自适应细胞学习自动机（Adaptive Cellular Learning Automata，简称A-CLA），它是CLA的概念性扩展，而不仅仅是参数的增量调整。A-CLA引入了三项创新：（i）结合了邻域强化和基于模块性的全局稳定的双重局部-全局反馈机制，（ii）根据度、密度和介数中心性确定的节点特定自适应学习率，以及（iii）用于稳定性的改进收敛标准。这些机制共同使A-CLA在保持合理的NMI和适中的F1分数的同时，实现了持续的高模块性和稳定的收敛性。A-CLA优先考虑连贯、分离良好的分割，而不是以召回率为驱动的重叠建模——这一明确的设计选择解释了它的优势和权衡[44]。
本文的其余部分组织如下：第2节回顾相关工作。第3节介绍理论基础和实验参数。第4节详细说明A-CLA的算法框架。第5节报告实验结果并进行比较分析，第6节总结研究结果和未来研究的方向。
相关研究
社区检测是网络科学中的一个基本研究领域，专注于识别网络中的隐藏结构。经典算法，如Newman和Girvan提出的Girvan-Newman（GN）方法[45]，会移除介数较高的边并提供直观的结果，但可扩展性较差；而Blondel等人开发的基于模块性的Louvain方法[22]由于其可扩展性和准确性，仍然是应用最广泛的技术之一。
初步
在本节中，我们概述了基本概念，包括模型参数和自动机原理。使用了几种社区检测性能指标来评估所提算法在不同数据集上的有效性。
提出的方法
在提出的方法中，我们引入了自适应细胞学习自动机（Adaptive Cellular Learning Automata，简称A-CLA），这是一种用于复杂网络中社区检测的增强框架。A-CLA建立在经典细胞学习自动机（Cellular Learning Automata，简称CLA）模型的基础上，并通过两项关键创新解决了其局限性。
与依赖静态学习率的传统CLA不同，A-CLA整合了动态学习适应机制，能够根据网络特征（如局部）自动调整学习率。
结果
为了评估所提出的A-CLA方法的有效性，我们在第1节介绍的数据集上进行了实验。评估考虑了多个性能指标，包括模块性（第5.3节）、标准化互信息（NMI，第5.4节）、F1分数（第5.5节）、边密度（第5.6节）、介数中心性（第5.7节）和收敛速度（第5.8节）。此外，还考虑了每个数据集的一般特征，如节点数和边数。
结论
本研究提出了基于自动机的社区检测框架——自适应细胞学习自动机（Adaptive Cellular Learning Automata，简称A-CLA），并全面评估了其在各种社会和生物网络中的表现。评估涵盖了多个性能维度，包括模块性、标准化互信息、F1分数、边密度、介数中心性、与重叠相关的行为和收敛动态，确保了结构和统计上的严谨性。
主要
未来工作
尽管这项工作侧重于静态、非重叠的社区检测，但A-CLA的自适应双重反馈设计并不限于这种设置。一个自然的扩展是加入考虑重叠情况的强化机制，使自动机能够保持多个高概率行为，从而支持多成员社区。此外，局部-全局反馈机制可以通过启用时变强化信号扩展到动态网络中。
CRediT作者贡献声明
阿米尔侯赛因·法提纳维德（Amirhossein Fathinavid）：撰写 – 审稿与编辑、监督、调查、形式分析。阿米尔侯赛因·肖什塔里·塔瓦索利（Amirhossein Shoshtari Tavasoli）：撰写 – 原始草稿、软件、资源、调查、数据管理。
