张 昕,楚善增,姚友娟,张 瑜,李晓光

(辽宁大学 信息学院,沈阳 110036) E-mail:xgli@lnu.edu.cn

1 引 言

现实世界中的许多系统都是以复杂网络的方式呈现,如电力网络、交通网络、社会网络以及互联网等,它们不仅具有小世界与无标度等结构复杂性,还表现出动态演化、连接多样性以及节点多样性等诸多复杂性质.社团结构[1]是复杂网络众多重要特性之一,而根据网络中所蕴含的信息解析出有价值的社团拓扑结构,即社团发现则是复杂网络研究领域中的一个重要方面,不仅具有重要的理论价值,对于许多现实系统还有广泛的应用前景[2-4].

社团发现算法一直备受众多研究人员的关注,如GN算法[5]、谱分析算法[6]、层次聚类算法[7]以及一些综合多种思想的算法[8,9]等.另外,还有部分工作重点针对重叠社区的发现,如基于团渗理论的CPM算法[10]、基于局部扩展的LFM算法[11]、基于集成网络的UEOC算法[12]以及基于连接划分的边社区发现算法[13]等.但现有研究大多是针对无权网络,而相比于无权网络,现实系统更适合抽象为加权网络.例如交通网络中,道路的运输能力自然可以作为边的权值;在人际关系网络中,则可以将关系的紧密程度作为权值,能够更为直观、准确的反映网络中人与人之间的联系情况.而且,不同于机会网络中的不确定连接[14],大多数现实系统中的节点关系普遍较为稳定.因此,加权网络相关研究显然具有更好的应用价值.

目前针对加权网络的社团结构发现研究较少[15],典型……