基于SVM与DOM重心半径模型的Web正文提取

为了从网页中精确地提取正文内容,提出一种基于支持向量机(SVM)与DOM重心半径模型的算法。通过SVM对网页DOM节点集进行提取,得出文本块节点。根据网页链接信息和初次提取的文本块节点计算重心半径,利用重心半径模型进行二次精确提取,并给出相应的公式推导和超参数选取过程。实验结果表明,与统计抽取、FFT抽取等算法相比,该算法的准确率和提取效率较高,泛化能力较好。     

一种网页分类中基于图的半指导学习算法*

提出一种基于图的半指导学习算法用于网页分类.采用k近邻算法构建一个带权图,图中节点为已标志或未标志的网页,连接边的权重表示类的传播概率,将网页分类问题形式化为图中类的概率传播.为有效利用图中未标志节点辅助分类,结合网页的内容信息和链接信息计算网页间的链接权重,通过已标志节点,类别信息以一定概率从已标志节点推向未标志节点.实验表明,本文提出的算法能有效改进网页分类结果.     

基于图刚性的无线传感器网络定位新算法

针对分布式 MDS-MAP 算法的不足,提出了一种基于图刚性理论的无线传感器定位新算法 MDS-MAP (GR)。算法利用图的刚性理论,确定网络中的所有刚性子区域,然后利用合并定理将刚性子区域进行扩展,最后对合并得到的刚性区域利用 MDS-MAP 算法和锚节点实现网络中节点的大规模定位。算法尽可能对刚性区域进行合并,节省了执行 MDS-MAP 算法的次数,提高了执行效率。通过在不同拓扑结构的无线传感器网络中进行了仿真实验,说明了提出的算法能有效定位不同半径下网络中90%以上的节点,另外,新方法比现有方法在定位成功率上提高了4%～5%,并且定位精度提高了2%～3．5%左右。算法适用于大规模无线传感器网络中的快速定位。     

基于二邻居图的无线传感器网络边缘检测算法

针对传统边缘检测算法未考虑边缘宽度的问题,提出了一种基于二邻居图的无线传感器网络边缘检测算法,通过调节节点通信半径得到合适的边缘宽度。该算法不需要任何节点位置信息,仅通过分析二邻居图的拓扑连通性来判断边缘节点。仿真结果表明,该算法能够准确检测出边缘节点,对于分布稀疏、节点密度较低的局部边缘同样适用,能够应用于无线传感器覆盖质量、连通性和能量管理等,有效延长了网络生命期。     

Torus连接Petersen图互连网络及路由算法

可扩展性和短直径是设计大规模并行计算机系统互连网络的两个重要因素.基于Petersen图的短直径和正规性和Torus拓扑结构的可扩展性,提出了一种新的互连网络拓扑结构,称为Torus连接Petersen图互连网络.该互连网络拓扑结构具有短直径、正规性、对称性和良好的扩展性.网络节点采用混合编码方法,使得路由算法设计简单.分别设计了基于混合编码的单播、广播路由算法.分析表明提出的互连网络具有较好的拓扑性质.     

基于局部语义的网页净化算法

网页净化算法的目的是除去影响搜索引擎获取网页主题的噪音.本文提出一种基于局部语义的网页净化算法.算法遍历转化成DOM树后的网页,通过计算相邻节点的相似度,确定局部语义节点范围,然后提取局部语义信息,建立局部语义树模型,最后除去与网页主体的相关性低于预定阈值的局部语义节点,达到网页净化的目的.实验表明算法是有效的.     

基于DOM状态转换的隐网页信息抽取算法

由于网页大量包含动态Java Script脚本,造成大部分网页内容对传统的网页爬虫不可见。为此,提出一种基于DOM状态转换的隐网页信息抽取算法。该算法增量地构建DOM状态转换机,以DOM节点及其点击事件作为状态机的输入事件。对能够引起目标节点变化的转换路径进行递归搜索;通过重放点击路径,自动完成目标节点的内容抓取;通过覆盖监听器方法原型,获取DOM树中所有可点击的节点作为候选节点。该算法应用RTDM算法和自定义过滤器来对DOM状态空间进行压缩,以缩减搜索空间,定义DOM树中候选节点到目标节点的距离作为h打分,进行启发式搜索。实验表明,所研究算法性能优良,对隐网页内容的抽取准确率达到89.48%,可应用在网页自动化测试、网页爬虫等领域。     

基于MapReduce的图结构聚类算法

