近年来,复杂网络中社团检测问题成为生物组织、计算机网络、交通管理等领域的一个研究热点。模体已经被证实在网络拓扑结构的演化过程中起到重要作用,然而,传统的社团结构理论只考虑了社团相关的连边信息,不能有效揭示网络的个体行为模式和演化规律,另外,现有的社团检测算法主要是从全局角度设计的,在局部范围应用时效率不高,而且在算法的有效性和稳定性方面缺少统一的评价指标。因此,合理定义社团,设计高效、稳定的社团检测算法是其核心内容和难点问题。本项目首先探讨模体和社团结构的演化关系,研究基于模体的社团定义和相关测度量;接着研究局部社团检测算法,针对社团结构的不均匀性,寻求边界阈值的动态控制策略。这些研究对于揭示复杂网络拓扑结构的演化规律、促进社团结构理论的发展具有重要意义。
community structure;motif structure;complex network;measurement;community division algorithm
随着复杂网络理论研究的不断深入,复杂网络中社团结构的特性广泛应用于生物学、物理学、计算机图形学和社会学中,探索网络中的社团结构具有很重要的现实意义。随着对网络拓扑性质的深入研究,人们发现模体结构在网络中的存在性,模体是网络的基本结构之一,其大小介于单个节点和社团之间,在研究社团性质时需要考虑模体结构的存在性。 本项目研究复杂网络中基于模体的社团结构及检测算法,主要包括以下内容。(1)用Rand-ESU算法对规模大小不同的9个网络进行模体检测分析,验证了模体在网络中的存在性。对Dolphin网络、Social 网络和Science网络进行详细的模体分析,包括模体的种类、结构特征等。提出基于模体的顶点度和边度的定义,研究基于模体的顶点度和边度与传统定义的相关性,通过相关性研究验证新提出的定义的合理性。(2)给出基于模体的社团的定义、基于模体的模块度的定义,提出基于模体模块度的改进GN算法,用Dolphin网络进行仿真分析,通过与真实网络中划分出的社团的对比研究验证改进GN算法的优越性。(3)提出基于模体的边聚类系数的定义,在此基础上提出基于模体边聚类系数的社团发现算法,用金融网络进行实证分析,研究金融网络的模体结构,用基于模体边聚类系数的社团发现算法对金融网络进行社团划分,对金融网络进行蓄意攻击和随机攻击,通过对比网络受攻击前后社团划分的差异性验证该算法的稳定性。 本项目提出了基于模体的复杂网络测度量和社团结构检测算法,实验结果表明研究网络测度理论和社团结构理论时考虑模体结构是有意义的。