复杂网络的社区发现算法研究

复杂网络是对于复杂系统的高度抽象,其中许多性质如小世界性质、无标度性质以及聚集性质等等已经得到了充分的研究。大量文献表明,复杂网络呈现出的社区结构特性。如何在大型网络中高效地发现社区问题是近年来复杂网络的研究热点。文章讨论了一些关于社区发现方面的概念、理论、算法及应用等,并简述了其发展趋势。     

基于优化理论的社区无标度网络模型

当前建模社区无标度网络的研究多基于组合法,即先构造无标度特征再构造社区特征,或者先构造社区特征再构造无标度特征.基于组合法的模型能生成令人满意的社区无标度网络,但是该方法需要满足社区大小相等、社区特征和无标度特征间的顺序依赖等特定条件,而这些特定条件在真实网络的演化中往往并不存在.值得注意的是,多数学者同意社区网络起源于网络节点之间的类别距离,如地理距离、兴趣距离、偏好距离等,但现有研究尚未确证社区结构与类别距离之间的因果关系.针对组合法的缺点和社区特征起源的问题,该文建立了一个优化模型,该模型以无标度属性为优化目标,以类别距离为约束条件.仿真结果表明该模型揭示了类别距离与社区特征间的因果关系,能生成多种参数下的社区无标度网络,更好地拟合了现实世界中的社区无标度网络.     

基于多标度曲线的股市网络构造及其社区挖掘

针对股票市场的复杂网络建模问题,提出使用不同阶数下的标度曲线(多标度曲线),测度沪深300指标股之间的加权多重分形特征相似性,并据此构造网络,研究网络的拓扑性质。在此基础上采用快速 Newman, Girvan-Newman,Louvain等经典算法挖掘网络社区结构,利用最大模块度确定最优相似性门限值,通过投资组合MV模型验证方法的有效性。实验结果表明,多标度曲线网络具有无标度、小世界和富人俱乐部性质,使用不同算法挖掘其社区结构可得到最优的划分效果。基于该网络社区结构构造的投资组合可有效降低风险。     

基于结构的社会网络分析

互联网的发展和社交网站的流行为研究社会网络提供了大规模的实验平台.主要使用DBLP和Facebook数据集构建网络,采取角色连接轮廓方法从结构上进行划分,发现它们属于外围串类型;验证了社会网络的一些统计性质,比如无标度分布、稠化定律和直径缩减等;发现社会网络中存在紧密连接且直径较小的核心结构,规模中等的社区主要呈现星型结构;基于事件框架研究了社会网络中社区结构的进化,发现社区间的融合很大程度上取决于社区间直接连接的节点所构成网络的聚类系数,而社区的分裂则与该社区的聚类系数相关.     

社会结构对财富分布的影响分析

将社会结构抽象化为随机网络（ER图）、小世界网络（WS网络）以及BA无标度网络三种不同的拓扑网络结构,分析了社会关系结构对社会财富分布规律的影响。通过模拟仿真以及实证研究得到,与ER随机网络以及WS网络相比,以BA无标度网络为基础的社会结构网络中的财富分布与真实社会中的财富分布规律是吻合的。因此说以BA无标度网络可以很好地刻画社会关系结构,其将为人类提供更多的财富信息,为进一步研究社会财富的累积、转移和重新分配提供了重要的理论基础。     

社区发现在复杂网络划分中的应用

在无标度网络中,社区结构是普遍存在的一种网络结构特性,社区结构是网络中间层的描述,是对网络的自然压缩。文中基于这一事实,将社区结构发现方法加入到多层网络划分框架中,提出了基于社区结构的多层网络划分改进策略。该方法首先对无标度网络进行社区发现;然后以发现的社区结构为单位,对原网络进行压缩;之后对压缩后的网络进行初始划分;最后将划分结果还原为对原网络的划分。在进行初始划分时,为获得较好的划分效果,引入了0-1规划方法,并使用K-L算法进行优化。通过对比实验,结果表明把社区结构引入多层网络划分方法中,可以获得更好的划分。     

具有社区结构的无标度网络生成算法

近年来,生成图模型在复杂网络研究中的作用越来越重要。图的生成过程对于研究疾病的蔓延和信息的传播具有重大意义,同时图模型的生成也有助于更深入地研究复杂网络的特性。为了能够生成既符合真实网络特征又具有结构多样性的复杂网络,提出了一种具有社区结构的可调节聚集系数和模块性的无标度网络生成算法——TCMSN(Scale Free Network with Tunable Clustering Coefficient and Modularity)。通过调节混合参数可以调节生成网络的模块性,通过调节社区内连边的概率和混合参数可以对网络聚集系数进行调节。TCMSN采用了合理的连边策略,在不破坏网络结构多样性的情况下,能尽可能维持网络的无标度特性。人工构造数据和真实网络数据的对比实验结果表明,TCMSN算法能够生成可调节聚集系数和模块性的无标度网络模型,且能够生成最接近真实网络社区结构特征的网络模型。     

复杂网络传播机理在贵州电网中的研究

在许多现实网络中其拓扑结构决定了网络的性质和动力特性,在对贵州电网的研究中我们发现,贵州电网表现出的是局域无标度特性,基于这一特性,我们运用局域无标度网络的传播机理对贵州电网中的电力拥塞进行了分析,并求解出了它的传播临界值,最后,我们通过对几种主要免疫策略的对比研究,得到了适合于局域无标度网络的免疫策略.     

基于随机游走的蠕虫网络演化研究

鉴于无标度网络的健壮性和小世界特性是蠕虫网络的理想特征,借助于复杂网络理论,提出了一个基于随机游走的蠕虫网络演化模型。该模型依据主机性能和网络的带宽采取择优的方式从蠕虫网络中选择合适的节点与新感染的主机建立连接。理论分析和模拟实验表明：所建立蠕虫网络具有无标度网络的性质。     

考虑群组结构的在线社交网络竞争性舆情信息传播模型研究

针对在线社交网络中竞争性舆情信息同时传播的问题,在无标度网络的基础上引入群组结构,构建竞争性舆情信息传播模型,考虑舆情信息内容、用户亲密度、社会强化效应因素并进行仿真研究。仿真结果表明,引入群组结构的无标度网络充分契合了在线社交网络的复杂性质;群组数量、群组规模、用户亲密度、社会强化效应对竞争性舆情信息的传播有不同的促进作用;控制舆情信息内容的重要性与模糊度可有效调控竞争性舆情信息的传播与扩散。