图结构聚类（SCAN）是一种著名的基于密度的图聚类算法。该算法不仅能够找到图中的聚类结构,而且还能发现图中的Hub节点和离群节点。然而,随着图数据规模越来越大,传统的SCAN算法的复杂度为O（m^1.5）（m为图中边的条数）,因此很难处理大规模的图数据。为了解决SCAN算法的可扩展性问题,本文提出了一种新颖的基于MapReduce的海量图结构聚类算法MRSCAN。具体地,我们提出了一种计算核心节点,以及两种合并聚类的MapReduce算法。最后,在多个真实的大规模图数据集上进行实验测试,实验结果验证了算法的准确性、有效性,以及可扩展性。     

融合结构与属性相似性的加权图聚集算法

图聚集技术是将一个大规模图用简洁的小规模图来表示,同时保留原始图的结构和属性信息的技术。现有算法未同时考虑节点的属性信息与边的权重信息,导致图聚集后与原始图存在较大差异。因此,提出一种同时考虑节点属性信息与边权重信息的图聚集算法,使得聚集图既保留了节点属性相似度又保留了边权重信息。该算法首先定义了闭邻域结构相似度,通过一种剪枝策略来计算节点之间的结构相似度;其次使用最小哈希(MinHash)技术计算节点之间的属性相似度,并调节结构相似与属性相似所占的比例;最后,根据2方面相似度的大小对加权图进行聚集。实验表明了该算法可行且有效。     

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

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

用于大数据分类的快速隐层优化分布式极限学习机

针对大数据分类问题应用设计了一种快速隐层优化方法来解决分布式超限学习机（Extreme Learning Machine,ELM）在训练过程中存在的突出问题--需要独立重复运行多次才能优化隐层结点个数或模型泛化性能。在不增加算法时间复杂度的前提下,新算法能同时训练多个ELM隐层网络,全面兼顾模型泛化能力和隐层结点个数的优化,并通过分布式计算避免大量重复计算。同时,在算法求解过程中通过这种方式能更精确、更直观地学习隐含层结点个数变化带来的影响。比较多种类型标准测试函数的实验结果,相对于分布式ELM,新算法在求解精度、泛化能力、稳定性上大大提高。     

基于参考节点嵌入的图可达性查询

针对k步可达性查询算法无法解决带距离约束的图可达性查询问题,提出基于参考节点嵌入的图可达性查询算法。首先,从所有节点中选出极少数有代表性的全局参考节点,预先计算所有节点与全局参考节点之间的最短路径距离;然后,采用最短路径树和范围最小值查询技术求得局部参考节点;接着,利用三角不等式关系得到查询点对距离范围;最后,根据查询条件中的距离值与查询点对距离范围上、下限值的大小关系,可快速得出可达性结论。针对社会关系网络和公路网络数据,将所提算法与Dijkstra算法、K-Reach算法进行实验对比测试。相较于K-Reach算法,其索引建立时间小4个数量级,其索引规模小2个数量级;相较于Dijkstra算法,在公路网络和社会关系网络中,直接得出可达性结论的比例分别为92%和78.6%,其查询时间大大缩短,分别降低了95.5%和92%。实验结果表明：所提算法能够通过使用较小的索引开销,实现在线查询计算复杂度的降低,可很好地解决既适用于有权图又适用于无权图带距离约束的可达性查询问题。     

基于链接重要性和数据场的链接预测算法

针对现有基于节点相似性的链接预测方法忽略了网络拓扑本身链接强度的信息,带权的拓扑路径方法中权值较难确定等缺陷,提出一种基于链接重要性和数据场的链接预测算法。首先,将所有链接边赋予不同的链接权重;其次,考虑潜在链接节点间的相互影响,对部分没有链接的节点进行链接预估计;最后,利用数据场势函数计算两节点间的相似值。在典型的网络数据进行的实验结果表明,所提方法在分类指标和推荐指标中都有很好的表现：以AUC为评价指标时,比同复杂度的局部路径（LP）算法提高了3到6个百分点;以DCG为评价指标时比LP算法提高了1.5到2.5个DCG值。算法整体上提高了预测准确性,且由于参数确定简单,复杂度又不高,在实际中易于部署。     

一种基于TextRank的单文本关键字提取算法

作为一种经典的文本关键字提取和自动生成算法,TextRank将文本看作若干单词组成的集合,并通过对单词节点图的节点权值进行迭代计算,挖掘单词之间的潜在语义关系。在TextRank节点图模型的基础上,将马尔可夫状态转移模型与节点图相结合,提出节点间边权为条件概率的新模型生成算法TextRank_Revised。通过对有标记和无标记的验证集进行验证,证明新的算法在不提升时间复杂度的前提下,通过计算单文本得出的单词排序结果相较于原TextRank算法更加吻合人工对文档的关键字提取结果。     

基于FP-Growth的图上随机游走推荐方法

