一种基于相对熵的随机游走相似性度量模型

针对基于随机游走的节点相似性度量模型中存在的大度节点依赖问题,从信息论的角度提出了一种改进的随机游走节点相似性度量方法:基于相对熵的随机游走相似性度量方法RE model(A random walk similarity measure model based on Relative Entropy).首先根据随机游走模型得到网络中节点的转移概率向量,再计算两个节点转移概率向量的相对熵得到该节点对的相似性.由于转移概率向量给出了从一个特定节点出发经过多步随机游走后到达网络其他所有节点的概率,导致网络中的每个节点在计算相对熵的过程中都被等同看待,并且网络规模的增大会使计算得到的节点间相似性耗时更多且存在较大偏差.根据节点经过多步随机游走后到达网络中影响力较大的节点的转移概率来构造该节点的转移概率分布,计算两个节点的转移概率分布的相对熵以得到网络中节点对之间的差异分数,进而得到网络节点间的相似性矩阵.RE model度量方法降低了传统随机游走相似性度量对于大度节点的依赖性.通过在真实网络数据集上的实验表明,RE model算法在对称性、网络传播及社区发现等方面表现良好.

基于随机游走相似度矩阵的改进标签传播算法

基于标签传播的社区发现算法因其时间效率高而得到广泛关注。针对该算法因标签传播的随机性导致其社区划分准确度难以保证的问题,提出一种基于随机游走的改进算法。首先,引入随机游走思想,计算得到一种衡量网络节点间相似度的矩阵;其次,在标签传播过程中,当邻居节点中标签出现频率存在多个最高时,不是随机选择一个,而是选择相似度最高的邻居节点所拥有的标签来更新,避免了标签在社区之间的任意传播;最后,用不同的真实网络进行测试,结果表明在社区发现中该算法比原始标签传播算法取得更好的表现。

结合信任和相似度的随机游走推荐算法

针对稀疏性和冷启动问题,提出一种结合信任和相似度的随机游走算法,利用两者的综合权重TS,应用于随机游走算法。实验结果表明,在全用户数据集和冷启动数据集中,算法比其他参照算法在准确率和覆盖率等方面均有提高,时间复杂度也有改善。本文的信任度采用数据集内用户评价的信任度,并没有采用信任度公式计算用户对其他用户的信任度。提出的算法改善了推荐精确度、覆盖率,优化了推荐质量。

基于用户相似度的随机游走社交网络事件推荐算法

针对基于社交网络的事件推荐覆盖性和准确性不够高的问题,提出了基于用户相似度Si-user Walker算法.该算法利用基于事件的社交网络特征,将线上用户群组数据抽象为图,以重启随机游走算法为基础,改变了传统的完全基于图的拓扑结构进行随机游走的策略.根据地理位置划分事件类型,提出了新的用户相似度计算方法,然后根据用户相似度矩阵作为随机游走的转移概率,既保留了图的传递性,又保证了图节点游走的真实性.与其他推荐算法在真实的数据集上实验表明,该算法在均方根误差、准确率及覆盖率上均得到提升.

融合相似度图和随机游走模型的多标签短文本分类算法

提出一种融合相似度图和随机游走模型的多标签短文本分类算法。首先,以样本数据和标签为节点创建相似度图,借助外部知识库计算样本与标签之间的权重,得到预测样本与标签集合之间的匹配度。然后,将多标签数据映射成多标签依赖图,在图上进行重启随机游走,并将已获得的匹配度作为初始预测值,计算每个节点的概率分布,直到概率分布趋于稳定时,节点的概率分布即为标签的概率分布,进而确定预测文本的标签集。实验结果表明,本文提出的算法有较好的多标签文本分类性能,与同类算法相比较,分类性能显著提升。

基于随机游走与最优匹配的装配体相似性分析

为了提高利用拓扑信息进行装配体检索的能力,提出一种基于随机游走和最优匹配的相似性分析方法.首先用图节点表示装配体中的零件,将装配体转化为属性连接图并进行简化;然后分析零件连接装配关系的紧密程度并构建转移概率矩阵,利用随机游走模型分析各零件的拓扑特征;最后依据拓扑和属性特征进行零件的两两相似性评价,建立对比装配体的二分图并用最优匹配获得装配体的整体相似性.实例验证了文中方法是正确和有效的.

基于逆向游走的PageRank社交网络影响力度量算法

随着社交网络的发展,其节点影响力度量成为一个重要的研究领域。针对传统随机游走PageRank算法精确度不高的问题,提出一种逆向随机游走PageRank算法,该算法采用逆向查找消息传播源的思想,对网络中的每条有向边以概率ε进行逆向随机游走,通过迭代计算出每个节点的PageRank值。实验表明,本文提出的算法较传统的随机游走PageRank算法具有更好的稳定性,并在迭代次数较少时也能保持较高精度。

基于用户兴趣度的改进二部图随机游走推荐方法

