论文部分内容阅读
摘要：对复杂网络中的社团结构进行划分与运筹学中的最优化理论之间有紧密联系。对复杂网络与社会结构的含义进行分析，同时对优化理论在解决复杂网络社团结构分析中的应用进行深入探讨与研究，主要分析运筹学在复杂网络社团结构中对经典模块划分方法的优化计算，说明运筹学对解决复杂网络社团结构的重要作用，对丰富复杂网络社团结构的划分算法提供一定参考与借鉴。
关键词：复杂网络；社团结构；运筹学；最优化理论；经典模块划分
一、复杂网络与社团结构基本概述
1、复杂网络定义
复杂网络主要指的是具有自组织、自相似、吸引子、无标度以及小世界等部分性质或者全部性质的网络。其主要特性主要有三个：其一，小世界性。复杂网络的基本构成十分简单，虽然其规模较大，但是每两个任意节点之间都存在一条较短的路径。并且复杂网络反应的相互关系数目较小，但可以连接世界。其二，集群性。社会网络中的人存在集团、群体概念，而复杂网络中同样具有集群性。这是网络集团化发展倾向的必然阶段，是网络的一种内聚倾向。每一个大型网络中都分布集聚性较强的小网络，并且小网络之间存在一定会的联系。例如，对一个朋友圈与另一个朋友圈的关系的相互关系进行反映。其三，幂律的度。度表示的有相互关系的顶点之间的联系性与紧密型，是网络中摸个顶点与其他顶点的数量。
除此之外，复杂网络还具有高度复杂性，主要体现在以下方面：第一，网络进化与改进。主要是网络节点的消失与不断产生会导致网络结构不断变化；第二，网络连接的多样性。每个网络节点在连接过程中都存在连接权重差异，这种差异会导致节点连接方式更加复杂，并且具有一定的方向性；最后，网络结构本身的复杂性。复杂网络的每一个节点都很简单，但是网络中存在的节点数量十分巨大，这就会导致网络呈现不同的结构与特征。这是复杂网络自诞生后就存在的主要特性。
2、社团结构的简单定义
网络中的社团结构并没有被广泛认可的定义。目前，常见的社团结构定义是以相对连接频数为基础进行定义的：可以将网络中的顶点进行分组，每个分组内部的顶点存在稠密连接与稀疏连接。但是这个定义中的“稠密”与“稀疏”并没有明确的标准。因此，一些研究人员提出了强社团与弱社团的定义：强社团的子图中每一个顶点与y内部的顶点连接度之和大于顶点与子图外部连接的度之和；而弱社团子图中顶点与子图内部顶点连接的度之和大于与子图外部顶点连接的度之和。此外，另外，还有一个较为严格的社团定义即LS集。这个定义表示由顶点组成的集合内部，任何真子集与该集合内部的连边数量都大于与该集合的外边连边数量。
二、利用优化理论对经典模块划分方法的优化改进与分析
1、经典模块结构优度方法概述
模块结构优度方法主要是给出每个划分的一个度量，以合理的划分方式确定较高度量。是由学者Newman与Girvan于2004年提出的。对这种度量进行优化时，可以获得最优化或者次优化的社团结构，两人将提出的度量定义为“Modularity”，中文翻译为“模块划分优度”。模块划分优度简称为模块度，利用公式进行定义时，将网络N划分为N1，N2，…，Nk，Ni=（Vi，Ei），这时，可以将模块优度定义为公式：
在这个定义中Ns中存在的边与总边数之间的比率与保持每块度数不变，但边连接方式随机的等价网络中Ns边和总边数的期望比率之差就是求和号中项的意义。而为了使模块Q的社团划分达到最大值，而得出最优化的社团结构，需要进行两步极大化问题分析，即：
这时会发现，这仅仅为一个里层问题，但是是一个难解问题。
而将整数变量0—1中的xij=1来代表网络中的点vi，属于社团j，不然xij=0。这时，里层的难题问题就可以转化为一个非线性的整数规划问题：
由此能够明显看出这是一个NP-hard问题，因此，最好使用启发式算法进行解决。
2、使用优化理论对模块优度方法进行改进分析
在对社团结构算法进行研究过程中，都比较注重对测试问题的计算，不能进行分析、定量地研究。而利用优化理论对算法的机制问题进行探讨时，主要是以运筹方法对复杂网络的重要属性与公开问题，根据最优化理论基础进行的逆向工程研究。更具体表述为：利用运筹学算法中的模型与技术将复杂网络社团结构中的重要属性与现象进行彻底研究，然后对其内在机制进行有效模拟，最终对这些重要属性与现象进行合理的、科学的阐述。
但是在研究过程中因为社团结构的复杂性过大，对网络结构畸形定量分析时，主要对常用的两个示范网络进行分析。示范网络图2（a），图2（b）。其中图2（a）表示的是由1bw条边将一个由L个m个顶点共有1in条边的稠密子图串起来的图。此图中1bw=1时，无论使用何种定义进行研究，每一个子图都是一个社团，图中不存在L=2P。而图2（b）表示的是两两之间共有1bw条边随机相连的L个有m个顶点、1in条边的稠密子块。
对以上公式的计算结果进行分析研究，得出关系式。如果这个关系式成立就会出现，这时，Q不能对每一个lump进行识别，将其划分为一个社团。在对示范网络进行优化计算时，还需要注意D函数中存在精度局限问题，L，lin，lbw都会对精度参数造成一定影响。并且在计算过程中，对Q与D的特性与优劣之处都进行了全面的分析，这也是最优化理论在模块优度方法中应用的重要意义。
除了使用最优化理论进行逆向工程分析外，还可以对目标函数D进行直接優化改进。这种优化思路主要是对优化Q中的约束最优化模型进行改进。就是对Q可能会出现的错分情况进行模拟考虑，并将社团定义等同于约束直接加入模型中，然后对模拟退火算法进行改进，得出带约束的Q或者D的最优解。这样可以确保得到的社团结构划分结果能够满足社团定义。
三、结语
经过对优化理论在复杂网络社团结构分析中的应用进行计算研究后，可以发现最优化理论可以对复杂网络社团结构的划分进行优化处理，但是需要注意是本文研究过程中涉及到的社团结构相对简单，社团之间不存在重叠性。而在对实际复杂网络社会结构进行划分时，社团的归属具有动态性，社会结构的复杂性与多样性会更多。这就需要相关研究人员根据最优化理论与社团结构之间的联系对社团结构划分进行适当优化与处理。希望广大研究人员敢于创新、勇于探索，促进优化理论对复杂网络社团结构问题中的应用。
参考文献：
[1]章祥荪. 运筹学在复杂网络社团结构分析中的应用[J]. 运筹与管理，2013（5）：1-11.
[2]贾松卫. 基于图论的复杂网络社团挖掘与结构分析[D]. 西安电子科技大学，2016.
[3]陈娟，吴开微. 工程管理中运筹学应用案例分析[J]. 科技展望，2016，26（31）.
[4]何广. 多智能体网络在运筹学图与网络分析教学中的应用[J]. 价值工程，2017，36（21）：238-239.
作者简介：
王文杰，男，山东菏泽人，讲师，主要从事图论与组合优化的研究。
关键词：复杂网络；社团结构；运筹学；最优化理论；经典模块划分
一、复杂网络与社团结构基本概述
1、复杂网络定义
复杂网络主要指的是具有自组织、自相似、吸引子、无标度以及小世界等部分性质或者全部性质的网络。其主要特性主要有三个：其一，小世界性。复杂网络的基本构成十分简单，虽然其规模较大，但是每两个任意节点之间都存在一条较短的路径。并且复杂网络反应的相互关系数目较小，但可以连接世界。其二，集群性。社会网络中的人存在集团、群体概念，而复杂网络中同样具有集群性。这是网络集团化发展倾向的必然阶段，是网络的一种内聚倾向。每一个大型网络中都分布集聚性较强的小网络，并且小网络之间存在一定会的联系。例如，对一个朋友圈与另一个朋友圈的关系的相互关系进行反映。其三，幂律的度。度表示的有相互关系的顶点之间的联系性与紧密型，是网络中摸个顶点与其他顶点的数量。
除此之外，复杂网络还具有高度复杂性，主要体现在以下方面：第一，网络进化与改进。主要是网络节点的消失与不断产生会导致网络结构不断变化；第二，网络连接的多样性。每个网络节点在连接过程中都存在连接权重差异，这种差异会导致节点连接方式更加复杂，并且具有一定的方向性；最后，网络结构本身的复杂性。复杂网络的每一个节点都很简单，但是网络中存在的节点数量十分巨大，这就会导致网络呈现不同的结构与特征。这是复杂网络自诞生后就存在的主要特性。
2、社团结构的简单定义
网络中的社团结构并没有被广泛认可的定义。目前，常见的社团结构定义是以相对连接频数为基础进行定义的：可以将网络中的顶点进行分组，每个分组内部的顶点存在稠密连接与稀疏连接。但是这个定义中的“稠密”与“稀疏”并没有明确的标准。因此，一些研究人员提出了强社团与弱社团的定义：强社团的子图中每一个顶点与y内部的顶点连接度之和大于顶点与子图外部连接的度之和；而弱社团子图中顶点与子图内部顶点连接的度之和大于与子图外部顶点连接的度之和。此外，另外，还有一个较为严格的社团定义即LS集。这个定义表示由顶点组成的集合内部，任何真子集与该集合内部的连边数量都大于与该集合的外边连边数量。
二、利用优化理论对经典模块划分方法的优化改进与分析
1、经典模块结构优度方法概述
模块结构优度方法主要是给出每个划分的一个度量，以合理的划分方式确定较高度量。是由学者Newman与Girvan于2004年提出的。对这种度量进行优化时，可以获得最优化或者次优化的社团结构，两人将提出的度量定义为“Modularity”，中文翻译为“模块划分优度”。模块划分优度简称为模块度，利用公式进行定义时，将网络N划分为N1，N2，…，Nk，Ni=（Vi，Ei），这时，可以将模块优度定义为公式：
在这个定义中Ns中存在的边与总边数之间的比率与保持每块度数不变，但边连接方式随机的等价网络中Ns边和总边数的期望比率之差就是求和号中项的意义。而为了使模块Q的社团划分达到最大值，而得出最优化的社团结构，需要进行两步极大化问题分析，即：
这时会发现，这仅仅为一个里层问题，但是是一个难解问题。
而将整数变量0—1中的xij=1来代表网络中的点vi，属于社团j，不然xij=0。这时，里层的难题问题就可以转化为一个非线性的整数规划问题：
由此能够明显看出这是一个NP-hard问题，因此，最好使用启发式算法进行解决。
2、使用优化理论对模块优度方法进行改进分析
在对社团结构算法进行研究过程中，都比较注重对测试问题的计算，不能进行分析、定量地研究。而利用优化理论对算法的机制问题进行探讨时，主要是以运筹方法对复杂网络的重要属性与公开问题，根据最优化理论基础进行的逆向工程研究。更具体表述为：利用运筹学算法中的模型与技术将复杂网络社团结构中的重要属性与现象进行彻底研究，然后对其内在机制进行有效模拟，最终对这些重要属性与现象进行合理的、科学的阐述。
但是在研究过程中因为社团结构的复杂性过大，对网络结构畸形定量分析时，主要对常用的两个示范网络进行分析。示范网络图2（a），图2（b）。其中图2（a）表示的是由1bw条边将一个由L个m个顶点共有1in条边的稠密子图串起来的图。此图中1bw=1时，无论使用何种定义进行研究，每一个子图都是一个社团，图中不存在L=2P。而图2（b）表示的是两两之间共有1bw条边随机相连的L个有m个顶点、1in条边的稠密子块。
对以上公式的计算结果进行分析研究，得出关系式。如果这个关系式成立就会出现，这时，Q不能对每一个lump进行识别，将其划分为一个社团。在对示范网络进行优化计算时，还需要注意D函数中存在精度局限问题，L，lin，lbw都会对精度参数造成一定影响。并且在计算过程中，对Q与D的特性与优劣之处都进行了全面的分析，这也是最优化理论在模块优度方法中应用的重要意义。
除了使用最优化理论进行逆向工程分析外，还可以对目标函数D进行直接優化改进。这种优化思路主要是对优化Q中的约束最优化模型进行改进。就是对Q可能会出现的错分情况进行模拟考虑，并将社团定义等同于约束直接加入模型中，然后对模拟退火算法进行改进，得出带约束的Q或者D的最优解。这样可以确保得到的社团结构划分结果能够满足社团定义。
三、结语
经过对优化理论在复杂网络社团结构分析中的应用进行计算研究后，可以发现最优化理论可以对复杂网络社团结构的划分进行优化处理，但是需要注意是本文研究过程中涉及到的社团结构相对简单，社团之间不存在重叠性。而在对实际复杂网络社会结构进行划分时，社团的归属具有动态性，社会结构的复杂性与多样性会更多。这就需要相关研究人员根据最优化理论与社团结构之间的联系对社团结构划分进行适当优化与处理。希望广大研究人员敢于创新、勇于探索，促进优化理论对复杂网络社团结构问题中的应用。
参考文献：
[1]章祥荪. 运筹学在复杂网络社团结构分析中的应用[J]. 运筹与管理，2013（5）：1-11.
[2]贾松卫. 基于图论的复杂网络社团挖掘与结构分析[D]. 西安电子科技大学，2016.
[3]陈娟，吴开微. 工程管理中运筹学应用案例分析[J]. 科技展望，2016，26（31）.
[4]何广. 多智能体网络在运筹学图与网络分析教学中的应用[J]. 价值工程，2017，36（21）：238-239.
作者简介：
王文杰，男，山东菏泽人，讲师，主要从事图论与组合优化的研究。