基于节点内聚系数的局部社团发现算法

为了能够快速有效地发现复杂网络中的局部社团,提出一种基于节点内聚系数的局部社团发现算法。该算法选取最大度节点作为起始社团,不断搜索其邻居节点,将满足条件的节点不断加入起始社团从而形成新的社团。在不同规模的真实网络数据集和人工合成数据集上进行实验,并与其他三种局部社团发现算法进行社团划分效果的对比。实验结果表明,该算法能够在较短的运行时间内保持较高模块度来识别复杂网络中的局部社团结构,更适合于大规模复杂网络的社团结构挖掘。     

一种基于随机块模型的快速广义社区发现算法

随机块模型可以生成各种不同结构(称作广义社区,包括传统社区、二分结构、层次结构等)的网络,也可以根据概率对等原则发现网络中的广义社区.但简单的随机块模型在网络生成过程建模和模型学习方面存在许多问题,导致不能很好地发现实际网络的结构,其扩展模型GSB(general stochastic block)基于链接社区思想发现广义社区,但时间复杂度限制其在中大型规模网络中的应用.为了在无任何先验的情形下探索不同规模网络的潜在结构,基于GSB 模型设计一种快速算法FGSB,更快地发现网络的广义社区.FGSB 在迭代过程中动态学习网络结构参数,将GSB 模型的参数重新组织,减少不必要的参数,降低算法的存储空间;对收敛节点和边的参数进行裁剪,减少每次迭代的相关计算,节省算法的运行时间.FGSB 与GSB 模型求解算法有相同的结构发现能力,但FGSB 耗费的存储空间和运行时间比GSB 模型求解算法要低.在不同规模的人工网络和实际网络上验证得出:在近似相同的准确率下,FGSB 比GSB 模型求解算法快,且可发现大型网络的广义社区.     

网络数据流存储算法分析与实现

针对网络数据流存储面临的瓶颈问题,提出同时保持时序性和属主性的网络数据流分段存储算法分析与设计模型。模型在内存中采用基于弱时序性的高速缓存数据结构,提高网络数据流实时存储的效率;在磁盘中采用基于多级索引结构的数据流生成树结构,提高基于时序性和属主性的检索效率。仿真结果表明,模型能显著提高网络数据流的实时存储能力,有效降低索引数据的信息量。     

基于分布式的RDF数据分割方法研究

基于分布式的RDF数据分割方法能够解决大规模RDF数据的分割和存储问题。为保证RDF数据的分布式存储和解决数据分割效率提出了一种基于贪婪策略的分割方法。先通过启发式贪心策略根据子图的负载均衡，依次选择度数最高的节点或者度数相对较高的节点，将其放入同一个子图中，后进行相邻顶点的优化。然后通过分区策略将子图分配到对应节点，存储到neo4j数据库并建立相应的索引将数据保存到Redis数据库。实验对比了几种数据分割算法以及图形数据库与关系型数据库的RDF数据存储方案，并验证了RDF图数据的存储方案和分割算法的有效性。     

面向大规模学术社交网络的社区发现模型

针对基于标签传播的复杂网络重叠社区发现算法中预先输入参数在真实网络中的局限性以及标签冗余等问题,提出一种基于标签传播的面向大规模学术社交网络的社区发现模型。该模型通过寻找网络中互不相交的最大极大团(UMC)并对每个UMC中的节点赋予唯一标签来减少冗余标签,提高社区发现的效率以及稳定性。标签更新时以UMC作为核心单位采用亲密度的方式由中心向四周更新UMC邻接节点的标签及权重,以权重最大值的方式更新网络中非UMC邻接节点的权重。后期处理阶段采用自适应阈值方式去除节点标签中的噪声,有效克服了预先输入重叠社区个数在真实网络中的局限性。通过在学术社交网络平台——学者网数据集上的实验表明,该模型能够将具有一定共性的节点划分到同一个社区中,并为学术社交网络平台进一步的好友推荐、论文分享等精确的个性化服务提供了支持。     

基于空间索引的WSN数据查询机制

针对当前无线传感器网络中数据查询通信开销大而带宽资源有限的问题,提出了一种基于局部聚类的数据存储模型.该模型通过将整个网络按地理位置划分区域,采用局部数据聚集存储,避免了将同种数据发送至一个存储点存储所造成的巨大通信开销,从而均衡通信带宽.在数据存储模型之上,提出了一种基于空间索引的数据查询方法(SIQ).在SIQ中只利用存储节点构建成索引的叶子节点,与利用所有节点建成的索引相比,其维护的节点数量少,索引的构建成本降低.同时SIQ采用数据属性为空间索引内容,有效地对监测数据进行多维属性的范围查询.仿真结果表明,与较成熟的DD算法和GHT算法相比,SIQ方法能克服泛洪查询所引起的高通信复杂度.     

大规模数据集下基于DBSCAN算法的增量并行化快速聚类