传统的二部图随机游走算法主要采用基于共同项目的相似度计算,并且项目之间、用户之间的影响程度是对称的,这种对称信息不能体现用户兴趣,推荐精度不高。为了提高推荐准确性,提出一种基于用户兴趣度的二部图随机游走方法。采用共同项目和用户打分项目数量的共同性质体现用户兴趣度,分析信息的不对称性,并在二部图中随机游走。实验表明,基于用户兴趣度的二部图随机游走算法提高了预测准确率和命中率。

基于叠加随机游走的复杂网络节点重要度评估方法

针对现有节点重要度评估方法排序结果不精确的缺点,提出一种基于叠加随机游走的评估方法。首先引入随机游走算法并进行叠加改进,计算得到节点间的相似度矩阵;其次提出相似和的概念,用以表征节点的重要度,相似和越高,表明其与越多的节点有更高的相似度,相对而言重要度越高;最后对相似和进行排序,得到网络中节点的重要度排序。实验证明,该方法能以较高的精度评估网络节点的重要度,获取网络中的关键节点。

属性网络中相似性增强随机游走的多社区搜索

社区搜索旨在寻找与给定查询节点高度相关的个性化社区.现有社区搜索方法多面向简单网络且处理单个查询节点或假定多个查询节点来自同一社区,这种严格的假设使得算法灵活性受限.据此,提出一种在属性网络中利用查询节点随机游走路径的相似性增强的多社区搜索方法,可以有效地定位查询节点所属的多个局部目标社区.具体地,有效融合网络中高阶结构与属性信息,利用重启随机游走计算各查询节点的重要性分数向量;计算查询节点随机游走路径的相似性并设计一种相似性增强策略,使得在无监督学习中相似路径游走者彼此增强关联从而定位不同查询节点所属的多个社区结构;基于结合结构和属性的并行电导值精准查询社区.真实数据集和人工数据集的实验验证了本文方法的有效性和效率.

基于网络表示学习与随机游走的链路预测算法

现有的基于随机游走链路预测指标在无权网络上的转移过程存在较强随机性,没有考虑在网络结构上不同邻居节点间的相似性对转移概率的作用。针对此问题,提出一种基于网络表示学习与随机游走的链路预测算法。首先,通过基于深度学习的网络表示学习算法——Deep Walk学习网络节点的潜在结构特征,将网络中的各节点表征到低维向量空间;然后,在重启随机游走(RWR)和局部随机游走(LRW)算法的随机游走过程中融合各邻居节点在向量空间上的相似性,重新定义出邻居节点间的转移概率;最后,在5个真实数据集上进行大量实验验证。实验结果表明:相比8种具有代表性的基于网络结构的链路预测基准算法,所提算法链路预测结果的AUC值均有提升,最高达3.34%。

信息网络中一个有效的基于链接的结点相似度度量

信息网络无处不在.通过把网络中的对象抽象为点,把对象之间的关系刻画为边,相应的信息网络就可以用图来表示.图中结点相似度计算是图数据管理中的基本问题,在很多领域都有运用,比如社会网络分析、信息检索和推荐系统等.其中,著名的相似度度量是以Personalized Page Rank和Sim Rank为代表.这两种度量本质都是以图中的路径来定义,然而它们侧重的路径截然不同.为此,提出了一个度量Super Sim Rank.它不仅涵盖了这些路径,而且考虑了Personalized Page Rank和Sim Rank两者都没有考虑的路径,从而能够更加体现出这种链接关系的本质.在此基础上对Super Sim Rank进行了理论分析,从而提出了相应的优化算法,使得计算性能从最坏情况O(kn4)提高到O(knl).这里,k是迭代次数,n是结点数,l是边数.最后,通过实验验证了Super Sim Rank优于Sim Rank和Personalized Page Rank,同时验证了优化算法在各种情况下都是有效的.

基于随机游走的语义重叠社区发现算法

语义社会网络是由信息节点及社会关系构成的一类新型复杂网络,因此语义社会网络重叠社区发现是传统社区发现研究的新方向.针对这一问题,提出基于随机游走的语义社会网络重叠社区发现算法,该算法首先以LDA(latent Dirichlet allocation)算法为基础建立语义空间,实现节点语义信息到语义空间的量化映射;其次,以语义空间中节点信息熵作为节点语义信息比重,以节点的度分布比率作为节点关系比重,建立节点语义影响力模型及语义社会网络的加权邻接矩阵;再次,以语义影响力模型和加权邻接矩阵为参数,提出一种改进的语义社会网络重叠社区发现的随机游走策略,并提出可度量语义社区发现结果的语义模块度模型;最后,通过实验分析,验证了所提出的算法及语义模块度模型的有效性和可行性.

基于混合图上随机游走的视觉注意显著目标检测模型

