基于复杂网络社区检测算法的元器件选用推荐方法

0引言

随着航天技术的快速发展,宇航元器件的可靠性和性能要求日益提高,元器件的可靠性对航天器的性能影响很大。传统的元器件选用方法主要依赖于专家经验和单一性能指标评估 ,这些方法在满足复杂、动态的航天任务需求方面常显力不从心^[1] 。许多复杂系统具有相互作用的特征,可以借助图论将这些复杂系统抽象为网络。复杂网络中的社区结构是一个很重要的特性,一般认为社区是网络中一组点的集合 ,社区 内部的节点联系 比较紧密 ,社区之间的节点联系比较稀疏^[2] ,找出复杂网络中社区结构的任务被称作社区检测,这对于揭示网络的功能和结构特性非常重要。复杂网络理论作为一种新兴的分析工具,近年来在多个领域得到了广泛应用,为复杂的元器件选用提供了新的方法和思路。

复杂网络通过节点和边的方式描述系统 中元素及其相互关系,能够有效揭示系统的结构特征和动态属性。社区检测算法作为复杂网络分析中的一个重要方向,旨在发现网络中的节点群体 ,这些群体 内部的节点联系较多 ,而与群体外的节点联系相对较少。在元器件选用推荐时,所依据的大多是元器件的历史选用数据。历史上的每一次选用 ,都在这些元器件之间建立起了联系 ,被联系起来的元器件可比拟为复杂网络中的节点,这些历史选用数据可作为复杂网络中的边。因此可以将元器件及其历史选用数据抽象为一个复杂网络。在元器件的选用过程中,某些元器件经常会被同时选中,这代表着这些元器件之间有着更加紧密的联系,这些联系紧密的元器件也就构成了复杂网络中的社区结构。当用户选择了一些元器件时,与这些元器件在同一社区的其他元器件便有很大的可能被选用。如果向用户推荐与已选的元器件在同一社区的其他元器件,便可提高元器件选用的效率。

国际上,复杂网络和社区检测算法已经被应用于多个领域 ,如社交网络分析、生物 网络研究、通信 网络优化等。在国内,复杂网络理论和社区检测算法的研究也取得了一定的进展。许多学者将复杂网络应用于交通网络优化、能源网络分析等方面 ,取得了显著的成果。然而 ,将复杂网络社区检测算法应用于宇航元器件选用的研究尚不多见,这为本研究提供了一个新的切入点。

将复杂网络社区检测算法应用于宇航元器件选用具有重要的理论和实际意义。复杂 网络社区检测算法能够综合考虑元器件的多维性能指标和相互关系,从而提供更全面的分析结果。宇航领域的元器件通常需要满足多个性能指标 ,如 电气性能、温度特性、尺寸重量、可靠性等。复杂网络社区检测算法可以综合考虑这些多维性能指标,并通过发现元器件之间的 内在关联性进而提取出具有相似性能和特点的元器件群组,从而为选用提供更全面的分析结果。复杂网络社区检测算法能够挖掘元器件之间的潜在关联和内在结构,以此发现元器件之间的功能模块和组织结构。这有助于在选用过程 中更好地理解元器件之间的相互作用,提高系统的整体性能和可靠性。通过应用复杂网络社区检测算法,可以将元器件划分为具有相似性能特点的元器件群组,使得在选用过程中可以优先考虑同一元器件群组内的元器件。这种优化选用决策的方法能够提高系统的一致性和可靠性,减少选用过程中的试错和盲目选择,从而提高选用的准确性和效率。将复杂网络社区检测算法应用于宇航元器件选用可以提供更全面的分析结果,优化选用决策,提高系统的一致性和可靠性,从而推动宇航领域的技术发展和进步。这种方法不仅具有重要的理论意义 ,更有广泛的实际应用价值 ,为宇航领域的元器件选用提供了新的思路和方法。

1元器件选用网络与社区检测

1. 1元器件选用网络的图表示

