异质信息网络中基于元路径的社团发现算法研究

实际的网络化数据往往包含多种类型的对象和关系,采用异质信息网络可以更好地对其建模,因此异质信息网络分析逐渐成为数据挖掘的研究热点。虽然同质信息网络中的社团发现已经被深入研究,但是异质信息网络中的社团发现还很少被研究。该文研究异质信息网络中的社团发现问题,提出了一个新的社团发现算法框架HCD(heterogeneous community detection)。该框架由两部分组成: 基于单条元路径的社团发现算法HCD_sgl和融合多条元路径的社团发现算法HCD_all。HCD_sgl首先确定在给定元路径下所有节点的初始标签,再利用改进的标签传递算法进行最终的社团发现;HCD_all是在HCD_sgl的基础上将基于多条元路径的社团发现结果进行融合。通过在真实数据集和人工数据集上的实验验证了HCD算法的有效性。     

异质信息网络分析与应用综述

实际系统往往由大量类型各异、彼此交互的组件构成.目前,大多数工作将这些交互系统建模为同质信息网络,并未考虑不同类型对象的复杂异质交互关系,因而造成大量信息损失.近年来,越来越多的研究者将这些交互数据建模为由不同类型节点和边构成的异质信息网络,从而利用网络中全面的结构信息和丰富的语义信息进行更精准的知识发现.特别是随着大...     

基于异质信息网络的模糊推荐算法

随着互联网信息的爆炸式增长,推荐系统扮演着越来越重要的角色。为了解决传统推荐系统存在的信息稀疏问题,并且合理表达用户的偏好,提出基于异质信息网络的模糊推荐算法(HFR)。HFR方法构建三角模糊评分模型将用户离散的评分信息模糊化,此外,还加入了项目的属性信息并使用元路径表示;在此基础上充分利用多源信息,提出了一种新的相似性度量,并预测评分获得最终的推荐结果。实验结果表明,HFR方法有效解决了信息稀疏问题,提高了推荐质量。     

基于图核的异质信息网络链路预测方法

链路预测是图挖掘主要研究的问题,其研究重点是提取图的特征信息,现有研究方法大多只关注网络拓扑结构而忽略了节点属性信息.针对该问题,提出了基于图核的链路预测方法NGLP.该方法能挖掘有效、可用的元路径;基于元路径对预测对象生成带节点属性的子图,使用子图表示被预测的链路;然后利用图核方法计算子图之间的相似性;最后训练SVM得出链路预测结果.实验结果表明,提出方法与其他方法相比具有更高的精度和更强的稳定性.     

时序图中Top-k稠密子图查询算法研究

稠密子图的查询是图分析领域的重要研究问题之一,在社交用户相关性分析、Web中社群分析等方面都有着广泛的应用.目前,关于稠密子图查询的研究工作主要基于静态图.而在实际应用中,时序信息会对稠密子图查询产生重要的影响,使得图拓扑结构随时间序列不断发生变化,包含的信息量也不断增加,使得已有的针对静态图的查找方法不再适用于时序图...     

基于注意力机制和异质信息网络元路径的推荐系统

异质信息网络（HIN）包含丰富的网络结构和语义信息使其常见于推荐系统中。然而,当前推荐系统的研究工作主要是基于元路径提供的间接信息进行推荐,而未充分利用直接交互信息。为了充分利用这些信息,提出一种融合注意力机制和异质信息网络元路径的三元交互模型（AMMRec）。在异质信息网络中使用隐式反馈矩阵构造用户相似度矩阵和项目相似度矩阵,运用异质信息网络的表示学习方法获得对应的特征向量嵌入,通过注意力机制对其进行修正;设计注意力神经网络,将不同元路径的表示向量进行融合;拼接用户嵌入、元路径嵌入和项目嵌入,通过全连接神经网络生成推荐结果。在真实数据集上的实验结果表明,AMMRec的推荐精度最高提升了9.5%。此外,AMMRec对推荐结果具有良好的可解释性。     

异质信息网络中演员合作关系的链路预测

在异质信息网络中,节点与链接的异质特性和复杂性会增加链路预测的难度。针对该问题,提出一种采用综合拓扑特征表示的链路预测方法。对不同的元路径根据异质和同质信息网络拓扑特征获得异质和同质数据,将逻辑回归模型作为链路预测模型,并综合拓扑特征进一步提高预测准确率。在异质的movielens电影数据集上进行实验,结果表明,该方法可有效提高异质信息网络演员合作关系的链路预测性能。     

