基于贝叶斯后验模型的局部社团发现

基于节点的局部社团发现在大数据社会网络分析中非常重要。针对Newman模块度在社团发现中的局限性,基于贝叶斯后验模型提出了BS模块度度量法。该方法结合节点的模块度和推荐概率进行建模,并以邻接并入为框架得到了一种新的局部社团发现算法。该方法克服了Newman模块度在稀疏网络中区分度低的问题以及社团结构差异大的分辨率问题,有效地寻找大规模网络中的局部社团。通过与Newman模块度在真实社团中的比较,验证了该度量方法的有效性。     

空铁综合运输网络结构特征实证分析

为探究中国空铁综合运输网络结构特性,以城市为节点,若城市间有航班或高铁则连边,以航班数量和高铁数量为权重,分别建立了3个加权网络：高铁子网络、航空子网络和空铁综合运输网络。首先,通过均值关联、三角中介中心度、加权谐波中心度指标对比研究了不同网络的关键节点;其次,通过聚类系数和平均最短路径长度研究了三个网络的小世界特性;再次,通过Newman算法研究了三个网络的社团结构;最后,通过加权网络效率为指标,研究了三个网络的鲁棒性。研究结果表明,北上广深是三个网络的三种不同加权中心度的排名都很靠前,是共有的最为关键的节点。三个网络都具有小世界特性,但只有高铁子网络的模块度值大于0.3,存在明显的社团结构,并被划分为了10个社团。空铁综合运输网络具有更好的加权网络效率,约为0.32,为三个网络中最高,节点失效时的加权效率变化最小,鲁棒性最强。可见空铁综合运输网络集成了高铁网络、航空网络的互补优势,网络结构特征优于单一运输网络。     

一种改进的基于节点相异度的社团结构划分算法

提出一种改进的基于节点相异度的社团结构划分算法.首先根据度和平均度评估标准,筛选出核心节点作为初始核心节点集,然后基于节点相异度进行划分,直至社团结构划分完成.实验结果证明,与其他一些算法相比,该算法的划分效果比较精确且易于实现.     

一种信任关系网络中的社团结构检测算法

针对群智计算和感知服务中不可信服务节点可能引入的安全威胁问题,提出了一种基于节点间信任关系网络的社团结构检测算法。该算法通过分析信任关系网络的功能和结构特点,引入连接的方向和权值因素,建立有向加权网络模型,定义最优路径相似度作为节点聚合标准,提出社团离散指数作为评价函数控制检测过程,从而准确识别信任关系网络中的可信节点集合,为服务节点选择提供参考。算法引入节点相似度阈值和归属判定指数控制社团聚合,与误分类节点再筛选环节配合,有效降低了检测过程中的节点误判概率,有针对性地设计社团离散指数作为评价函数,动态评估检测结果并调节聚合参数,保证了社团结构检测结果的准确率及合理性。实验结果表明:该算法能够有效实现信任关系网络中社团结构的检测与识别,与已有算法相比,检测准确率提高了5.88%。     

基于核心图增量聚类的复杂网络划分算法改进

基于核心图增量聚类的社团划分算法,设置了一个结点度阈值,利用该阈值在给定网络中筛选核心结点,以这些核心结点构造核心子图,调用GN算法产生社团框架;根据结点与社团的相似度,将除核心结点之外的结点划归到各个社团,经过反复调整各结点的归属,产生网络的社团划分。通过举例说明当度阈值设置不当,筛选出的核心结点所构成的核心子图并不能清晰地构成给定网络的各社团框架,从而严重影响网络的社团划分效率与效果。为此对其进行了改进。文中提出的是一种启发式算法,利用结点的度来逐步产生各社团框架,最后生成各社团。通过在真实网络数据集上测试,说明改进算法是高效的。     

兰州市公交网络的社团结构与脆弱性分析

基于复杂网络理论,研究兰州市公交网络的社团结构及其脆弱性.根据实证数据建立了兰州市公交网络的结构模型,并应用Fast Newman算法分析公交网络的社团结构,给出了最优的社团划分;从获得的社团结构出发,分析了兰州市公交网络社团结构的脆弱性,给出了各个社团的脆弱集及脆弱性指标.研究结果表明,兰州市公交网络具有明显的社团结构特性,社团划分受到城市独特地形特性的影响;许多社团在网络中表现异常脆弱,社团之间联系稀疏,极易因为随机故障或蓄意攻击而形成多个独立的连通分支.     

基于社团密合度的复杂网络社团发现算法

传统的社团发现算法大多存在划分效果和复杂度相矛盾的问题,为了解决该问题,提出一种新的单社团结构评价标准——社团密合度(group density).在此基础上,设计了一种基于凝聚思想的社团发现算法,该算法通过不断融合小社团,使网络的社团结构向平均社团密合度最大的方向发展,并使用模块度检测算法的划分结果.通过与经典的GN,Fast Newman,LPA等算法对多个数据集进行实验对比,验证了本文算法在获得较好的划分效果的同时具有较低的时间复杂度.     

