社会合作网络中社团结构的搜索算法研究

许多实际的网络都具有一个共同性质,即它们都是由各个社团通过公共节点连接而成网络,因此,网络中社团的数目以及每个节点归属于社团的数目对于研究复杂网络都具有重要的意义。通过分析复杂网络的社团结构和寻找网络社团数目的传统算法,针对传统算法所存在的缺陷,提出了一种搜索社团结构的算法。该算法正确的对网络的社团结构进行了划分,且较好的改进了其运行效率。最后指出了进一步的研究方向。     

基于复杂网络的社区划分算法分析

近年来,复杂网咯吸引了大量的学者,作为一个新兴起来的学科,来自各个领域的学者们都开始对其进行研究分析。社区划分是复杂网络的重要特征之一。针对复杂网络中社区划分问题,对三种的社区划分算法进行了研究,传统GN算法、FN算法和谱聚类算法,分别阐述了各种算法的基本原理,并对这两种算法基于真实世界网络模型进行了适当的分析和比较,选取出较为高效的谱聚类算法,用于现实世界复杂网络中的社区划分,为实际应用中社区划分算法的认识与应用提供了方法参考。     

基于传染病模型的LPA特征阀值社团划分方法

社团结构划分对于分析复杂网络的统计特性非常重要.在非均匀社交网络的信息传播中,社团结构划分更是一个广泛关注的研究热点,相关研究往往侧重于研究紧密连接的社团结构对于信息传播所产生的关键影响.传统社团划分方法大多基于点和边的相关特性进行构建,如标签传播算法LPA（Label Propagation Algorithm）通过半监督机器学习方法,基于网络节点标签的智能交换和社团融合过程进行社团划分,但运行效率较低.为提高LPA类算法的运行速度,使其快速收敛,并提高社团划分精度,特别是重叠社团划分精度,针对LPA算法划分中的低运行效率和低融合收敛速度,本文从标签传播的网络连接矩阵本质出发,将该矩阵的最大非零特征值与网络标签信息传播的阀值相结合,提出了新的基于传染病传播模型的社团划分方法（简称ESLPA算法,Epidemic Spreading LPA）.通过经典LFR Benchmark模拟测试网络、随机网络以及真实社交网络数据上的算法验证,结果表明该算法时间复杂度大幅优于经典LPA算法,在重叠社团划分上精确度优于基于LPA模型的经典COPRA算法,特别是在重叠社团较明显时,划分精度接近精度较高GA、N-cut和A-cut算法,明显优于GN、FastGN和CPM等经典算法.     

模块度优化启发式算法应用

模块度优化的启发式快速算法常常用来检测复杂网络中的社团结构.较之其余的社团检测方法,该算法在计算时间上更具优势,而且用模块度衡量发现检测社团的质量很高.运用模块度优化启发式算法划分空手道俱乐部网络、大学足球俱乐部网络和区域贸易网络等,并对其结构和功能做出一定的分析.特别地,针对贸易网络中自由贸易区往往表现为一个社团的特点,以221个国家或地区为研究对象,对贸易协定与地域之间的关系做了大量的实证研究.首先,从世贸组织网站上采集了区域贸易协定中国家之间贸易的数据;其次,通过模块度启发式算法进行社团划分,共得出7个主要的贸易区,其中欧盟自由贸易区的社团表现极为明显;最后,从社团结构的表现形式推断实际区域间的贸易情况.     

基于结点相似性的层次化社团发现算法

复杂网络中往往存在着社团结构,通过发现网络中的社团结构,可以以社团为单位研究网络的特性和隐藏的规律,从而降低了研究大型复杂网络的难度。文中提出了一种基于结点相似性的层次化社团发现算法,设计了方法选取最佳的边权重阈值,首先得到局部核心树结构,并经过两次扩散步骤,得到网络的社团划分结果。仿真实验表明,提出的算法在较低的时间复杂度下能够取得较高的社团发现准确度。     

面向大规模应用层拓扑的社团发现技术

社团发现是复杂网络研究领域里一个极具挑战性的方向。特别地,对于现实世界中许多规模巨大的应用层拓扑,一些社团发现算法因为计算复杂度过高而不适用。另一些社团发现算法的实际性能还有待评估。为此,提出了可用于衡量社团发现算法实际应用价值的三个指标:(1)可扩展性,衡量算法能处理的应用层拓扑的规模;(2)准确度,衡量社团划分结果好坏;(3)敏感度,衡量社团划分结果的一致程度。在7个大规模的现实世界应用层拓扑图上,对三个针对大规模网络的社团发现算法(CNM算法、Wakita算法和Louvain算法)进行了比较分析。实验结果表明,Louvain算法在可扩展性上最优且所得划分结果准确度最高,CNM算法在敏感度上表现最好。     

基于Fast-Newman算法的网络社团分区在传送网汇聚区划分中的应用

目前现网中部分区域规划不合理,存在长距离组环以及业务接入不规范等问题。为解决上述问题,我们提出通过划分汇聚区的方式来实现不同区域内的业务收敛,提升组网的合理性。通过对Fast-Newman网络社区分解算法的分析,发现该算法同样是针对不同类型的大规模复杂网络,提出了寻找社团结构的算法,实现复杂网络社团结构的分解。依次类推,传送网络同样可以参考Fast-Newman算法来针对汇聚区进行科学合理的划分。     

基于FCM的复杂网络重叠社团结构发现算法

复杂网络中的社团结构发现是对网络数据集进行数据挖掘的普遍性问题.针对网络中大量存在的重叠社团现象,提出了基于FCM的发现重叠社团结构算法,并进一步在NG模块度的基础上,给出了评价重叠社团结构的模块度函数.算法首先将网络的节点映射成欧氏空间的节点,再以此做模糊聚类得到各重叠社团结构,根据模块度函数选择最佳重叠社团结构.最后,在经典网络上的实验结果表明,算法能够得到满意度高的重叠社团结构,而且时间复杂度较低.     

基于稠密子团和边聚类系数的局部社团挖掘算法

发掘复杂网络的社团结构,有助于深入理解网络结构属性及其功能重要性。本文通过定义稠密子团,结合边聚类系数和局部模块度,提出一种DIDE社团挖掘算法。该算法通过选取稠密子团作为初始聚类团,利用边聚类系数扩张该稠密子团,最大化局部模块度值来生成社团结构。在计算机生成网络、三社团网络、Zachary网络和美国足球俱乐部网络上进行社团划分,验证该算法的可行性和有效性。     

面向图表示社区检测的新型聚类覆盖算法

图表示社区检测使用图表示方法学习网络节点的向量表示,然后对节点向量进行聚类获得社团结构.然而经典的聚类算法在聚类节点向量时,得到的结果往往不能够体现社区的特性.提出一种新型的聚类覆盖算法,将聚类所得覆盖视为社区划分结果.首先在节点向量空间中计算得到每个簇的覆盖中心;然后根据覆盖中心到同类样本的平均距离作为覆盖半径,在向量空间中形成覆盖;最后对未覆盖的点做二次划分得到社区结构.在多个有真实和无真实标签网络的实验表明,所提出的算法可以得到更合理的社区结果.