元器件的历史选用数据可构建为一个复杂网络,即元器件选用网络。元器件选用网络可抽象为图 ,用 G表示。元器件即图 G 中的节点 ,节点的集合用V表示。元器件之间的联系视作边 ,边的集合用E 表 示 ,即 E =[(u,v)|(u,v)∈V²],一个元器件选用网络可以表示为一个图G(V,E)。若图的边有权值,则称其为加权图,否则为非加权图。加权图可表示为 Gw=(V,E,w) ,其中 w表示权值。若图的边有方向,称之为有向图,否则为无向图。由元器件历史选用数据得来的图为无向的加权图。

1.2 元器件选用网络中的社区结构

定义网络中的社区集合为 C,Ci即网络中的第i个社区。社区应满足式(1)的要求^[2] :

一个社区即一组联系紧密的元器件,这些元器件在历史上被同时选用 ,今后极有可能被 同时选 中 ,因此可以 向用户推荐在同一个社区 中的元器件。如果一个节点可以属于多个社区 ,则称其为重叠社区 ,即一个元器件可以属于多个群组。本文只讨论非重叠社区,并且每个节点都必须有其对应的社区,即每个元器件都必须有自己对应的群组。将网络划分为子图的非重叠社区的集合称为社区划分,社区划分用 P表示,即 :

P={C1 ,C2 ,…,Ck} i≠j |i,j ∈ {1,2,…,k} (2)

需要注意的是,在现实世界中一些网络的社区划分是已知的,然而很多网络的社区划分是未知的。

1.3社区检测的评价指标

为了评价不同社区划分的优劣,需要一些对社区检测结果的评价指标。常用的评价指标有模块度和标准化互信息。

模块度(modularity)又称Q值 ,是一种基于网络社区划分边的非随机性来评估网络的给定社区划分的度量^[3]。

模块度的定义如下 :

式中,m 为图的边数,i和j表示节点编号,A 为邻接矩阵 ,d为每个节点的度数。若节点i和节点 j在同一个社区,则δ (Ci,Cj)=1;否则,δ(Ci,Cj)=0。

通常,具有较高模块度值的社区划分代表了给定网络良好的社区结构。一个社区划分表示一个较强的社区结构 ,则其模块度会很高 ,此时社区 内的元器件有极大的概率被同时选用。反之,若社区内边的比例与零模型间没有差异,则其模块度会很低,此时社区内的元器件关联不强。从拓扑结构的角度来看,模块度接近于1表示网络划分较好,即模块度越大的社区划分表示社区结构越强。

标准化互信息(Normalized Mutual Information,NMI) ,是一种比较两种社区划分之间相似度的指标。通常比较现有划分和真实划分,真实划分可采用实际型号或单机的元器件BOM,对其进行处理 即可得到真实划分。 NMI越高,则表示该划分与真实划分越接近^[4]。

记真实划分C^= {C^1,C^2,C^3,…,C^k} ,现有划分 P={P₁,P₂,P₃,…,P_l} 。标准化互信息定义为:

式中,H(P)表示社区划分 P 的交叉熵,I(C^,P)表示C^和 P 的互信息。通常NMI值越高 ,表示两个社区划分之间的相似度越大 ,即社 区 中 的元器件与现实 的元器件 BOM 越接近。若求出的社区划分与真实社区划分完全一致 ,则NMI取其最大值为1。反之 ,若求出的社区完全独立于真实社区,则 NMI取其最小值为 0。

现实中大多数网络并无真实社区划分,对于元器件选用网络,设定其真实划分也需要耗费时间与精力。对这些网络便不能求取 NMI值,这也是 NMI作为评价指标的一个缺陷。对具有真实社区划分的网络,从匹配真实社区划分的角度出发,NMI接近于 1表示该划分非常优秀,即 NMI 值越大的划分表示该划分与真实社区划分间的相似度越大,此时构建的元器件群组接近于真实的型号与单机。

2 复杂网络社区检测用于宇航元器件选用

2. 1构建元器件选用网络

