基于限制性随机游走局部谱近似社区发现算法

针对大型网络中社区发现优化方法的效率问题,提出一种局部社区发现方法(LRW-LSA),从少量种子节点中识别本地社区的所有潜在社区成员。采用限制性随机游走进行采样处理,从种子节点出发得到一个相对较小的子图;利用种子的归一化指示向量对子图进行Lanczos迭代,得到相关节点与目标社区的隶属概率用以恢复出目标社区。在不同领域的真实数据集和合成数据集上进行实验,结果表明,LRW-LSA优于现有的社区发现方法。

圈上的多重懒惰随机游走

本文考虑了n个定点的圈上的多重懒惰随机游走.利用偶和方法证明了其最大相遇时的期望的阶数为h_(max)×log n,其中h_(max)为圈上的一简单随机游走的最大击中时.

一种基于局部随机游走的标签传播算法

社区结构是复杂网络的重要特征之一,识别网络中不同功能的社区对理解复杂网络特性具有重要作用。基于标签传播的社区发现算法通常以节点的直接邻居作为邻域更新标签,可能无法准确发现社区结构或导致得到的社区划分结果不稳定。针对此问题,提出了一种基于局部随机游走的标签传播算法(Local Random Walk Based Label Propagation Algorithm, LRW-LPA),利用节点的k步邻域内局部重要性指标选择重要性最低的节点作为起始节点,进行带重启的局部随机游走以确定起始节点的局部邻域;选择此局部邻域范围内出现次数最多且影响值最大的标签来更新起始节点标签。LRW-LPA采用带重启的局部随机游走过程能更准确地确定节点的合适邻域范围,提高了算法的稳定性。与LPA,BGLL,Infomap, Leiden, Walktrap等经典社区发现算法在12个真实网络和12个人工构造网络上的比较实验表明,LRW-LPA算法在标准互信息(NMI)、调整兰德系数(ARI)和模块度(Q)等方面表现良好。

结合局部敏感哈希和随机游走的异常检测算法

异常检测是数据挖掘的主要研究热点问题之一。目前已存在很多异常检测的方法,但是现存的主要异常检测方法在高维数据处理过程中效率较低。为解决此问题,提出了一种高效的异常检测算法。该算法结合局部敏感哈希的性质和图的随机游走来识别异常点。具体而言,通过局部敏感哈希实现对高维数据的高效处理,随后利用数据之间距离获取其相似性,并将其转化为随机游走的转移概率。在此基础上,使用随机游走技术计算数据之间的游走概率,其中正常数据之间的转移概率越来越高,而异常点的概率越来越低,进而根据此性质最终辨别异常数据。实验结果表明,提出的方法能有效检测出数据中的异常,总体上优于其他异常检测算法。

基于局部随机游走的超像素分割方法

针对基于图论的超像素分割方法缺乏超像素紧凑性控制和运算复杂度过高的问题,提出了一种基于局部懒惰随机游走(LLRW)的超像素分割方法,并将超像素分割形式化为像素邻接图的局部划分问题,提出了一种直观的分割质量度量。该方法首先将均匀平铺的六边形重心作为超像素种子点初始位置;然后利用局部随机游走算法计算种子点与周围像素的相关程度,将其最相关种子点的标号赋予该像素;最后计算新的超像素重心,并将其作为下一轮迭代的种子点位置,通过若干次迭代逐步优化超像素分割结果。此算法具有线性的时间复杂度和线性的空间复杂度,同时超像素分割质量具有理论保证。通过标准数据集上的实验证明,该方法不仅能够较好地保持图像边界,还可以保证超像素的紧凑性,从而达到理想的超像素分割效果。

局部自适应输入控制的随机游走抠图

针对传统性抠图算法中,非完全正确用户标注及不精确超像素分割造成的信息误扩散,以随机游走算法为基础,提出带软性约束的抠图算法。通过对扩展Dirichlet问题的推导,指出带软约束的随机游走与部分自吸收随机游走概率的关联性。以吸收概率为指导,在传统相似扩散所构建的图模型上,根据局部窗口内特征矩阵的秩与方差设计了输入控制矩阵,使得信息扩散的过程能够跟随图像的局部特征进行自适应扩散。最后将软约束随机游走应用到单帧双层抠图及视频抠图中。实验表明,所提算法具有信息远距传播能力和良好的容错性能,尤其在用户标注不够充分的情况下能够取得更加优良的抠图结果。

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

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

具有步长调整策略的强制进化随机游走算法优化换热网络