时空轨迹数据挖掘是发现移动对象行为模式的重要方式。针对海量轨迹数据处理的需求,提出一种增量并行化快速聚类算法。算法基于数据点的数量采用二分法对空间网格分区,结合贪心算法弹性重组分区,合理进行数据划分;进行本地局部聚类,获得合并簇候选集;采用R*-tree索引候选簇进行合并判断并处理;建立合并簇的无向无环图模型,并进行数据的全局重标签。实验结果表明:算法的弹性分区处理能有效地减少噪点数据,提高局部聚类的质量,采用R*-tree索引结构的合并策略有效提高了聚类的时间效率,聚类效果好,能实现大规模数据的在线处理。     

代数连通性在社会网络影响力传播最大化中应用研究

针对社会网络信息传播的研究多集中于具体应用场景中的传播机制,而用户间关系所形成的网络拓扑结构对传播的影响却没有给予充分考虑,因此对信息扩散的分析应当综合考虑社会网络的传播机制和结构特征;把相关系数引入到割边模型可以有效解决重叠社团划分问题,在考虑社会网络拓扑结构特征的基础上,提出了基于代数连通性的社会网络影响传播最大化模型,模型以代数连通性为主要参量计算边的中心性,实现网络社区的快速划分,通过降维达到算法效率优化;模型挖掘社区内影响力大的核心节点、度中心节点和社区间的桥节点,从中选择Top-k全局影响力最大的节点作为初始传播点集;实验结果显示,模型在传播影响范围和运行时间上都更具优势。     

基于MapReduce的高维数据频繁项集挖掘

传统的数据挖掘算法在面向大规模高维数据的挖掘过程中,存在数据特征捕捉准确率低、节点负载不均衡、数据交互频繁、频繁项集紧凑化程度低等问题。提出基于MapReduce的并行挖掘算法PARDG-MR,结合高维数据特征,设计基于维度粒化算法和负载均衡算法的DGPL策略,并对数据进行预处理,以解决高维复杂数据特征属性捕捉困难及数据划分中节点负载不均衡的问题。通过构建基于PJPFP-Tree树的频繁项集并行挖掘策略PARM,实现频繁项集的并行化分组过程,从而提高数据处理的运行效率。在此基础上,提出基于剪枝前缀推论的整合节点剪枝算法PJPFP,提高频繁项集挖掘过程中的剪枝效率,增强频繁项集的紧凑化程度。在Webdocs、NDC、Gisette 3个数据集上的实验结果表明,相比PFP-growth、PWARM、MRPrePost算法,该算法的运行时间平均缩短了约20%,能够有效提高数据挖掘效率且降低内存空间。     

关系数据库中社区发现方法研究

文中在研究了现有社区发现算法的基础上,提出了一种简单的加权网络中社区发现方法。文中基于社区结构最为普遍的性质,受社会网络中真实社区结构和并行计算的任务划分规则的启发,提出了基于核心边的加权网络中社区发现方法。该方法首先依据网络中边的权值寻找核心边;然后依据相似性度量,发现网络中的一个初始社区;最后通过隶属度度量,将发现的初始社区逐步扩展成网络中的社区结构。该方法在进行社区结构发现的过程中,仅仅依赖节点所处位置的局部信息,可以在对网络进行广度优先遍历的过程中完成社区发现工作。因此该方法具有较低的计算复杂度,可以适用于大规模网络中的社区发现。通过有效性实验和效率实验,表明该方法可以有效发现大规模网络中的社区结构。     

一种面向大型网络的快速随机化社区挖掘算法

寻找网络的社区结构对于理解真实网络的自组织机制、可视化大网络有重要的作用.然而,现有的社区挖掘算法由于性能较低,还难以处理大型网络,特别是有着百万顶点的网络.然而,百万规模的大网络却在越来越多的真实应用中大量涌现,这对于高效的有效社区识别算法提出新的需求.为此,一种新颖的随机算法被提出,能够在接近线性时间内,从大型网络上高效地挖掘质量较高的网络社区:新算法的核心思路是在每一随机步骤中对网络中的顶点进行基于深度优先顺序的编码,这样的编码有助于有效地识别社区之间的边.最后,通过针对模拟网络和真实网络的一系列实验验证了新算法的高效性和有效性.     

基于连边相似度的重叠社区发现算法研究

针对GN算法在发现重叠社区时存在的不足,以及为了降低算法时间复杂度,提出一种基于网络图中连边相似度划分连边集的重叠社区发现算法EGN。算法依据网络图的连边集进行划分,每一条边被划分到某个特定的社区,而一个节点可以关联多条连边,因此节点可以被划分到不同的社区,从而发现重叠社区。EGN算法首先需要构造网络节点之间连边关系的边图;然后根据边图中节点的关系计算网络图中连边的相似度,在节点之间相似度的基础上提出了连边之间相似度的计算方法;再按照相似度由小到大对边图删除边,构建出边图的树状图。树状图的每一层对应网络的一个划分,采用划分密度函数来衡量划分的质量,以此寻找最优的划分。最后将算法应用到Zachary空手道俱乐部网络中,并与GN算法进行对比,实验结果表明EGN算法能够很好地发现重叠社区。     