将复杂网络社区检测方法用于宇航元器件选用推荐,首先需要准备元器件的历史选用数据并用其构建元器件选用网络。元器件及其历史选用数据可以抽象为加权的无向图 ,一个元器件即为图的一个节点 ,若两个元器件被同时选用一次 ,则这两个节点间 的权值加1,将所有历史选用数据叠加即可得到最终的图 G。

2.2社区检测算法的选择与应用

构建好元器件选用网络后,选择合适的社区检测算法求取社区划分。社区检测算法大体可分为两类 :基于结构的社区检测、基于结构和内容的社区检测。社区检测的研究主要集中于网络的拓扑信息,常用的社区检测算法包括模块度优化算法、谱聚类算法、标签传播算法和新兴 的智能算法等^[5]。

随着模块度在社区检测中的广泛应用,研究人员将注意力转 向 了进化算法(Evolutionary Algorithm,EA) 。进化算法能在较短时间内解决一些极复杂的搜索问题,虽不能保证得到全局最优解,但能在短时间内求出近似最优解的能力使其得到了广泛的应用^[6]。

选择合适的算法后 ,对元器件选用 网络进行社 区检测 ,识别出网络中的社区结构。在元器件选用网络 中 ,社区表示一组紧密连接的元器件,这些元器件在性能参数与协同工作上表现出高度的关联性。通过社区检测可以发现哪些元器件在系统中具有更强的协同作用,从而为元器件的选用推荐提供依据。

2.3元器件选用推荐

社区检测完成后 ,基于社 区结构进行元器件选用推 荐 。元器件选用推荐的 目标是根据系统需求和已有元器件的性能参数推荐合适的元器件,以优化系统性能^[7] 。在复杂网络中,推荐系统可利用节点的社区结构和特征相似性进行推荐。通过社区检测识别出的社区具有高度 内部关联性,这意味着社区内的元器件在性能参数和协同工作上具有相似性和互补性。因此,当需要为某一型号或单机以及分系统选择元器件时 ,优先考虑 同一社 区 内的元器件,因为这些元器件更有可能在实际应用中表现出更好的协同效果和兼容性。此外,元器件推荐还可以利用基于相似度的推荐算法,通过计算目标元器件与候选元器件之间的相似度 ,并根据相似度得分进行排序 ,推荐得分最高的元器件。

3用进化算法对元器件选用网络进行社区检测

进化算法是一种启发式算法,通过模拟生物进化作为一种问题解决策略。给定一个待解决的问题,算法的输入为解的随机总体。每个可能的解被称为个体,这些个体以某种方式进行编码 ,评价个体的指标被称为适应度函数。此外 ,为了更新种群中的个体 ,在算法的每一步都使用了一些遗传算子 ,如交叉算子、变异算子等^[8] 。本文设计 了一种改进的进化算法用于社区检测,并在两个元器件选用网络上进行了实验,适应度函数采用模块度。

3. 1算法介绍

大多数基于进化算法的社区检测方法使用基于轨迹 的编码或基于解 向量 的编码 ,这些编码方法存在一些缺 陷,例如会产生无效社区和重复表示。本文引入了一种新的编码方法,称为基于节点相似度的最大生成树的编码方法 ,这种方法基于元器件选用树进行编码 ,既克服现有编码方法的缺陷,又从基于不同相似度的方法中获益。与其他编码方法相比,基于节点相似度的最大生成树的编码可以通过消除无效的社区划分将搜索过程导 向更优秀的社区划分来缩小搜索空间。另外,该编码方法移除了一些无效的编码,减小了可能的染色体总数,缩小了搜索空间,提高了算法的效率。

加速遗传算法收敛时间的方法之一是从非随机种群开始该过程。为了进一步提高算法的收敛时间,本文提出了一种新的初始种群生成函数。新的初始种群生成函数利用一种简单但有效的阈值切割方法将网络划分为一些初始社区,从而得到联系更紧密的初始元器件群组。本文还基于模块度的可加性质,提出了模块分度的概念。不仅降低了计算的复杂度,还以此引入了基于模块分度的父代导入子代的交叉算子。

