基于复杂网络理论的产品结构模块划分方法

杨格兰

（湖南城市学院计算机科学系，湖南 益阳 413000）

模块化设计是通过已有模块的选择和组合来实现产品的快速设计，正确合理地划分结构模块是产品模块化设计的前提和关键环节。目前的模块划分方法主要有两类：一类是功能分析法[1-4]，即根据产品的子功能及其相互间的关系来划分模块；另一类是零部件分析法[5-11]，即根据产品的零部件及其相互之间的依赖关系来划分模块。这两种模块划分方法都存在着明显的不足[11]：

1）过分依赖于产品的功能结构，离开功能结构的前提就无法实现模块划分；

2）仅仅适用于开发新产品的模块结构划分，不能对已有产品结构进行模块化分析、模块划分；

3）模块划分中需要构造大量的相关矩阵，计算量大，算法复杂，并且模块划分结果需要进一步优化。

产品结构的模块划分就是实现结构模块之间弱耦合，模块内各个零部件之间具有强耦合；而复杂网络的社团结构（Community Structure）就是社团内部的节点之间的连接相对非常紧密，各个社团之间的连接却相对来说比较稀疏[12]，从这个意义上来说，产品的结构模块就可以看成产品结构单元关联图（网络）的社团结构，从而借助社团结构发现方法来实现产品结构的模块划分。网络社团结构理论在物理学、社会学、生物学和图形学中都有广泛的应用，但是在产品模块化设计方面很少有研究，目前在中国期刊全文数据库中仅查到两篇相关文献。文献[13]将复杂网络理论应用于产品族结构建模中，提出产品族结构的零部件关系网络模型，零部件作为网络的节点，零部件之间的隶属关系作为网络的边，并在此基础上演化出产品族结构的模块关系网络模型。运用简单路径搜索等算法对各个节点的边介数、次数等参数进行计算和统计。通过分析和比较这些参数，确定基本模块、必选模块和可选模块，从而实现产品族的模块划分。文献[14]将复杂网络理论应用到产品变型设计领域，构建了产品尺寸约束关系网络，研究了网络统计参数意义及尺寸参数传递方法，在此基础上提出了基于尺寸参数传递方法的产品变型设计方法。

产品结构单元关联图实际上也是一种网络，零部件作为网络的节点，零部件之间的隶属关系作为网络的边，复杂网络中的相关理论和算法都可以应用到产品结构的模块划分中。鉴于模块划分与社团结构发现的相似之处，本文尝试将网络社团结构发现方法应用到产品的结构模块划分中，为产品结构模块划分提供一种新的思路。

1 基于复杂网络社团结构的产品结构模块划分

1.1 复杂网络及其社团结构

复杂网络是现实世界中复杂系统的一种抽象表现形式，现实世界中存在很多类型的复杂网络，比如互联网，社会关系网络等。Newman于2002年提出了复杂网络的社团结构概念[12]，随后的近几年来，复杂网络社团结构的研究受到了众多学者们的广泛关注和深入研究[15-19]。

目前，对于网络社团结构还没有统一的定义，一般来讲，网络社团结构是指网络中的顶点可以分成组（块），组（块）内顶点之间的连接比较稠密，组（块）间顶点的连接比较稀疏，如图1所示。

图1 网络社团结构示意图

1.2 网络社团结构的GN算法

Girvan 和Newman提出一个基于边介数的社团发现算法(GN算法)[20]。GN算法采用分割法，依据边不属于社团的程度逐步把不属于任何社团的边（即社团之间相连接的边）删除，用边介数衡量边在社团间连通中的重要程度和不属于任何社团的程度，社团之间的边比社团内部的边有更大的边介数，通过逐步移去这些边介数较高的边就能把它们连接的社团分割开来，从而达到社团划分的目的。

离心式压缩机的喘振系统工艺设计应该根据离心式压缩机的功率等自身特点，结合工艺要求的操作范围、操作介质的特性、管路系统的特点，综合考虑启动、正常工艺控制和紧急停车等不同工况，选择合理的喘振工艺控制系统，避免因喘振造成压缩机轴承、叶轮、机械密封等机械部件的损坏，造成不可挽回的经济损失。

GN算法发现社团结构的具体步骤如下：

1）找出给定网络的所有最短路径，然后计算每个边的边介值；

2）将具有最大边介值的边移除；

3）重新计算剩余边的边介值；

4）重复步骤(1)、(2)、(3)，直到划分出网络中的社团结构。

其中，最短路径为两个节点之间的最短连边的条数。在图1中，节点1与节点3直接相连，那么它们的距离是1，该种情况下节点1节点3的最短路径为1-3；节点1与节点5的最短路径为 1-3-5。边介数为通过该边的最短路径的总数量定义为边介数。以图1中的边（3-5）为例，通过该边的最短路径为 1-3-5、1-3-9、1-3-5-9、1-3-5-6、1-3-5-7、1-3-5-8，所以边（3-5）的边介数为6。