强制进化随机游走算法(random walking algorithm with compulsive evolution,RWCE)是一种优化换热网络的新方法,具有程序简单、算法适应性和全局搜索能力较强等优点。本文研究了最大步长对RWCE算法优化性能的影响,提出了抛物线函数的最大步长递减调整策略来平衡RWCE算法的全局搜索与局部搜索能力。将引入策略的RWCE算法与基础算法比较,发现加入最大步长递减调整策略的RWCE算法与基础RWCE算法相比,在进化后期能够跳出局部极小值,具有更强的局部搜索能力。采用10SP2、9SP和15SP换热网络实例检验加入此策略RWCE算法的有效性,其中10SP2和9SP算例的优化结果均好于文献最好结果,相比算例原始文献下降了20.98%和1.11%。对15SP算例优化找到了新的换热网络匹配结构,并好于多数无分流换热网络优化结果,且低于文献结果 4.60%,证明了此方法在换热网络优化中具有较强的优化能力。

基于LBP纹理特征的随机游走图像分割

本文通过求解融入纹理特征信息的对称、半正定线性方程组,提出一种新的基于随机游走(Random Walker)的纹理图像分割算法。为了构造该方程组,首先通过局部二元模式(Local binary pattern,简称LBP)算子来描述纹理,将图像映射至不同纹理之间有显著区别的LBP图(LBP map)上,进而将其与梯度和几何信息结合并构造倒数型像素相似度,形成方程所需的权值矩阵,在随机游走模型下使已标号区域向未知区域传递,从而实现纹理图像分割。最后以纹理图像、噪声合成图像、MRI、CT图像为实验对象来验证算法的有效性。定性及定量实验结果表明,在多目标分割任务下,本方法有更好的有效性和精确性。

基于快速FCM聚类的自动随机游走算法在红外图像分割的应用

随机游走算法作为图论分割算法的一种,拥有分割精度高、对噪声的鲁棒性强的特点,对弱边界图像有着良好的分割效果,因此随机游走算法适用于红外图像这种边界区分弱、易受噪声干扰的图像,但是随机游走算法作为一种半自动化的图像分割算法需要人工标定种子点,这使得随机游走算法不适用于那些对实时性要求较高的场合,针对随机游走算法的这一缺陷,提出了一种基于非局部空间信息的快速模糊C均值聚类自动随机游走算法,首先使用基于非局部空间信息的快速模糊C均值聚类算法对红外图像进行预分割,再结合图像形态学为随机游走算法提供种子点,实现了红外图像的自动分割,提高了随机游走算法的实时性.该文提出的算法可以对红外图像进行自动分割,其分割效果与传统随机游走算法相当.

基于随机游走的社区发现方法综述

随机游走技术可实现准确、高效的社区发现。为总结分析基于随机游走的社区发现方法,将随机游走技术细分为个性化网页排名方法、热核扩散方法和其他随机游走方法,将社区发现问题分为局部社区发现和全局社区结构识别两类任务。详细综述了不同类型的随机游走技术及其在2种社区发现任务中的应用方式,并分析了现有方法存在的问题,对未来研究方向进行了展望。最后,针对不同社区发现任务从相似性标准与结构性标准两方面总结了社区发现准确性的评价指标,为相关研究提供便利。

基于自适应t分布与随机游走的麻雀搜索算法

针对麻雀搜索算法在解决复杂问题时存在的收敛精度降低以及陷入局部最优等问题,文中提出了一种基于自适应t分布与随机游走的麻雀搜索算法。该算法在初始化过程中使用反向学习来生成反向解,从中选择优秀的个体组成初始化种群。在原始麻雀搜索算法上采用自适应t分布策略和高斯随机游走策略可以提高麻雀个体的寻优能力,同时防止算法早熟。仿真结果表明,相较于对比算法,文中所提算法的收敛精度和收敛速度都有所提升。

一种叠加随机游走重力模型的链路预测算法

基于局部随机游走的链路预测算法忽略网络结构对转移概率的影响,不适用于具有局部高聚集程度的网络,因此提出叠加随机游走重力模型的链路预测算法。结合局部信息重定义随机游走的转移概率矩阵,将其应用到叠加随机游走中,量化局部网络结构对游走转移的影响,利用叠加随机游走得到的转移概率重定义重力模型参数,计算节点之间的相似性。与基于局部信息、路径、随机游走和节点聚类系数的算法相比,在局部无高聚集程度的网络中,新算法的AUC指标平均为0.951,提高了1.3%,Precision指标提高了0.9%;在具有局部高聚集程度的网络中,新算法的AUC指标平均为0.978,提高了5.5%,Precision指标提高了1.4%。

一种基于随机游走模型的融合视觉单词共现性的软分配词袋技术