最后 ,引入了一种新的 自适应变异函数 ,称为基于正弦的变异函数。基于正弦的变异函数基于 自适应控制参数和边到社区边界 的距离来创建变异概率 的分布 函数。随着最优个体适应度的提高,控制参数使变异概率的分布函数发生平滑的变化,使得适应度较高的个体更容易发生变异。算法的整体流程如图1所示。

3.2 编码

树是一种特殊 的 图 ,连通 的无 回路 的无 向图被称为树。树有一个重要特性 ,树的边数等于其节点数减1。若无向图 G 的生成子图 T 是树 ,则 T 是G的生成树,生成树包含原图的所有节点和边的一个子集,可以从元器件选用网络得到元器件选用树。若 图 G 是加权 图 ,其所有 的生成树中 ,所有权值之和最小的生成树称为最小生成树 ,所有权值之和最大的生成树称为最大生成树,一个图的最小生成树和最大生成树都不唯一。若图 G有 n个节点 ,则其生成树 T也有n个节点,且 T必有(n-1)条边。在生成树 T 中,每去掉一条边就可以将 T分成两个树,将被去掉的边称为断边。可以利用这一特性 ,对于图 G,去掉其生成树的一条边 ,就可以将图 G分成两个社区 ,从而将所有元器件分成两个群组。

首先,求取元器件选用网络的最大生成树。现有求取最大生成树的算法不多,将元器件选用网络的权值取其相反数 ,套用求取最小生成树的算法即可求得最大生成树 ,此最大生成树即元器件选用树。本文采用经典的 Prim算 法[9]求取元器件选用树。编码时 ,染色体为一个长度为 (n-1)的数组 ,每个节点代表元器件选用树 的一条边。数组的值只取 0和1,若值取0,则该边得到保留 ,若取1,则该边被去除。即每条染色体对应一个社区划分,若染色体全取0,则元器件选用树 的所有边都得到保 留 ,即将原图的所有节点划为一个社区,此时所有元器件都在一个群组内;若染色体全取1,元器件选用树的所有边都被去除 ,则原图的每个节点都是一个社 区 ,原 图被划分为n个社区 ,此时每个元器件独 自为一个群组。

如图 2所示,该元器件选用树有10个节点和9条边,该染色体去掉了节点1和节点 3之间的边,同时又去掉了节点 3和节点 5之间的边。去掉两条边之后,所有的元器件被分成 3个群组。

3.3种群初始化

大多数进化算法都采用随机初始化的方法,但合理的初始化方法能加快算法的收敛时间。一般认为社区的大小随网络规模的增大而增大 ,社区的节点数约为 √n,n为网络的节点数 ,在操作中 √ n若为小数 ,则 向上取整 ,本文的种群初始化方法即基于上述假设^[8]。

对于已经求得的元器件选用树,首先定义一个被访问的标志。随机从一条边开始 ,如果这条边 的两个节点 尚未被访问 ,则将这两个节点加入一个社区 ,并且标记其为已被访问 ,然后搜索与这两个节点相连的其他节点 ,同时计算已被加入社区的节点数,当社区节点数达到时结束搜索。若在搜索过程中遇到断边(即向前的节点已属其他社区) ,则停止这个方向的搜索,若所有方向都是断边且当前社区的节点数不够√n,则修复一条断边,将现有节点数不足的小社区并入一个节点数够√n的社区,产生一个大社区。

搜索结束后生成一个初始社区,即社区内部节点之间的边取 0,得到保留,与社区内部节点相连但并未被划入社区的边取 1,成为断边。一直进行下去,直到所有节点都被访问,此时 n个点都有了对应的社区,生成树的(n-1)条边都有了对应的染色体值,种群初始化完成。生成的初始社区划分 ,每个社区都至少有 √ n个节点。图3为一个种群初始化的示例。

3.4选择算子

在进化算法 中 ,选择 的目 的是保 留适应度较高 的个体,去除适应度较低的个体。选择是要对每个个体的适应度进行评估,本算法适应度函数采用模块度。模块度的一个重要性质是其具有可加性。对于一个社区划分 P,其模块度可以写成若干个基本函数之和,即 :

