基于矩阵分解的二分网络社区挖掘算法

二分网络社区挖掘对复杂网络有重要的理论意义和应用价值。提出了一个基于矩阵分解的二分网络社区挖掘算法。该算法首先将二分网络分为两个部分,每个部分尽可能保存完整的社区信息,然后分别对两个部分进行递归的拆分,直至不能拆分为止。在拆分的过程中,应用矩阵分解,使得到的分解能与网络的相关矩阵的行空间尽可能接近,即尽可能保持原图的社区信息。实验结果表明,该算法在不需任何额外参数的情况下,不但能较准确地识别实际网络的社区个数,而且可以获得很好的划分效果。     

一种改进的基于广义后缀树的文本聚类算法

分析了基本STC算法存在的三个缺点,即不能有效处理包含文本数目差距较大但具有包含关系的节点,不能有效处理包含文本相似但主题不同的节点,缺乏有效的类别标识提取算法．针对以上问题,在综合考虑主题相似性以及文本包含相似性的基础上,给出了改进的用于基类合并的相似度公式,并提出了基于信息增益的类别标识提取算法．为了进一步提高聚类效率,给出了一种简单有效的用于基类选择的测度,用来排除一些无意义的广义后缀树节点．实验结果表明,所提算法不仅可以有效提高STC算法的聚类准确度,而且可以对聚类结果进行有效的类别标识．     

基于蚁群优化的二分网络社区挖掘

近年来,网络社区挖掘得到了极大的关注,尤其是针对二分网络的社区挖掘。二分网络社区挖掘对于研究复杂网络有非常重要的理论意义和实用价值。提出了一个基于蚁群优化的二分网络社区挖掘算法。该算法首先将二分网络社区挖掘问题转化成一个优化问题,建立一个可供蚂蚁搜索的图模型。同时,根据顶点的拓扑结构定义启发式信息。每只蚂蚁根据每条路径上的信息素和启发式信息选择路径,构造出一个社区的划分,再用二分模块度去衡量社区划分的优劣。实验结果表明,该算法不但可以较准确地识别二分网络的社区数。而且可以获得高质量的社区划分。     

基于连边密度传播的二分网络社区发现算法

依据节点在社区中的连边情况,定义社区内节点的连边密度,构造社区的平均密度评价指标。经过实例验证,社区的平均密度评价指标能够克服模块度在完全图上的分辨率限制。同时,通过节点的连边密度和最优化社区的平均密度,提出连边密度传播算法。在真实数据和人工数据上进行测试,利用该算法划分社区后求得的模块度和社区平均密度都比利用BRIM算法、边集聚系数算法和资源分布算法求得的值高。这表明相比以上三种算法,连边密度传播算法更能够有效地发现二分网络的社区结构。     

后缀树的并行构造算法

后缀树是一种非常重要的数据结构,它在与字符串处理相关的各种领域里有着非常广泛的应用。构造后缀树是应用后缀树解决问题的前提和关键。虽然很多现有的后缀树构造算法都是线性时间和空间的,但是,当被索引的字符串的长度很长时,构造其后缀树所消耗的时间和空间仍将非常巨大,这极大地限制了后缀树的实际应用。而并行技术是解决这一问题的很好途径,因此人们提出了后缀树的并行构造算法。本文对后缀树的三种并行构造算法进行了综述,通过系统的比较和分析,总结出当前存在的问题,并指明了下一步的研究方向。     

一种高效的广义后缀数组构造算法

本文介绍了后缀数组和广义后缀数组的概念,然后提出了一种类似桶排序的广义后缀数组的高效构造算法,并对算法的复杂度进行了分析.     

维吾尔文后缀树构造算法的设计与实现

为用后缀树聚类算法对维吾尔文网页进行聚类,通过分析可扩展后缀树和维吾尔文的特点设计了维吾尔文后缀树构造算法。实验结果证明该方法能够在线性的时间范围内构造维吾尔文后缀树,并用它来对维吾尔文网页进行聚类。     

一种基于后缀树的Web访问模式挖掘算法

在Web使用挖掘中,分析用户的行为模式是一个关键的问题。文中提出了一种基于后缀树的最大频繁序列MFS(Maximal Frequent Sequences)的有效挖掘算法,该算法能够从增量数据中动态发现和输出MFS。     

基于位置序列的广义后缀树用户相似性计算方法

为了解决移动数据形成的轨迹间用户相似性问题,提出了一种基于位置序列的广义后缀树(LSGST)用户相似性计算方法。该算法首先从移动数据中抽取位置序列,同时将位置序列映射为字符串,完成了对位置序列的处理到对字符串处理的转化工作;然后,构建不同用户间的位置序列广义后缀树;最后,分别从经过的相似地方个数、最长公共子序列、频繁公共位置序列三方面对相似性进行具体计算。理论分析和仿真表明,该算法提出的三个计算指标在计算相似性方面具有理想的效果;除此之外,与构造后缀树的普通方法相比,时间复杂度较低;与动态规划和朴素字符串匹配方法相比,该算法在寻找最长公共子串、频繁公共位置序列时,效率更高。实验结果表明LSGST能够有效测量相似性,同时减少了寻找测量指标时需要处理的轨迹数据量,并在时间复杂度方面明显优于对比算法。     