基于图压缩的最大Steiner连通k核查询处理

研究了基于图压缩的最大Steiner连通k核查询处理,提出了一种支持最大Steiner连通k核查询的图压缩算法SC,证明了基于SC压缩算法的查询正确性.由于最大Steiner连通k核查询仅需要找到符合要求的连通区域,提出了图压缩算法TC,进一步将压缩图压缩为树.证明了基于压缩树的查询正确性,并提出了线性时间的无需解压缩的查询处理算法.真实和虚拟数据上的实验结果表明：压缩算法平均可将原始图压缩掉88%,且对于稠密的原始图,压缩算法的压缩效果更好,可将原始图压缩掉90%,与在原始图上直接进行查询处理相比,基于压缩图的查询处理算法效率更好,平均提升了1～2个数量级.     

多元图融合的异构信息网嵌入

基于元结构(如元路径或元图)的网络嵌入方法,能够有效地利用异构网络结构.但与元路径相比,元图能够捕获更加复杂的结构信息,更能提升异构信息网中相似节点匹配的准确性.然而,现有的基于元图的嵌入方法具有如下局限：大多由专家指定元图类型,在大型复杂网络的应用环境中并不适用;虽然融合了多个元图进行嵌入,但并未考虑元图权重的差异性;部分模型利用用户的期望语义关系生成可以保留特定语义的元图组合,但这类模型过分依赖元图选择和用于监督学习的样本,缺乏通用性.基于此,提出一种多元图融合的异构网络嵌入方法,该方法包括2部分：第1部分是元图发现,目的是挖掘代表当前网络结构和语义特征的重要元图;第2部分是基于多元图融合的节点嵌入,主要内容是提出了一种基于元图的通用节点相似度度量方法,同时利用神经网络嵌入节点的元图特征.实验结果表明,与其他网络嵌入方法相比,提出的方法具有较高的准确性和效率.     

非对称异构信息网络的模糊推荐算法

传统的协同过滤推荐算法存在普遍的数据稀疏性问题;应用于推荐算法领域的异构信息网络模型对对象的相似关系认定通常是对称的,这种对称关系的认定在实际问题的处理中存在局限性。为解决上述问题,提出一种非对称异构信息网络的模糊推荐算法。该算法利用模糊集理论在处理用户喜好程度方面的优势,从模糊的信息种获取用户的准确偏好,根据异构信息网络中元路径的丰富语义信息,获取不同角度的用户关联,在相似度计算中引入对象关系的非对称系数,对不同特征元路径的计算结果进行加权,以此提高用户之间相似关系的准确度,通过矩阵分解的方法实现评分预测。实验结果表明,该算法有效解决了数据稀疏性问题,提升了推荐精度。     

属性公平的异质信息网络上的社区搜索算法

近年来,异质信息网络上的社区搜索问题已经吸引了越来越多的关注,而且被广泛应用在图数据分析工作中.但是现有异质信息网络上的社区搜索问题都没有考虑子图上属性的公平性.将属性的公平性与异质信息网络上的kPcore挖掘问题相结合,提出了基于属性公平的异质信息网络上的极大core挖掘问题.针对该问题,首先提出了一个子图模型FkPcore.当对FkPcore进行枚举时,基础算法Basic-FkPcore遍历了所有路径实例,并枚举了大量k Pcore及其子图.为了提高算法效率,提出了Adv-FkPcore算法,以避免在枚举FkPcore时对所有的kPcore及其子图进行判断.另外,为了提高点的P＿neighbor的获取效率,提出了结合点标记的遍历方法(traversalmethod with vertex sign, TMS),并基于TMS算法提出了FkPcore枚举算法Opt-FkPcore.在异质信息网络数据集上进行的大量实验证明了所提方法的有效性和效率.     

一种异构环境下覆盖多播网络路由算法

由于IP多播在部署上的困难,覆盖多播网络(overlay multicast networks,简称OMN)作为构建通用的多播服务平台的另一可行途径正不断为人们所认可.针对实时多媒体应用对带宽需求的异构性,研讨了异构环境下OMN的路由问题.通过对度约束模型进行扩展,描述了一种新的适应异构环境的OMN网络模型.采用分层的带宽分配策略,提出了一种异构环境下构造OMN最小延时半径多播树的启发式算法--分层的压缩树(1ayered compact tree,简称LCT)算法,并对其性质进行了理论证明和分析.仿真实验结果表明,随着分配带宽的减少,LCT算法能够有效地降低多播树的高度和网络资源使用量,并保持较低的多播树延时半径增幅.     