(5)

将 q称为模块分度,q(C)即社区 C的模块分度。

具体的有:

(6)

式 中 ,m 为边的总数 ,C表示一个社区 ,lC表示与社区 C 内的节点相连的边数 ,d_C表示社区 C 内所有节点的度数之和。

利用模块度的这一特性可以减少一些不必要的计算。为每个个体创建一个模块分度列表,列表的长度等于其社区的数量 ,列表中包含每个社区各 自的模块分度。因此 ,在发生交叉或变异的情况下,只需重新计算发生改变的社区的模块分度,再相加就可求出新个体的模块度。

在求取每个个体的适应度后,采用轮盘赌的方法选择个体。个体a保留下来的概率等于其适应度与所有个体适应度之和的比值,即 :

(7)

式中,Ω为所有个体长成的空间。计算每个个体被保留的概率后 ,即可得到每个个体 a 的累计概率p^_a。p^_a  的计算公式如下 :

(8)

然后 ,随机在 0到1之间选取一个数 r,观察 r的值,如果 p^_k-1≤r<p^_k,那么个体 k被保留。

3.5 交叉算子

交叉是为了从父代产生更加优秀的子代,每次随机从所有个体中选取一对作为父代。在选择算子 中已经为每个个体定义了一个包含其各个社 区 的模块分度 的列表。首先,根据两个父代各自的模块分度列表对两个父代的各个社区的模块分度从高到低进行排序。从高到低开始,先把模块分度最高的社区导入子代,然后将模块分度次高的社区导入子代。对于后导入的社区,若其某些节点已属其他社区 ,则去掉这些节点 ,因此导入的这个社区可能会被破坏。由高到低依次导入两个父代的社区,直到所有的节点都有归属,此时所有的元器件都被归入确定的群组,交叉结束。

3.6变异算子

现有的进化算法在变异时,大多采用等概率的随机变异。本文引入了一种基于每个基 因所对应边的深度 自适应变异函数。

本算法采用基于最大生成树的编码,染色体的每个节点表示元器件选用树的一条边 ,染色体的节点取值只有0和1两种情况。在变异时 ,按照概率选取一个节点 ,对选中的节点进行变异。因所用的编码值只有1和0,将选到的节点反转即可完成变异。对于一个社区,可将其边分成两类 ,一种是社区内部的边 ,一种是社区边界的边。可以认为 ,如果社区内部的边发生变异 ,此时保持社区边界的边保持不变是合理的,反之亦然。这种方法分配了每个基因与其群落断边的相应距离的概率,它对社区边界上的边赋予了更多的权重。

为了生成这样的分布 ,首先创建一个长度为 (n-1)的向量w→,并将相应 的断边元素赋值为1。对于每条断边,开始以 BFS的顺序^[10]访问与其相连的边,直到遇到另一条断边。对于每条被访问的边 ,更新其对应的w→,更新公式为:

式中,i表示生成树的第几条边,d 为该边与边界边的距离,α 为控制的参数。若α=0,则生成的概率分布会给边界边较大的变异概率;若α=1,则会给内部边较大的变异概率;若α=0.5,则所有边变异概率相等。α 是一个自适应参数,它根据每一代最佳个体适应度的变化在0到1之间变化。如果最佳个体的适应度较上一代有所提高,那么α 保持不变,否则改变α。具体如下:

式中 ,δ为一个 自定义的参数 ,表示每一步 的长度 ,q表示进化过程的第几代。在使用个体的所有断边执行完上述的过程后 ,对w→向量的值在0到1之间进行变换 ,并用它作为变异概率的分布函数。通过这种自适应方法可以造成更有效的变异,基于种群池中最佳个体质量的提高,调整突变概率函数的参数,从而可以更好地分离或合并社区。

3.7 实验结果及分析