基于半局部结构的异常连边识别算法

随着网络科学领域研究的进展,所涉及的真实网络类型愈加广泛.复杂系统中存在的冗余错误关系,或出于异常目的 刻意发生的行为,如网页错误点击、电信网刺探呼叫等,都对基于网络结构的分析工作造成了重大影响.复杂网络异常连边识别作为图异常检测重要分支,旨在识别网络结构中由于人为制造或数据收集错误所产生的异常连边.现有方法主要从结构...     

基于亲密度和吸引力的二分网络社区发现算法

社区划分是二分网络研究中的一个热门话题,针对现有的二分网络社区发现算法存在从不同节点出发社区划分准确率低的问题,提出了基于亲密度和吸引力的二分网络社区发现算法（Intimacy and Attraction Algorithm,IAA）。该算法将[U]类中的每一个节点看作一个社区,通过计算出每一个社区的亲密度和社区间的吸引力来合并社区,从而得到[U]类节点的划分,最后[V]类节点划分到已有的社区中得到完整的社区划分结果。在人工数据集和真实网络上进行分析,分别利用互信息和模块度作为评价指标,实验结果表明,IAA能够更有效挖掘二分网络社区结构,具有良好的社区划分效果。     

以优先点为中心的Delaunay三角网生长算法

目的 Delaunay三角网具备的优良性质使其得到广泛的应用,构建Delaunay三角网是计算几何的基础问题之一,为了高效、准确地构建大规模点集的Delaunay三角网,提出一种基于优先点的改进三角网生长算法.方法 算法以逆时针次序的一条凸包边为初始基边,使用基边对角最大化并按照逆时针次序选定第3点构建一个Delaunay三角形,通过待扩展边列表中的数据判断新生成的两条边是否需要扩展,采用先进先出的方式从待扩展边列表中取边作为基边,以优先点为中心构建局部Delaunay三角网使优先点尽快成为封闭点,再从点集中删除此封闭点.结果 对于同一测试点集,改进算法运行时间与经典算法运行时间的比率不超过1/3,且此比率随点集规模增长逐步下降.相比经典算法,改进算法在时间效率上有较大提升.结论 本文改进算法对点集规模具有较好的自适应性与较高的构网效率,可用于大规模场景下Delaunay三角网的构建.     

P2P流媒体网络的关键节点识别算法

P2P流媒体网络中普遍存在一些关键节点,关键节点对网络的安全和通信性能起着重要作用,识别网络中的关键节点尤为重要,而传统方法对于大规模网络的关键节点识别时间开销很大,无法保证实时性。提出P2P流媒体网络中的关键节点识别算法,结合混合模式的网络结构特点,采用分区域的计算模型解决网络规模过大造成的巨大时间开销问题,根据节点的贡献度和传播能力差异定量化描述节点的重要性程度。仿真结果表明,所提算法可以快速获得节点重要性排序,有效识别P2P流媒体网络中的关键节点。     

融合连边符号语义信息的网络表示学习算法

为融合连边符号语义信息提升网络表示学习质量,针对现有算法处理复杂连边符号语义信息能力较弱问题,提出一种融合连边符号语义信息的网络表示学习算法,将包含正负关系的连边符号语义信息引入网络表示学习过程。首先,该算法设计基于三层感知机的关系预测模型刻画节点间不同类型的上下文链接关系;然后,引入随机游走策略实现上下文链接采样以适应大规模网络场景训练需求。在三个数据集中实验表明,该算法能够有效建模节点间不同类型的上下文链接关系,挖掘其中包含的复杂语义信息,相比目前最优的SIDE方法,所提算法的性能分别提高了0.31%、1.3%和1.85%。     

基于图遍历的局部社区发现算法

针对当前局部社区发现算法扩张速度慢不适用于大规模网络的问题,提出了一种基于图遍历的局部社区发现算法。该算法首先找出网络中度数最低的节点,以该节点为起点通过影响力函数将网络中的节点分为社区节点和边界节点,形成初步的社区划分,然后通过适应度函数确定边界节点的社区得到最终划分结果。实验结果表明,该算法在真实网络上进行测试时不仅能够有效地挖掘网络中的社区结构而且具有较快的速度。     

分布式入侵检测中基于能力与负载的数据分割算法

针对高速网络环境下分布式入侵检测中海量数据并行检测处理的效率和检测率问题,提出一种基于能力与负载的数据分割算法。该算法依据采集到的集群内各数据分析节点的系统性能指标及运行状态,评估节点的数据处理能力与负载程度。基于节点的能力与负载适应因子,权衡节点在集群中检测和分析数据能力的权重,实现海量数据在集群内各数据分析节点间的动态数据分割,为节点分配适应其能力与实时负载的数据粒度。仿真测试结果表明,该算法具有较好的负载均衡性,降低了系统的检测时间,提高了数据并行处理的效率和检测率。