采用链路聚类的动态网络社团发现算法

针对当前基于节点的动态网络社团结构发现算法难以发现稳定的社团结构的问题,提出了一种采用链路聚类的动态网络社团发现算法(LDC)。该算法首先从链路的角度得到网络的链路图结构;然后对比不同时刻的链路图结构,将动态网络中节点的添加与移除以及边的添加与移除等复杂的变化信息简化为链路添加和链路移除2种增量变化信息;再在前一时刻社团结构的基础上以改进的链路划分密度函数对增量变化信息中变化的链路进行处理,判断该链路是否加入到社团中从而得到最优的社团结构;最后将得到的链路社团转化成为最终的节点社团结构。实验结果表明,相比于当前基于节点的动态社团发现算法,LDC算法能够有效地发现网络中结构稳定的社团结构,其模块度值和标准化互信息值至少提高了0.19和0.13,且算法的运行效率要明显优于基于节点的动态社团发现算法。     

一种基于节点重要度的社团划分算法

指出了通过挖掘复杂网络中存在的社团结构,可以分析整个复杂网络的拓扑结构和功能,还可以发现网络中隐藏的规律.为了得到最佳社团划分结构,定义了网络的节点重要度矩阵和聚类矩阵,结合图的特征谱平分法和模块度函数,提出了一种基于节点重要度的社团划分算法(CDNIM).通过在空手道俱乐部、海豚关系网络等多个经典数据集上应用,结果表明:该算法能够有效提高发现社团结构的准确率.     

复杂网络中的层次结构挖掘

挖掘复杂网络中的层次结构对复杂网络的研究有着重要的意义.复杂网络中的社团结构往往具有层次性.过去的研究中,研究者更多的关注于层次社团结构,而很少关注于社团内部成员的层次结构.因此,提出一种基于模糊相容关系的层次结构挖掘算法(fuzzy tolerance relation based hierarchical structure detection algorithm,FHSD),旨在挖掘层次社团结构以及社团内部成员层次结构.在该算法中,首先通过相似度函数计算节点之间的相似性从而获取一个满足模糊相容关系的相似度矩阵;其次,基于相似度矩阵获取对应的商空间链;然后,依据重叠节点对各社团的隶属度处理商空间链各层中的重叠节点,从而得到层次社团结构;最后,基于处理后的商空间链,获取对原始模糊相容的近似模糊等价关系,从而获取社团内部成员层次结构.在真实网络上的实验结果表明:(1)复杂网络中不仅存在层次社团结构,同时存在基于模糊相容关系的社团成员层次结构;(2)相比于当前主流的社团挖掘算法,FHSD挖掘出的社团结构具有最高的精准性(NMI accuracy)和较高的模块度值.     

基于中心度发现的中心社团

使用度中心度与流介数中心度相结合的方法,首先计算出节点的度中心度和流介数中心度,得出网络中的几何中心点和信息、物质或能量在网络上传输时经过路径最多的节点,并将这两个指标作为一个整体考虑,得到这两个指标相对比较大的节点,再在这些节点和其邻居节点上利用CPM社团发现算法,从而发现网络中的中心社团.此方法可以发现网络中相对"重要"的社团,对复杂网络上的传播机理、相继故障等分析都有一定的意义.随后利用该方法分析兰州市公共交通线路网络的中心社团结构,结果表明该社团在网络中的确可以起到比较重要的作用.     

基于相似性模块度最大约束标记传播的网络社团发现算法

提出一种基于相似性模块度最大约束标记传播的快速网络社团发现算法(MLPA)。该方法采用结构相似度计算,通过最大约束标记传播模型更新节点标记,使社团的划分结果更加符合社团内部结构相对紧密、社团之间结构相对稀疏的特点,提高社团划分的精确度。结合标记传播5次循环迭代可以完成95%或者更多节点标记过程的实验结果,判定标记更新过程趋于稳定,从而在稳定时停止更新,降低了运行时间。MLPA避免了传统的邻接矩阵计算方法,适合大规模网络的社团发现。     

基于先验知识与模块性的网络社区结构探测算法

在分析模块性指标和Newman有关网络社区结构探测算法的基础上，提出了一种基于先验知识与模块性的社区结构探测算法．利用节点度等社会网络结构先验知识，获得一个社区结构的基本划分，然后进行社区的合并，以此获得一个清晰的社区结构．经计算机模拟网络、Ucinet软件网络和中国农民工社会网络的社区结构探测，结果表明所提算法比Newman的迭代次数减少近50％，并且可以获得更好的模块性指标．     