基于元器件的历史选用数据,生成了两个元器件选用网络 ,称之为网络一和网络二。网络一有34个节点和78条边,网络二有62个节点和 318条边,并且人工对这两个网络做出了参考划分 ,从而可以用NMI对求得的划分进行评价。算法在运行 时 的参 数 ,种 群 规模 统一设置 为100,最大代数为100,每个数据集运行25次 ,变异函数中的 δ设置为 0. 1。实验结果如表1所列。

可以看出 ,网络一和 网络二求 出的社区划分 的 Q值均较高,本算法有效检测出了两个元器件选用网络中的社区结构。网络一社区划分的NMI值为0.60,网络二社区划分的NMI值更是达到了 0.73,检测出的社区划分与人工做出的参考划分有较高的相似性。实验结果表明,本文设计的社区检测算法实现了元器件的智能选用推荐。

4结语

复杂网络社区检测方法能够综合考虑元器件的多维性能指标和相互关系 ,提供更全面的分析结果 ,减少对专家经验的依赖 ,通过算法 自动识别优选元器件 ,提升选用效率,并且复杂网络社区检测方法适用于多种类型的元器件和不同的应用场景。在系统设计中,常常需要比较和选用不同类型的元器件,复杂网络社区检测方法可以帮助将这些不同类型的元器件划分为具有相似性能特点的社区,从而更好地进行比较和选用。复杂 网络社区检测方法可以根据具体的应用场景发现元器件之间的相互关系和 内在结构 ,从而帮助优化元器件的选用 ,使其更好地适应特定的应用环境。

随着技术的发展 ,新型元器件不断涌现 ,旧有元器件可能需要被替换。复杂网络社区检测方法可以帮助分析新元器件与现有元器件的相似性和替代性,指导新元器件的引入和旧元器件 的替换过程。复杂 网络社区检测方法能够从数据驱动的角度出发,基于元器件之间的性能参数 和相互关系 ,提供客观、系统化的选用决策支持。这种方 法有助 于 降低 主 观偏见 ,提 高选用决策 的科 学性 和准确性。

但是复杂网络分析依赖于高质量的数据,数据不完整或不准确都会影响结果。社区检测算法在大规模网络上的计算复杂度较高,可能需要高性能计算资源。今后不断改进数据收集和处理方法 ,以及优化社区检测算法 ,复杂网络社区检测方法在宇航元器件选用 中的应用前景将更加广阔。

参考文献

[1]张磊,魏世隆,李强,等. 基于应用等级的航天元器件选用和保证技术[J].电子产品可靠性与环境试验,2015,33(6) :38 42.

[2]张玮桐. 基于标签传播和社区融合的复杂网络社区检测[D].西安 :西安电子科技大学,2017.

[3]SCHUURMAN T,BRUNER E.Modularityandcommunitydetection inhumanbrainmorphology[J]. TheAnatomical Record,2024,307(2) :345 355.

[4]MAHMOUDIA,JEMIELNIAK D. ProofofbiasedbehaviorofNormalizedMutual Information[J].Scientific Reports,2024,14(1) :9021.

[5]GASPARETTIF,SANSONETTIG,MICARELLIA. Com- munitydetectioninsocialrecommendersystems.asurvey [J]. AppliedIntelligence,2020,51(6) :3975 3995.

[6] 白靖. 基于进化算法的复杂网络社区检测[D].西安 :西安电子科技大学 ,2013.

[7]沈士英,贾儒悦. 航天型号元器件选用策略[J].电子与封装,2019,19(9) :37 42.

[8] HESAMIPOURS,BALAFARMA,MOUSAZADEHS.DetectingCommunities in Complex Networks using an A-daptiveGeneticAlgorithm andnodesimilaritybasedenco- ding[J]. Complexity,2023(1) :4796536.

[9]KAYB,DATEP,SCHUMANC.Neuromorphic graph algo-rithms:Extracting longest shortest paths and minimum spanning trees[C]//Proceedings of the 2020 Annual Neuro inspired Computational Elements Workshop,2020:1 6.
[10]SCHEFFLERR.On the recognition of search trees genera-ted by BFS and DFS[J].Theoretical Computer Science,2022,936:116 128.

2025年第1期第7篇