推荐是促进诸如社交网络等应用活跃度的重要模式,但 庞大 的节点规模以及复杂的节点间关系给社交网络的推荐问题带来了挑战。随机游走是一种能够有效解决这类推荐问题的策略,但传统的随机游走算法没有充分考虑相邻节点间影响力的差异。提出一种基于FP-Growth的图上随机游走推荐方法,其基于社交网络的图结构,引入FP-Growth算法来挖掘相邻节点之间的频繁度,在此基础上构造转移概率矩阵来进行随机游走计算,最后得到好友重要程度排名并做出推荐。该方法既保留了随机游走方法能有效缓解数据稀疏性等特性,又权衡了不同节点连接关系的差异性。实验结果表明,提出的方法比传统随机游走算法的推荐性能更佳。     

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

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

过必经结点集的选择性排序算法

目前研究经过必经结点集的最短路径算法多数是针对不允许存在回路的情况,少数针对存在回路的传统算法时间复杂度相对偏高。对此通过探索最优路径形成的规律,将含有大量结点的图转化为含有少量结点的图,用选择性排序法尽量少地生成路径序列分支,对这些分支进行筛选从而得到最短路径。实验结果表明,在面对数目较多的必经结点时,该算法性能将优于传统算法。     

GPPR: Geo-distributed Personalized PageRank Algorithm

Personalized PageRank, as a basic algorithm in large graph analysis, has a wide range of applications in search engines, social recommendation, community detection, and other fields and it has been a hot problem of interest to researchers. The existing distributed personalized PageRank algorithms assume that all data are located in the same geographic location and the network environment is the same among the computing nodes where the data are located. However, in the real world, these data may be distributed in multiple data centers across continents, and these geo-distributed data centers are connected to each other through WANs, which are characterized by heterogeneous network bandwidth, huge hardware differences, and high communication costs. Moreover, the distributed personalized PageRank algorithm requires multiple iterations and random walk on the global graph. Therefore, the existing distributed personalized PageRank algorithms are not applicable to the geo-distributed environment. To address this problem, the GPPR (Geo-distributed Personalized PageRank) algorithm is proposed in this paper. The algorithm first preprocesses the big graph data in the geo-distributed environment and maps the graph data by using a heuristic algorithm to reduce the impact of network bandwidth heterogeneity on the iteration speed of the algorithm. Secondly, GPPR improves the random walk approach and proposes a probability-based push algorithm to further lower the number of iterations required by the algorithm by reducing the bandwidth load of data transmission between working nodes. We implement the GPPR algorithm based on the Spark framework and build a real geo-distributed environment in AliCloud to conduct experiments comparing the GPPR algorithm with several existing representative distributed personalized PageRank algorithms on eight open-source big graph datasets. The results show that the communication data volume of GPPR is reduced by 30% on average in the geo-distributed environment compared with that of other algorithms. In terms of algorithm running efficiency, GPPR improves by an average 2.5 factor compared with other algorithms.     

基于压缩的大规模图的割点求解算法

割点求解是图应用中的一个重要操作.深度优先搜索树算法可以解决割点求解问题.但是该算法存在缺点,导致它不能在实际问题中得到很好的应用.这是因为当今数据的两大特点,一是数据规模庞大,对于很多图操作提出了挑战性的要求;二是数据多变,每天数据的大量更新使得传统算法必须依据更新重复计算,浪费了时间和空间.深度优先搜索树算法的时间复杂度为O(|V|+|E|),其中,|V|和|E|分别为图的顶点的数目和边的数目.它能够很好地适应第1个特点,但是对于第2个特点该算法则无能为力.提出一种基于压缩的割点求解算法来解决这个问题.该算法通过点的朴素相似来压缩图,时间复杂度为O(|E|).在得到的无损压缩图上进行割点求解,同时在压缩图上动态地维护点和边的更新,在不解压图的情况下完成图的更新,在更新后的图上进行割点求解,极大地降低了时间和空间消耗.该压缩算法得到的压缩图对其他图操作同样适用.     

基于因子图和联合消息传递的无线网络协作定位算法

针对现有基于消息传递算法的无线网络节点定位算法复杂度和通信开销过高的问题,提出一种基于测距的、低复杂度低协作开销的联合消息传递节点定位算法。所提算法考虑参考节点位置的不确定性以减少误差累积,并将消息约束为高斯函数以降低通信开销。首先,根据系统的概率模型和因子分解设计因子图;然后,根据状态转移模型和测距模型的特点,分别使用置信传播和平均场方法计算预测消息和协作消息;最后,在每次迭代过程中,通过非线性项的泰勒展开将非高斯置信消息近似为高斯函数。仿真分析表明,所提算法的定位性能与基于粒子的SPAWN算法接近,但节点间传输的信息由大量粒子变为均值向量和协方差矩阵,同时计算复杂度也大幅降低。