目前的视觉显著性检测算法,主要依赖像素间的对比,缺乏从全局角度对显著目标进行分析理解。根据生物视觉注意机制,显著目标通常是显眼、紧凑和完整的,提出一种基于混合图上随机游走的显著目标检测算法,将视觉显著性检测公式化为马尔科夫随机游走问题。首先将输入图像进行分块,利用颜色特征距离和方向的空间分布和方向熵对比分别确定无向图和有向图的边权重,进而得到混合图;然后通过全连通图搜索提取全局特性,突出全局较孤立的区域;同时通过k-regular图搜索提取局部特性,增强局部较均匀的区域;最后结合全局特性和局部特性得到输入图像的显著图,从而确定感兴趣区域位置。实验结果表明,相比于其他两种具有代表性的算法,所提算法检测结果更加准确、合理,证明该方法合理可行。

基于组合类别空间的随机游走推荐算法

传统的类别驱动方法只考虑类别间的关联或是将其组织成扁平或层次结构,而项目和类别对应关系复杂,其他信息容易被忽略。针对这个问题提出基于组合类别空间的随机游走推荐算法,更好地组织了项目类别信息、缓解了数据稀疏。首先,建立一个用哈斯图表示的项目组合类别空间,将项目和类别复杂的一对多关系映射成一对一的简单关系,并表示用户上下层次、同层次及跨层次的项目类别间的跳转;接着,定义组合类别空间的语义关系及链接、偏好两种语义距离,更好地定性、定量描述用户动态偏好的变化;然后,结合组合类别空间上用户浏览图的语义关系、语义距离、用户行为跳转、跳转次数、时序、评分等各种信息,利用随机游走建立用户个性化类别偏好模型;最后,根据用户个性化偏好完成基于用户的协同过滤项目推荐。在MovieLens数据集上的实验显示,与基于用户的协同过滤(UCF)、基于类别关联的推荐模型(UBGC和GENC)相比,所提算法推荐的F1-score提高了6～9个百分点,平均绝对误差(MAE)减小了20%～30%;与基于类别层次潜在因子模型(CHLF)相比,所提算法推荐的F1-score提高了10%。实验结果表明,所提算法在排序推荐上优于传统基于类别的推荐算法。

一种基于随机游走算法的复杂网络生成

为了更好地研究复杂网络结构,采用随机游走算法实现复杂网络的生成。该算法采用扩散策略实现网络生成,根据活跃标签标注下一次抽取与前一次抽取的联系,除第一个节点之外的所有网络节点的加入均由网络节点属性决定,以最大转移概率为准则来实现下一个节点的选择,有效避免局部陷入与遍历不全的不足。实验证明,相比于传统的复杂网络生成方法,该算法能更好地反映复杂网络的原始网络结构,网络连通性好,度分布和聚类系数与原始网络更相似,网络层次性更强。

基于随机游走模型和KL-divergence的聚类算法

聚类分析在数据挖掘领域有着广泛的应用,该文提出一个聚类新思路,它不需要任何参数的假设,只基于数据两两之间的相似性。该方法假设数据点之间存在随机游走关系,根据数据相似性构造随机游走过程的转移矩阵,当随机游走过程进入收敛期后,t阶转移矩阵揭示了数据点的分布。用迭代方法寻找最小的KL-divergence来对这些分布聚类。该方法具有严谨的概率理论基础,避免了传统算法需要参数假设、限于局部最优等不足。实验表明,该算法具有较优的聚类效果。

一种结合随机游走和粗糙决策的文本分类方法

情感分析一直是社交媒体领域所研究的热点,为克服有些情感词语在文本中模糊性强的问题,本文引入了两个模型.随机游走模型在互联网分析及页面排序中有了一些成熟的应用,但在文本倾向性分析中少有涉及.文中提出基于扩展随机游走模型的情感词极性判别算法,对模糊性词语的情感词极性进行分析,通过建立文本向量空间,提出基于情感词极性权重序的属性离散化算法,对候选属性进行离散化处理.最后通过粗糙决策置信度模型,对文本最终情感类别进行判定.实验通过词极性判别、离散化、粗糙决策置信分类三个阶段,把各阶段得到的结果与其他方法进行对比,最后通过多种评价指标对情感分类的最终分类结果进行评判,实验结果证明了方法的有效性.

改进的基于信任网络和随机游走策略的评分预测模型

为了提高推荐算法评分预测的准确度,该文在Trust Walker模型的基础上,提出了一个改进的基于信任网络和随机游走策略的评分预测模型——Referential User Walker模型。该模型通过随机游走策略,利用信任网络中的信任朋友对目标物品或与目标物品相似的物品的评分进行评分预测,并在信任网络中找到最可信的Top N评分参考用户,同时引入信任度权重,降低了噪声数据的影响。实验结果表明,与Trust Walker模型相比,Referential User Walker模型的评分预测准确度有所提高。

利用2-hop随机游走进行异质网络社区发现

针对异质社交网络社区识别问题,提出一种基于随机游走层次社区识别算法。提出异质网络层级吸引力度量函数,构建异质网络随机游走模型;设计了一种基于2-hop互随机游走的异质网络节点相似性度量函数;通过将该相似性函数推广到层次聚类并设计相应的相似矩阵校准方案,异质社区识别任务可以在较短的时间内迭代完成。人工合成网络和真实网络上的仿真实验验证了算法的可行性和有效性。