GN算法准确度比较高，分析社团结构的效果也优于其他的一些算法，特别适合中等规模的复杂网络，完全能满足机械产品结构关联图的网络规模，所以在模块划分中采用GN算法来实现产品结构的模块划分。

1.3 基于GN算法的产品结构模块划分

产品结构单元关联图上也是一种网络，产品的结构模块可以看作是关联网络的社团结构。所以，网络社团结构的发现算法可以应用到产品结构的模块划分中，基于GN算法的产品结构模块划分方法与步骤如下：

1）依据产品结构，找出组成产品的结构单元之间的关联关系，然后绘制出产品结构单元关联表。

2）结构单元作为网络的节点，结构单元之间的关联关系作为网络的边，构建产品结构网络图。

3）找出产品结构网络的所有最短路径，计算产品结构网络中所有边的边介值。

4）将具有最大边介值的边移除，计算模块度Q。

5）重复步骤3)、4)，划分出对应于不同Q值的一系列的社团结构。

6）依据产品结构，选模块度最大值或次大值所对应的社团结构为产品的结构模块。

其中，模块度 Q是表示社团特性强弱的参数。

上式中， ki,kj是节点的度值； Ci,Cj是i节点所属社团；m是网络总边数。当 Ci= Cj时，δ( Ci,Cj)= 1。Q值在0 ～1之间，一般以Q=0.3为网络具有明显社团结构的下限[20]。

某一产品结构单元之间的相互关联如表1所示，结构单元之间的关联用0、1表示，1表示有关联，0表示无关联。以产品结构单元为节点，有关联的结构单元之间的连线为边，构建产品结构单元的网络，如图2所示。

表1 产品结构单元关联表

图2 产品结构网络图

基于GN算法的模块划分的具体步骤及结果如表2所示。下面用3种不同颜色（圆点、方框、椭圆）表示不同的社团结构内部的节点。由图3可以看出，第1次移除最大边介值的边（1-8）后，该结构网络就被划分为两个社团结构，即产品结构被分为2个模块（6，7，8）与（1，2，3，4，5，9）。然后对第 2个模块在进一步划分，移除其最大边介值的边（1-2），但是，此时的结果没有完成对产品结构网络的社团发现，所以要继续在第2步的基础上，寻找剩下边中的最大边介值。在第3步中，移除最大边介值的边（5-9），最后产品结构网络被划分成3个社团结构，从而结构模块也是 3 个：（6，7，8）、（1，9）、（2，3，4，5）。

2 应用实例

文献[5]以汽车发动机为例，采用基于设计结构矩阵的模块化聚类，得到了发动机结构的主要模块。为了验证本文方法的可行性，在这里以文献[5]中的发动机结构模块划分为例，使用GN算法对其进行模块划分。由于冷却系统、润滑系统及电控系统3个结构单元的独立性，可以将其直接归为一个系统整合模块，所以在这里只考虑前20个结构单元的模块划分，其关联关系见表3。构建的结构单元网络图如图3所示，使用Ucinet[21]GN算法划分的发动机结构模块如图4所示，其中W表示模块数目，Q为社团模块度。

表2 基于GN算法的模块划分的具体步骤及其结果

图3 汽车发动机结构单 网络图（使用netdraw[22]绘制）

取模块度最大值（Q=0.237）的社团结构为汽车发动机结构模块划分的最终结果（见表4），此时，社团结构数目（W）为5，即发动机结构被划分为5个模块，分别为M1（1，3，5，6）、M2（2，4，9，10，17，18，19）、M3（11，13，14）、M4（12，15，16）、M5（7，8，20）。

从发动机结构模块划分结果对比（见表4）中，可以看出除了结构单元2、4、18以外，本文所用方法的模块划分结果与文献5的结果完全一致。从图4中可以看出，节点2、4、18是“骑墙节点”[23]，这3个节点同时被多个社团包含，属于多个社团的交叉部分,骑墙节点在一定程度上影响了结构模块的划分准确度。此外，发动机结构网络图的社团模块度最大值（Q=0.237）小于网络具有明显社团结构的下限（0.30），所以这在一定程度上也影响了模块划分的准确度。

表3 发动机结构单元关联表

3 结 束 语

本文将产品结构单元作为网络的节点，有关联的结构单元之间的连线作为网络的边，从而构建了产品结构单元网络，在此基础上，将GN算法用于产品结构单元的社团结构发现，从而实现产品结构模块的划分，文中的具体实例验证了该方法的可行性。需要说明的是，产品结构模块的划分是一项相当复杂的工作，任何一种方法都不可能完全准确的完成模块划分，本文所阐述的方法也不例外，基于GN算法的模块划分结果也只是一个辅助参考，对于复杂产品的模块划分，还需要工程人员在此基础上进一步的优化。

存在的问题和今后进一步研究的方向：

1）产品结构单元之间的关联仅仅考虑了两个极端情况（0-1），即节点要么有关联，要么没关联，没有全面考虑节点之间的其他关联程度，这点与工程实际不太相符，今后应研究使用赋有权值的网络社团划分方法实现结构模块的划分。

