运筹学在复杂网络社团结构分析中的应用

《运筹学在复杂网络社团结构分析中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第２２卷第５期运筹与管理Ｖｏｌ．２２，Ｎｏ．５２０１３年１０月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥＯｃｔ．２０１３运筹学在复杂网络社团结构分析中的应用章祥荪（中国科学院数学与系统科学研究院，北京１００１９０）摘要：社团结构研究是复杂网络这一前沿领域中的重要问题，同运筹学有着密切的关联。本文介绍了传统社团结构问题的基本定义，以及最近十年通过应用运筹学理论对该问题的研究进展。这些进展包括启发式模型，到随后的概率优化模型，以及组合优化模型。通过这些介绍，说明了运筹学方法论和基本工具在复杂系统研究中所起到的重要作用。关键词：复杂网络；社团结构；运筹学；

2、启发式模型；概率优化模型；组合优化模型中图分类号：Ｏ２２１文章标识码：Ａ文章编号：１００７-３２２１（２０１３）０５-０００１-１１OperationsResearchMethodologyinCommunityStructureAnalysisofComplexNetworksＺＨＡＮＧＸｉａｎｇ-ｓｕｎ（AcademyofMathematicsandSystemsScience，CAS．Beijing１００１９０，China）Abstract：ＣｏｍｍｕｎｉｔｙＳｔｒｕｃｔｕｒｅＡｎａｌｙｓｉｓｉｓｏｎｅｏｆｔｈｅｐｏｐｕｌａｒｒｅｓｅａｒｃｈｐｒｏｂｌｅｍｓｉｎｔｈｅｃｏｍｐｌ

3、ｅｘｎｅｔｗｏｒｋｓｔｕｄｙ，ｗｈｉｃｈｈａｓｃｌｏｓｅｄｒｅｌａｔｉｏｎｓｈｉｐｗｉｔｈＯｐｅｒａｔｉｏｎＲｅｓｅａｒｃｈｔｈｅｏｒｙａｎｄａｌｇｏｒｉｔｈｍ．Ｔｈｉｓｐａｐｅｒｉｎｔｒｏｄｕｃｅｓｔｈｅｂａｓｉｃｄｅｆｉ-ｎｉｔｉｏｎｏｆｔｈｅｃｏｍｍｕｎｉｔｙｓｔｕｃｔｕｒｅｐｒｏｂｌｅｍａｎｄｓｕｒｖｅｙｓｔｈｅｄｅｖｅｌｏｐｍｅｎｔｏｆｍｅｔｈｏｄｓｆｉｎｄｉｎｇｔｈｅｃｏｍｍｕｎｉｔｙｓｔｒｕｃｔｕｒｅｉｎｒｅｃｅｎｔｔｅｎｙｅａｒｓ，ｅｓｐｅｃｉａｌｌｙｔｈｏｓｅｕｓｉｎｇＯＲｍｅｔｈｏｄｏｌｏｇｙｓｕｃｈａｓｈｅｕｒｉｓｔｉｃｍｏｄｅｌｓ，ｓｔｏｃｈａｓｔｉｃｏｐｔｉ

4、ｍｉｚａｔｉｏｎｍｏｄｅｌｓａｎｄｃｏｍｂｉｎａｔｏｒｉｃｍｏｄｅｌｓ．Ｆｒｏｍｔｈｅｓｕｒｖｅｙ，ｏｎｅｃａｎｓｅｅｔｈａｔＯＲｍｅｔｈｏｄｏｌｇｙｔａｋｅｓｖｅｒｙｉｍｐｏｒｔａｎｔｒｏｌｅｓｉｎｔｈｅｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓｔｕｄｙ．Keywords：ｃｏｍｐｌｅｘｎｅｔｗｏｒｋ；ｃｏｍｍｕｎｉｔｙｓｔｒｕｃｔｕｒｅ；ＯｐｅｒａｔｉｏｎＲｅｓｅａｒｃｈ；ｈｅｕｒｉｓｔｉｃｍｏｄｅｌ；ｓｔｏｃｈａｓｔｉｃｏｐｔｉｍｉｚａ-ｔｉｏｎｍｏｄｅｌ；ｃｏｍｂｉｎａｔｏｒｉｃｍｏｄｅｌ０引言复杂网络具有非简单拓扑结构特征，它的这些特征既不在简单的格点网络中出现，也不在随机网络中出现，

5、但却在现实世界的网络中出现。这一研究的里程碑式起点是上世纪末的两篇重要文章：１９９８年［４３］Ｗａｔｔｓ和Ｓｔｒｏｇａｔｚ发表在Ｎａｔｕｒｅ上的对小世界网络模型的研究，以及１９９９年Ｂａｒａｂａｓｉ和Ａｌｂｅｒｔ在［４］Ｓｃｉｅｎｃｅ上关于无尺度网络模型的研究。Ｂａｒａｂａｓｉ最近在枟ＮａｔｕｒｅＰｈｙｓｉｃｓ枠上发表了一篇题为“网络论的兴起（ＴｈｅＮｅｔｗｏｒｋＴａｋｅｏｖｅｒ）”的文［５］章，文章的主要论点如下：（１）复杂性理论在几十年的研究中没有得到有效的进展。（２）从以爆炸速度增加的数据财富中得益最多的领域是网络理论，它本质性地重塑了我们对复杂性的研究。（３）各具体复杂网络在

6、节点的属性和节点之间的连接上有很大差别，但大部分网络却由一系列基本收稿日期：２０１３-０６-０８基金项目：国家自然科学基金资助项目（１１１３１００９）作者简介：章祥荪，男，国际运筹学会副主席，亚太地区运筹学联合会主席，中国运筹学会名誉理事长。２运筹与管理２０１３年第２２卷的规则支配着，确定和限制着它们的行为。（４）网络科学远比物理学大，而物理学深深卷入其中。要像前辈物理学家在上个世纪开创了量子力学一样，投入网络理论的研究，直到它的完成。这一研究确实是物理学家走在前面，但随后也引起了数学界和运筹学界的反响。经美国ＩＮＦＯＲＭＳ前主席ＲｉｃｈａｒｄＬａｒｓｏｎ的推荐，在２００８年的枟Ｏｐ

7、ｅｒａｔｉｏｎｓＲｅｓｅａｒｃｈ枠上发表了一篇题为“抓住‘网络科学’的［３］要害问题：运筹学家的视野和机遇”的论文。论文的主要论点为：（１）概要地介绍网络理论的起源、方法论以及重要的成果。（２）对传统以图理论为基础进行的网络研究同工程师、决策者需要的网络理论进行比较。（３）建议以运筹学方法对复杂网络的重要属性和公开问题进行‘基于最优化理论的逆向工程’（ｏｐｔｉｍｉｚａｔｉｏｎ-ｂａｓｅｄｒｅｖｅｒｓｅｅｎｇｉｎｅｅｒｉｎｇ）。复杂网络的特性，或者说不同于格