基于相似性模块度最大约束标记传播的网络社团发现算法

提出一种基于相似性模块度最大约束标记传播的快速网络社团发现算法(MLPA)。该方法采用结构相似度计算, 通过最大约束标记传播模型更新节点标记, 使社团的划分结果更加符合社团内部结构相对紧密、 社团之间结构相对稀疏的特点, 提高社团划分的精确度。结合标记传播5次循环迭代可以完成95%或者更多节点标记过程的实验结果, 判定标记更新过程趋于稳定, 从而在稳定时停止更新, 降低了运行时间。MLPA避免了传统的邻接矩阵计算方法, 适合大规模网络的社团发现。     

一种可变分辨率的社团发现算法

介绍了复杂网络及社团结构的相关概念,给出节点的综合特征值和增益函数的定义,然后提出一种新的社团发现算法(CNCD).综合特征值与节点的度数及其聚类系数有关,用于发现社团中的核心节点;增益函数决定何时获得社团结构的最佳划分.作者用C++语言实现算法,并使用经典数据集对算法进行验证,实验结果表明此算法不仅能够得到正确的社团结构,而且通过动态调整算法中的参数值,能够得到比传统算法更加详细的社团划分结果,获得网络的细节信息.     

移动社交网络中基于用户动态需求的D2D数据分流方法

针对因数据流量的爆炸式增长给蜂窝网络带来的流量负担和网络拥塞等问题,提出一种基于移动社交网络中用户动态需求的D2D数据分流方法。考虑用户在一天中不同时段的兴趣和移动轨迹,构建用于描述用户流量需求的图结构。通过Newman快速算法将移动用户划分为不同的社团,同一社团中的用户具有相似的数据需求并且经常彼此联系。在此情况下,每个社团挑选不同的种子用户进行数据共享。为了最大化蜂窝网络的数据分流,对比五种不同的中心性度量方法选择种子节点,采用对比实验,证明新提出的DDS方案的有效性。实验结果表明,在DDS策略中,PageRank度量方法选择的种子节点分流表现最好。     

基于电阻网络的节点重要性判别

节点中心性是复杂网络研究的关键问题之一.我们从电阻网络出发,基于基尔霍夫电流定律,定义了一种新的中心性指标KL(G),该指标由通过节点的电流和基于度的电流方差构成.这个指标在网络流的基础上考虑了网络的全局信息和节点所处位置的局部信息.我们将指标应用于实际网络中,发现其可以识别出对于社团结构来说重要的节点,结合辅助指标w还可以区分社团重叠节点和桥节点.     

基于多属性融合策略的复杂网络社团划分算法

为解决目前社团划分算法依赖于单一度量方法,划分结果不够准确,无法适应不同类型的网络划分需求的问题,通过一种多属性融合策略方法研究社团划分。该算法首先基于节点连接,综合度量了多个影响社团划分的属性,并引入模块度概念确定各属性融合的权重,为划分增加了客观的参考信息,从而提高划分准确率;其次,针对传统划分方法迭代次数过多、效率低的问题,利用人工免疫网络内在的全局并行搜索能力实现对社团核心节点的快速寻优,并提出动态算子、免疫检测因子和反向学习机制对人工免疫网络的收敛速度和局部最优问题加以改进,从而提高寻优效率,缩短算法执行时间。最后,在三个经典真实数据集(Zachary、Dolphin、College Football)上进行实验,并将结果与经典算法对比。结果表明,该算法能适应不同的网络,且在较短的执行时间里实现更加精确的划分。可见,相比传统算法,本文算法具有更高的划分效率。     

基于最短路径相似度的复杂网社团识别算法

基于最短路径的思想,定义新的节点相似度,利用谱平分算法来识别复杂网络的社团结构.首先根据节点间最短路径的思想计算改进的共享最近邻(SNN)相似度,将其标准化后求出标准化矩阵的特征值及特征向量,然后根据网络选取一定数目的第一非平凡特征向量作为聚类样本,利用FCM算法可识别网络的社团.实验结果表明,该算法对于社团结构不明显的网络划分效果很好.     

基于模块度优化的加权复杂网络社团发现算法分析

社团结构是复杂网络的一种重要拓扑结构。针对加权复杂网络中的社团发现问题,在8个不同领域、不同规模的真实数据集上,从模块度、强/弱社团、聚集系数3个评估指标分析了基于模块度优化的GN算法、FN算法、CNM算法和BGLL算法在加权复杂网络社团发现的效果。研究结果表明,上述3个评估指标在加权复杂网络上的划分结果不能始终保持一致,基于优化模块度的算法更倾向于找到复杂网络中比较粗糙的社团结构,而不是精准的社团结构,其算法的泛化能力有待加强。