摘要: 1．本文的创新点自然世界与人类社会中的许多系统都可以表示成为复杂网络，比如人们所熟知的万维网（WWW）, 社会网络，公交网络，以及科学研究领域中的引文网等等。随着对网络性质的物理意义和数学特性的深入研究, 科学家们发现现实世界中的这些网络，尽管来自各种不同的领域，却有着一个极为相似的共性，即这些网络通常表现为整体上稀疏，但局部却非常密集。实际上, 整个网络是由若干个社团、社区（community）构成的。社团结构内部的节点之间连接非常紧密, 但是各个社团之间的连接却相对稀疏。实际网络中这些社团结构的存在往往映射出了其背后某些共同的特性，比如：万维网上的社区往往是一组具有类似主题的网页，社会网络中具有相似偏好的朋友经常聚在一起等等。因此，有效地发现并深入研究这些社团结构，对于理解网络的整体结构与功能特性有着十分重要的实际意义。在社区发现算法方面，Newman等人给出了社团结构的量化衡量标准，即：网络模块性（Network Modularity Q）,并首先提出了基于Q值优化的启发式算法GN以及基于层次聚类的快速算法Fast，然而，由于实际网络往往具有上百万规模数量的边和结点，因此，GN算法以及后来若干相类似的改进启发式算法通常很难胜任如此大的规模，而Fast算法虽然做了特别的性能优化，却不能取得令人十分满意的社区划分效果。因此，本文的主要创新点就是提出了能够适用于大规模真实复杂网络的社区发现算法ComTector，该算法的实际运行效率接近Fast算法，而社团划分效果则接近GN算法而远好于Fast算法，ComTector算法不需要事先预知可能的社团个数或是初始的划分情况，在实际应用中能够取得具有直观现实意义的网络社团划分结果。2．实现方法ComTector的基本思想是围绕互相紧密重叠的极大团（完备子图）来进行网络的社团划分。第一步，我们需要找到给定图的所有极大团；第二步，对于给定结点v, 我们将v所处的彼此紧密重叠的极大团的集合作为社团的候选“核心”进行过滤，当找到真正的“核心”后，我们围绕这些发现的社团“核心”进行聚类，将网络中余下的结点按照一定的距离标准归结到相应最近的“核心”，在该步骤结束以后，我们便得到了给定网络的初始社区划分；第三步，针对得到的初始社团划分，我们需要进行局部的Q值优化调整，从而将一些琐碎的社团进行合并，以获得社团划分的局部最优解。3．结论及未来待解决的问题我们在实际网络中对ComTector进行了测试，一方面，对于像“空手道俱乐部”，“2000年北美足球联盟”等社团结构事先已知的网络，ComTector给出的社团划分结果准确地与实际结构相匹配；另一方面，在“科研合作网”、“南佛罗里达词网”，“公共交通网络”，“北美电力网”，以及“移动电信呼叫网络”等大规模结构未知的网络中，ComTector给出了具有直观意义的划分结果，比如，在“南佛罗里达词网”中，每一个发现的社区都是一组概念上彼此紧密相关的词汇，而在“移动电信呼叫网络”，处于同一个社区的人们往往具有相类似的消费能力、年龄或者相同的邮政编码。在进一步的工作中，我们会结合结点的自然属性以及网络拓扑随时间的演变特性来描述在连续的时间快照内得到的各种社区的演化特征及其相应的物理意义。与此同时，由于社团结构的存在往往代表了其背后的某些共性，因此，我们也会将算法扩展到结点类型“异质”的网络中，比如：2分图，希望利用社区的结构特性以对现有基于协同过滤的推荐算法进行改进。4．实用价值或应用前景ComTector能够在大规模网络中给出特定的社团结构划分，那么可以把每个社团当作“点”，社团之间的联系当作“边”，从而对原始网络进行压缩，以便能够在信息可视化中进行展示，以帮助人们对网络的整体拓扑及其骨干有一个清晰直观的认识。此外，我们可以针对社区内部各个结点进行“角色”细分，通过找出社区内最有影响力的“核心”人物，或者社区间起到连接作用的“桥梁”人物，有针对地进行广告推荐，以相对较小的资源开销使得信息得到充分的传播。在“移动电信呼叫网络”，运营商可以针对各个社区的公共背景，有选择地调整产品套餐的配置，或提出更经济适用的套餐，以便获得更大的市场空间从而提高企业的核心竞争力。