异构重叠蜂窝网中基于业务选择的流量均衡

未来多种无线接入网必将融合成一个异构无线系统，研究如何提高整个异构系统的利用率并服务尽可能多的移动用户就有着重要的意义，本文针对异构重叠蜂窝网络提出了一种基于业务选择的流量均衡算法，该算法能够将热点小区的非实时性业务转移到负载较轻的重叠覆盖异构小区，同时还采取了一些措施来改善转移业务的服务质量．仿真结果表明，整个异构蜂窝系统各方面的性能得到了较大改善。     

异构WSNs中节点稳定匹配的覆盖空洞修复优化算法

针对异构无线传感器网络中初始节点随机部署或节点失效产生覆盖盲区的问题,提出一种节点稳定匹配的覆盖空洞修复优化算法(ROA-NSM)。首先,对静态节点进行Voronoi多边形划分确定节点覆盖盲区,通过Delaunay三角形计算虚拟修复节点位置;其次,基于距离和能量阈值函数计算节点优先级,建立虚拟修复节点与移动节点的稳定匹配关系;最后,通过移动节点位置的移动,实现覆盖空洞修复的优化。仿真实验表明,优化算法使每个虚拟修复节点有最优的移动节点匹配,通过与已有相关覆盖空洞修复算法比较,ROA-NSM优化算法收敛速度加快,匹配次数和节点移动距离减少,覆盖率提高。     

基于RSSI差分似然估计的WSN节点定位算法

为了克服接收信号强度测量误差对无线传感嚣网络(WSN)节点自身定位精度的影响.在对极大似然估计定位算法和接收信号强度指示(RSSI)模型分析的基础上,定义了个体差异差分系数、距离差分系数和距离差分定位方程,把离目标节点最近的信标节点作为参考节点对基于RSSI的测距进行差分修正,并将测距差分修正和极大似然估计相结合提出了一种测距差分修正极大似然估计定位算法.算法通过RSSI进行测距,无需增加额外硬件开销,容易实现.定位精度可达2.5 m以下,适合于处理能力和能量有限的WSN节点定位.     

面向移动对象连续k近邻查询的双层索引结构

移动对象连续k近邻（CKNN）查询是指给定一个连续移动的对象集合,对于任意一个k近邻查询q,实时计算查询q的k近邻并在查询有效时间内对查询结果进行实时更新.现实生活中,交通出行、社交网络、电子商务等领域许多基于位置的应用服务都涉及移动对象连续k近邻查询这一基础问题.已有研究工作解决连续k近邻查询问题时,大多需要通过多次迭代确定一个包含k近邻的查询范围,而每次迭代需要根据移动对象的位置计算当前查询范围内移动对象的数量,整个迭代过程的计算代价占查询代价的很大部分.为此,提出了一种基于网络索引和混合高斯函数移动对象分布密度的双重索引结构（grid GMM index,GGI）,并设计了移动对象连续k近邻增量查询算法（incremental search for continuous k nearest neighbors,IS-CKNN）.GGI索引结构的底层采用网格索引对海量移动对象进行维护,上层构建混合高斯模型模拟移动对象在二维空间中的分布.对于给定的k近邻查询q,IS-CKNN算法能够基于混合高斯模型直接确定一个包含q的k近邻的查询区域,减少了已有算法求解该区域的多次迭代过程;当移动对象和查询q位置发生变化时,进一步提出一种高效的增量查询策略,能够最大限度地利用已有查询结果减少当前查询的计算量.最后,在滴滴成都网约车数据集以及两个模拟数据集上进行大量实验,充分验证了算法的性能.     

一种无线传感器网络中的多维K-NN查询优化算法

提出了一种基于过滤器的无线传感器网络多维K-NN查询优化算法PREDICTOR.过滤器是设置在节点端的取值分布区间,用来屏蔽节点发送属于区间内的数据,从而节省节点能耗.在服务器端保存有各节点的历史样本数据,根据K-NN查询请求和样本数据的分布范围为节点定义过滤器.提出了3种优化策略:(1) 过滤器覆盖区间大小分配策略的动态调整方法,使得进入最终查询结果可能性小的节点拥有较大的覆盖区间;(2) 节点间过滤器共享方法,使得历史样本数据相近的节点使用相同的过滤器;(3) 过滤器压缩传输方法,减少为不同K-NN查询更新过滤器的代价.通过实验评价,验证了PREDICTOR算法的能量有效性,与朴素算法相比,极大地降低了数据传输量.