提取局部兴趣点并通过词袋技术表征图片,是进行图片检索的一种经典方案。在传统的词袋技术中,每一个局部兴趣点的分配都是相互独立的,而没有考虑相邻局部兴趣点分配的相互影响。这样可能会导致某些局部兴趣点不可靠的分配,从而降低图片检索的精确度。通过统计视觉单词的共现性,可以学习到一些有价值的先验知识;同时利用随机游走模型,将视觉单词的共现性融合到传统的软分配词袋技术中,从整体上减少局部兴趣点不可靠的分配,进而提升图片检索的精确度。

随机游走的布谷鸟搜索算法

布谷鸟搜索(Cuckoo Search,CS)算法是一种简单方便的仿生群优化算法。它虽然具有明显的优点,但在处理高维复杂问题时,不能收敛到最优解。针对算法后期收敛速度降低、易陷入局部最优的问题,本文在布谷鸟搜索算法中加入偏好随机游走机制,使得算法不容易陷入局部最优,还改变了发现概率pa的值来提高算法的各种性能。对单目标基准函数进行仿真测试,仿真结果表明,优化后的算法可以有效地提高布谷鸟算法的寻优能力。

基于用户影响力游走模型的社会化推荐算法

社会化推荐在一定程度上缓解了推荐中的数据稀疏性问题,但是通常仅考虑了社交网络中用户间的局部影响关系。综合考虑用户的局部影响力和全局影响力,提出了基于用户影响力游走模型的社会化推荐算法,该算法根据用户信任关系和历史行为分析用户的局部影响力,通过评估用户的评分质量研究用户的全局影响力,然后将二者有机结合计算随机游走模型中各节点之间的转移概率。通过与以往的算法在均方根误差、覆盖率和F-Measure等指标的实验结果表明,提出的算法在一定程度上提高了推荐的性能。

一种微电网优化配置的随机游走算法

针对独立型微电网配置优化问题,建立一种以能流匹配形式描述的风-光-柴-储优化模型,形成表示各时刻设备出力的节点连接关系。鉴于群智能算法应用于微电网优化配置问题易早熟收敛的特点,提出适用于微电网优化配置的随机游走优化算法,算法以降低系统年综合费用为导向,通过随机增大或减小设备逐时出力,实现连续变量(设备出力)和整型变量(设备数量)同步优化,通过接受差解机制,使算法具有跳出局部最优解的能力,更好兼顾微电网容量优化过程中的全局搜索与局部搜索。将随机游走算法应用到算例进行仿真,得到年综合费用为552826.39元,与粒子群优化算法进行对比,结果更好,验证了算法在优化质量上的优越性。

融合边界连通性与局部对比性的图像显著性检测

本文提出了一种融合边界连通性与局部对比性的图像显著性检测算法.首先,构造包围前景区域的凸包并利用K-means聚类算法,增强凸包内前景区域,抑制背景区域.为获取更加准确的前景概率,建立超像素图模型并结合随机游走模型计算超像素显著值,再利用聚类内显著值传播计算超像素前景概率.然后,利用边界连通性计算超像素背景概率.最后,融合前景概率与背景概率计算超像素最后的显著值.而且,为克服单一显著性检测算法的局限性,在DS证据理论的基础上,设计了一种新的融合算法.实验结果表明:在DUT-OMRON、ECSSD、MSRA10K三个公开数据集上,提出的算法得到的显著图更接近于真值图,且在准确率-召回率曲线、F-measure值以及平均绝对误差值三个评估指标上均优于其他12种经典显著性检测算法获取的结果.

基于懒惰随机游走的雾天含噪图像清晰化

针对现有单幅图像清晰化算法无法很好地保证去雾和降噪效果的问题,提出了一种在懒惰随机游走模型下的单幅雾天含噪图像清晰化算法。分析了现有大气散射模型的物理意义,并对其加以改进,使之更符合实际雾天含噪图像的特殊性,利用懒惰随机游走模型估计改进雾天退化模型的衰减项;利用几何约束和color-line先验获取精准的退化模型中的大气光,最后恢复出噪声水平低的无雾图像。实验结果表明,所提算法在获得最佳去雾效果和抑制噪声水平的同时,具有较强的稳健性。

一种大规模异质信息网络中的局部社区发现算法

社区结构是复杂网络中的重要研究领域,也是复杂网络的重要特征之一,网络中的社区结构发现在理解网络功能方面有着重大意义。给定一个大规模异质信息网络,局部社区发现的目标是找到一个包含查询结点的同质社区,并最大化或最小化一种度量。本文研究了异质信息网络中的局部社区发现算法,提出了一个新的局部社区发现算法框架(Heterogeneous Local Community Detection)HLCD。该框架主要采用了基于元路径的相似性度量算法HeteSim,来测量与查询结点类型相同的结点之间的相似性,通过随机游走给各个结点赋予权值,并用这些结点权值及结点之间的相似性来重新建图,最后在新图中找到局部社区。