基于Spark的并行增量动态社团发现算法

动态社团发现是研究网络演化的关键步骤。在数据量迅猛增长的情况下,社团发现的单机算法效率较低。该文提出了一种基于Spark的并行增量动态社团发现算法(parallel incremental dynamic community detection algorithm based on Spark,PIDCDS),为了在GraphX并行图计算平台上通过最大化持久力发现社团,该算法对节点的持久力计算公式进行了有效修正。PIDCDS计算每个时间片中增量节点的持久力指标,更新其社团归属,在保证一定的社团划分准确性的基础上减少计算量。通过与FacetNet动态社团发现算法做比较,该算法能够获得更好的稳定性,同时能发现更真实的社团划分。对比不同规模网络在PIDCDS上的运行时间,发现该时间随着网络节点和边数的增加缓慢增长,性能较高,并且增加执行器核数将在一定程度上加速算法的执行。     

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

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

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

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

基于单步添加团的重叠社团检测算法

基于局部扩充的重叠社团检测算法由单个节点或团出发,不断添加新的节点而获得最终的社团划分,但现有算法均为每次添加一个节点,没有充分考虑所添加节点的局部信息,从而影响了社团检测结果的准确性.为此,文中提出了一种基于单步添加团的重叠社团检测算法,该算法从一个团开始,通过不断添加此团邻居内适应度增值最大的团,使算法在局部扩充时不仅考虑了所添加节点与已有社团的连接紧密性,而且考虑了所添加节点内部的连接情况.在真实网络和计算机生成网络上的实验结果表明,与现有基于局部扩充的重叠社团检测算法相比,文中算法可以更准确地检测出复杂网络中的重叠社团.     

基于定向天线的无线自组网拓扑控制算法

为采用定向天线的特点解决无线自组网中节点异构、能量有限、带宽受限的问题,提出了一种基于定向天线的异构无线自组网拓扑控制算法K-DRNG.该算法包括三个阶段:信息收集阶段,节点控制发射功率,通过扇区转换机制收集邻域拓扑信息;拓扑构建阶段,节点根据链路权重和节点剩余能量构建定向邻近图;拓扑优化阶段,构建初始拓扑子图及添加或删除方向性链路,确保生成拓扑的双向连通性.仿真结果表明,算法能够降低网络中的节点平均能耗,提高无线资源空间复用性,改善网络性能.     

基于加权树的层次社团划分算法

社团发现常用于挖掘复杂网络中的隐藏信息,如功能模块和拓扑结构.为提高复杂网络中社团结构挖掘的质量,提出一种基于加权树的层次社团划分算法HCD_WTree(Hierarchical Community Detection Algorithm Based on Weighted Tree).首先,结合邻域重叠比和节点的度中心性来度量节点间关系强度,基于该度量将原无权网络转换成加权网络;接着,对网络进行简化,得到加权树;最后,基于层次社团挖掘方法,根据边权依序裁剪加权树,得到层次的社团结构,并结合模块度函数获得最优的社团划分结果.在公用数据集上的实验结果表明,与现有的社团挖掘技术相比,HCD_WTree算法能够更准确地划分复杂网络中的社团结构.     

无人机集群网络中一种基于链路质量预测的按需路由算法

无人机集群网络,相较于传统Ad Hoc网络,其节点速度更快,拓扑变化更剧烈。传统路由算法已难以满足无人机集群作战需要。因此,提出一种基于链路质量预测的按需路由算法。通过链路稳定度和节点拥塞度评估当前链路质量,并以此作为选路标准。同时,通过灰色-WNN组合预测模型,对相关参数进行合理预测,并以此估计链路稳定性与节点拥塞程度,进而对链路质量进行提前评估。算法根据得到的链路质量预测值来优化路由发现与路由维护过程,避免无人机的高动态特性对集群网络的不利影响。仿真结果表明,与AODV及其他相关改进算法相比,该算法明显改善了网络性能,减少了路由断裂的次数,大幅降低了节点高速移动时的路由开销与平均时延,使分组投递率得到明显提高。     

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

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

动态分布式社团检测算法

针对手持设备网络,提出动态分布式社团检测算法。首先利用节点相遇历史数据计算累积相遇持续时间与相遇次数均值,并作为动态阈值确定节点朋友集合,然后构建本地关系图,最后对本地关系图进行多社团检测。仿真结果表明该算法能够反映节点间关系的变化,更适用于动态变化的移动容迟网络环境。     

一种基于异域自适应的新型社团发现算法

社团发现已被广泛应用于社会学、生物学、物理学和计算机科学等诸多领域.通过发现复杂网络中的社团结构,可以帮助人们理解和分析复杂网络的功能,发现复杂网络中隐藏的规律并预测复杂网络的行为.目前,已有的社团发现算法主张融合网络结构信息和内容信息,以更好地避免网络噪声和节点缺失等原因对算法有效性产生影响.然而,它们并没有考虑当网络结构信息和内容信息维度不同时如何进行信息融合.针对该问题,提出一种基于异域自适应理论的网络社团发现算法CDHDA.该算法能够将不同维度的网络结构信息和内容信息映射到同一维度的子空间中,以实现对不同维度的信息融合.此外,在信息融合过程中可以对主要信息特征进行加强,以降低网络噪声和节点缺失对算法性能的影响.通过真实的社交网络数据集与经典的社团发现算法进行对比,验证了该算法的有效性.