基于后缀树的骨干网络垃圾邮件检测方法

虽然目前垃圾邮件过滤或检测的研究比较多,但是它们大多数是基于邮件客户端。文章提出了一种基于后缀树的骨干网络垃圾邮件检测方法,它采用后缀树文本表示方法,通过不定长统计方法判定邮件是否相似,然后利用邮件重复出现的次数判定是否为垃圾邮件。该方法不需要任何训练,直接对接收的邮件进行分类统计;对于长度为的邮件,算法的时间复杂度和空间复杂度均为;另外,该方法独立于任何语种。     

SuffIndex--一种基于后缀树的XML索引结构

针对形如∥element1／dement2／…／elementm0的查询,提出了一种基于后缀树(suffix tree)的XML索引结构SuffIndex．SuffIndex的构造通过只对OEM数据树遍历一次以及在SurfIndex中引入后缀链(SuffIink)的方法,从而达到较低的构造代价．SuffIndex中所有结点利用Hash表保存到其所有子结点的指针,最终使查询∥element1/element2／…／elementm的处理代价为O(m)．     

基于模块度增量的二分网络社区挖掘算法

针对二分网络的社区挖掘问题,提出了一种基于模块度增量的二分网络社区挖掘算法。该算法假设每个顶点独自构成一个社区,并具有自己的标号。其中,一部分顶点将自己的标号复制并传递到另一部分中的某个顶点上,使之与其位于同一个社区;另一部分的顶点实施同样的操作。如此反复迭代,直至收敛。标号传播时,选择模块度增量最大的边进行传送,使整体模块度不断提高。在真实数据集上进行的测试表明,所提算法能对二分网络进行高质量的社区划分。     

基于WB-MMSB模型的微博网络社区发现

提出了一个用于微博网络社区发现的模型WB-MMSB,该模型考虑了微博网络中节点存在的单向关系,节点的社区隶属度从链入主题隶属度和链出主题隶属度两个方面表示。用指数族分布和平均场变分推理方法推导了模型中各变量的表示,并用SVI算法计算模型涉及的参数。实验在新浪微博数据集上进行,采用归一化互信息和困惑度进行评估,结果表明,WB-MMSB模型的社区发现能力优于aMMSB模型,并且其收敛速度快于aMMSB模型。     

基于通用后缀树模型的垃圾邮件过滤方法

采用通用后缀树模型(GSTM)，利用邮件内容的上下文信息，进行每个文本位置的不定长多元统计，从而获得被测邮件与不同训练集的相似程度，确定邮件所属的类别。理论分析和实验表明，在相同语料上，该方法的精确度和召回率均达到或超过了基于向量空间模型的邮件过滤方法；对于长度为N的邮件，过滤时间为O(N)；长度为N的新邮件加入训练集，训练时间为O(N)，满足了训练集的动态增长；该方法不需进行分词处理，完全独立于语种，适用于多语种邮件同时存在的情况。     

基于非压缩后缀树的在线PPM预测模型

PPM模型适合预测用户的下一个请求,但已有的PPM模型不具备在线性,更新通过重构来实现,不能满足实时更新的要求。该文提出基于非压缩后缀树的在线PPM预测模型,采用非压缩后缀树实现增量式在线更新,提高了模型的更新速度。该模型的优点是具备在线性。     

改进的维吾尔语Web文本后缀树聚类

该文提出了改进的维吾尔语Web文本后缀树聚类算法STCU,其中后缀树的构建以维吾尔语句子为基本单位。针对维吾尔语语言和Web文本特点,文中对词语进行词干提取,构建了维吾尔语绝对停用词表和相对停用词表,采用文档频率和词性结合的方法提取关键短语,改进了合并基类的二进制方法,根据语料类别数自动调整聚类类别阈值,利用最一般短语对聚类类别进行描述,有效地改善了文本聚类的质量。与传统的后缀树聚类算法相比,聚类全面率提高了44.51%,聚类准确率提高了11.74%,错误率降低了0.94%。实验结果表明 改进的后缀树算法在Web文本聚类的精度和效率方面具有较强的优越性。     

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

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

基于信息扩散概率的二分网络社区划分算法

二分网络是复杂网络的表现形式之一,二分网络单侧节点的社区划分对研究复杂网络具有重要的实际意义.基于信息在网络中的扩散概率和模块度思想,本文提出了一个针对二分网络的社区划分聚类算法(IPS算法).该算法通过模拟信息在网络中扩散的过程,利用各个节点的信息量在网络中扩散后,每个节点收到其他节点的信息量作为社区之间合并的依据,并引入二分网络模块度作为社区划分优劣判断的依据.最后算法在典型网络上测试结果表明,该算法不仅能够精确的识别二分网络社区个数,而且可以获得高质量的社区划分结果.