2）本文所用的方法是基于社团模块度指标Q的GN算法，该算法对产品结构模块划分的准确度受产品网络社团模块化的影响。对于具有明显社团结构的产品网络图（Q >0.3），该方法的划分准确度很高，否则其模块划分结果的准确度就受到影响。文献 19采用基于模糊树图方法对产品模块进行了有效的划分，但由于该产品网络图的模块度指标Q为0.059，说明该网络不具有明显的社团结构，所以采用本文中的方法得到的减速器模块划分结果很不理想。今后应尝试用其他的社团发现算法，如社团发现快速算法（Fast algorithm for detecting community structure）、边聚集算法（edge clustering coefficient）来研究复杂产品的模块划分，提高方法的实用性和准确性。

图4 使用GN算法得到的汽车发动机结构模块划分结果

表4 发动机结构模块划分结果对比

3）使用GN算法划分模块没有考虑所划分模块的实际意义，有强迫节点必须属于某一个社团的情况，所以划分模块的结果有局部错误，特别是对于一些边缘节点和骑墙节点。今后应进一步深入分析GN算法划分模块的适用范围，并考虑如果修正划分模块划分结果，从而提高基于社团结构发现算法的模块划分方法的准确性。

[1] 周开俊,李东波,童一飞.面向产品创新设计的功能模块划分方法[J].计算机辅助设计与图形学学报,2007,17(1): 73-77.

[2] 朱春燕,唐敦兵. 基于公理化设计的产品模块划分方法[J]. 机械科学与技术,2009,28(7): 926-930.

[3] Stone R B,Wood K L,Crawford R H. A heuristic method for identifying modules for product architecture [J]. Design Studies,2000,21(1): 5-31.

[4] Stone R B,Wood K L,Crawford R H. Using quantitative functional models to develop product architectures [J]. Design Studies,2000,21(3):239-260.

[5] Liu Yiliu,Ma Yongsheng,Stephen S G,et al. Product module partition and optimization for customization [J].International Journal of Advanced Manufacturing Systems,2007,11(10): 9-14.

[6] 陈 平,杨文玉. 复杂产品结构的模块化聚类及设计迭代量计算[J]. 中国机械工程,2007,18(1):1346-1349.

[7] 毛雨辉. 基于一种改进聚类算法的雷达导引头产品功能模块划分方法研究[J]. 中国机械工程,2010,21(3): 315-319.

[8] 吕利勇,乔立红,王田苗. 面向产品生命周期的产品模块化分解方法研究[J]. 计算机集成制造系统,2006,12(4): 743-748.

[9] 邓 可. 基于蚁群聚类算法的大规模定制产品模块划分研究[J]. 计算机工程与应用,2008,44(2):130-132.

[10] 王海军,孙宝元,王吉军,等. 面向大规模定制的产品模块化设计方法[J]. 计算机集成制造系统,2004,10(10): 1171-1176.

[11] 刘建刚,马 安,王宁生. 基于设计结构矩阵的产品结构模块聚类方法[J]. 华南理工大学学报,2006,34(1): 45-48.

[12] Newman M. Modularity and community structure in networks [J]. Proc Natl Acad Sci USA,2002,99:7821-7826.

[13] 樊蓓蓓,祁国宁. 基于复杂网络的产品族结构建模及模块分析方法[J]. 机械工程学报,2007,43(3):187-192.

[14] 邓小林,等. 基于复杂网络的产品变型设计方法[J].机械科学与技术,2009,28(4): 505-509.

[15] Sawardecker E N,Sales-pardo M,Amaral L N.Detection of node group membership in networks with group overlap [J]. Eur Phys J B,2009,67: 277.

[16] Gang Xu,Laura B,Lazaros G P,et al. Module detection complex networks using integer optimization [J/OL]. Algorithms for Molecular Biology,2010,5: 36 http://www.almob.org/content/5/1/36.

[17] 刘 婷,胡宝清. 基于聚类分析的复杂网络中的社团探测[J]. 复杂性网络与复杂性科学,2007,4(1):28-35.

[18] Fan Ying,Li Menghui,Zhang Peng,et al. Accuracy and precision of methods for community identification in weighted networks [J]. Physic A,2007,377: 363-372.

[19] Fortunato S. Community detection in graphs [J/OL].Eprint arXiv,2009,0906: 0612v1. [2009-04-20].http://www.arXiv.org.

[20] Yang B,Cheung W K,Liu J. Community mining from signed social networks [J]. IEEE Trans. on Knowledge and Data Engineering,2006,19(10):1333-1348.

[21] Borgatti S P,Everett M G. A graph-theoretic framework for classifying centrality measures [J].Social Networks,2006,28(4): 466-484.

[22] Borgatti S P. Centrality and network flow [J]. Social Networks,2005,27 (1): 55-71.

[23] 汪小帆,刘亚冰. 复杂网络中的社团结构算法研究[J]. 电子科技大学学报,2009,38(5): 538-543.