1.本公开涉及计算机
技术领域：
：，具体涉及数据挖掘、图模型构建、相似度计算、智能推荐等
技术领域：
：，可应用于广告投放、信息推荐等场景，尤其涉及一种确定节点相似度的方法、装置、电子设备及存储介质。
背景技术：
：：2.目前，在广告投放、信息推荐等诸多领域中，可以通过计算节点之间的相似度，来获取与某个节点类似的节点。例如，节点可以是用户搜索的关键词、需要投放的广告、又或者期望推荐的短视频等。3.但是，目前计算节点之间的相似度的方法速度较慢，计算过程需要消耗大量的资源。技术实现要素：4.本公开提供了一种确定节点相似度的方法、装置、电子设备及存储介质，能够提高计算节点之间的相似度的速度，减少计算过程所消耗的资源。5.根据本公开的第一方面，提供了一种确定节点相似度的方法，所述方法包括：6.根据多个节点之间的关联关系，确定每个节点在最大游走长度内到达多个节点中的其他节点、以及所述节点到所述其他节点的概率；对第一节点和第二节点，根据第一节点和第二节点分别在最大游走长度内能够到达的最长路径，确定第一节点和第二节点在不同步伐内能够相遇的相遇节点；所述第一节点和所述第二节点为所述多个节点中的任意两个节点；对第一节点和第二节点在每一步伐内能够相遇的相遇节点，获取第一节点到达相遇节点的概率和第二节点到达相遇节点的概率之间的乘积，得到相遇节点对应的概率乘积结果；根据第一节点和第二节点在每一步伐内能够相遇的相遇节点对应的概率乘积结果，确定第一节点和第二节点之间的相似度。7.根据本公开的第二方面，提供了一种确定节点相似度的装置，所述装置包括：8.概率确定单元，用于根据多个节点之间的关联关系，确定每个所述节点在最大游走长度内到达所述多个节点中的其他节点、以及所述节点到所述其他节点的概率。9.相遇节点确定单元，用于对第一节点和第二节点，根据所述第一节点和所述第二节点分别在所述最大游走长度内能够到达的最长路径，确定所述第一节点和所述第二节点在不同步伐内能够相遇的相遇节点；所述第一节点和所述第二节点为所述多个节点中的任意两个节点。10.相似度确定单元，用于对所述第一节点和所述第二节点在每一步伐内能够相遇的相遇节点，获取所述第一节点到达所述相遇节点的概率和所述第二节点到达所述相遇节点的概率之间的乘积，得到所述相遇节点对应的概率乘积结果；以及，根据所述第一节点和所述第二节点在每一步伐内能够相遇的相遇节点对应的所述概率乘积结果，确定所述第一节点和所述第二节点之间的相似度。11.根据本公开的第三方面，提供了一种电子设备，包括：至少一个处理器；以及与所述至少一个处理器通信连接的存储器；其中，所述存储器存储有可被所述至少一个处理器执行的指令，所述指令被所述至少一个处理器执行，以使所述至少一个处理器能够执行如第一方面所述的方法。12.根据本公开的第四方面，提供了一种存储有计算机指令的非瞬时计算机可读存储介质，所述计算机指令用于使计算机执行根据第一方面所述的方法。13.根据本公开的第五方面，提供了一种计算机程序产品，包括计算机程序，所述计算机程序在被处理器执行时实现根据第一方面所述的方法。14.本公开可以根据多个节点之间的关联关系，确定每个节点在最大游走长度内到达多个节点中的其他节点、以及所述节点到所述其他节点的概率。然后对第一节点和第二节点，根据第一节点和第二节点分别在最大游走长度内能够到达的最长路径，确定第一节点和第二节点在不同步伐内能够相遇的相遇节点，并对每一步中第一节点到达相遇节点的概率和第二节点到达相遇节点的概率之间的乘积进行求和，可以实现将第一节点和第二节点在不同步伐内相遇的概率作为第一节点和第二节点随机游走相遇的期望，从而用第一节点和第二节点随机游走相遇的期望来衡量第一节点和第二节点之间的相似度。第一节点和第二节点为多个节点中的任意两个节点。本公开计算第一节点和第二节点之间的相似度时，无需迭代多次或重复模拟，能够大大提高计算节点之间的相似度的速度，减少计算过程所消耗的资源。15.对于多个节点而言，本公开加速了多个节点中节点之间相似度的计算，能够实现以更快的频率全量更新所有节点的相似度，增加了相似度的新鲜程度。因此，本公开计算节点之间的相似度时，得到的相似度计算结果的实时性更强，计算结果更准确。16.应当理解，本部分所描述的内容并非旨在标识本公开的实施例的关键或重要特征，也不用于限制本公开的范围。本公开的其它特征将通过以下的说明书而变得容易理解。附图说明17.附图用于更好地理解本方案，不构成对本公开的限定。其中：18.图1为本公开实施例提供的确定节点相似度的方法的流程示意图；19.图2为本公开实施例提供的一种图模型的示意图；20.图3为本公开实施例提供的图1中s104的一种实现流程示意图；21.图4为本公开实施例提供的图1中s101的一种实现流程示意图；22.图5为本公开实施例提供的节点a对应的节点树的示意图；23.图6为本公开实施例提供的图4中s402的一种实现流程示意图；24.图7为本公开实施例提供的图6中s603的一种实现流程示意图；25.图8为本公开是实力提供的一种节点a和节点b的关系示意图；26.图9为本公开实施例提供的确定节点相似度的装置的组成示意图；27.图10示出了可以用来实施本公开的实施例的示例电子设备1000的示意性框图。具体实施方式28.以下结合附图对本公开的示范性实施例做出说明，其中包括本公开实施例的各种细节以助于理解，应当将它们认为仅仅是示范性的。因此，本领域普通技术人员应当认识到，可以对这里描述的实施例做出各种改变和修改，而不会背离本公开的范围和精神。同样，为了清楚和简明，以下的描述中省略了对公知功能和结构的描述。29.应当理解，在本公开各实施例中，字符“/”一般表示前后关联对象是一种“或”的关系。术语“第一”、“第二”等仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。30.目前，在广告投放、信息推荐等诸多领域中，可以通过计算节点之间的相似度，来获取与某个节点类似的节点。例如，节点可以是用户搜索的关键词、需要投放的广告、又或者期望推荐的短视频等。31.但是，目前计算节点之间的相似度的方法速度较慢，计算过程需要消耗大量的资源。32.本公开提供了一种确定节点相似度的方法，能够提高计算节点之间的相似度的速度，减少计算过程所消耗的资源。33.该方法中，节点可以是用户搜索的关键词、需要投放的广告、又或者期望推荐的短视频等。在不同的应用场景或领域中，节点所表示的含义不同，本公开在此不作限制。34.本公开实施例中，该方法的执行主体可以是计算机或服务器，或者还可以是其他具有数据处理能力的设备，在此对该方法的执行主体不作限制。35.一些实施例中，服务器可以是单独的一个服务器，或者，也可以是由多个服务器构成的服务器集群。部分实施方式中，服务器集群还可以是分布式集群。本公开对服务器的具体实现方式也不作限制。36.下面对该确定节点相似度的方法进行示例性说明。37.图1为本公开实施例提供的确定节点相似度的方法的流程示意图。如图1所示，该方法可以包括：38.s101、根据多个节点之间的关联关系，确定每个节点在最大游走长度内到达多个节点中的其他节点、以及节点到其他节点的概率。39.一些实施例中，多个节点之间的关联关系可以表示为图模型。例如，以多个节点包括：a、b、c、d、e、f、g、h为例，图2为本公开实施例提供的一种图模型的示意图。a、b、c、d、e、f、g、h等多个节点之间的关联关系可以参考图2所示。其中，当箭头指向的节点为子节点，箭头起源的节点为父节点。40.另外一些实施例中，多个节点之间的关联关系也可以表示为二部图或共现图形式的图模型。41.或者，还有一些实施例中，多个节点之间的关联关系也可以通过其他的数据结构(如表、文本等)来表示。本公开对获取到的多个节点之间的关联关系以何种形式表示并不作限制。42.可以理解的，本公开实施例中，s101之前，该方法还可以包括：获取多个节点之间的关联关系的步骤。43.示例性地，s101中提到的最大游走长度可以根据crashsim提出的方法计算得到，采用crashsim提出的方法计算最大游走长度为较为成熟的技术，在此不再详述。44.s102、对第一节点和第二节点，根据第一节点和第二节点分别在最大游走长度内能够到达的最长路径，确定第一节点和第二节点在不同步伐内能够相遇的相遇节点；第一节点和第二节点为多个节点中的任意两个节点。45.可以理解的，多个节点中的每个节点在多个节点的关联关系中可能具有到达不同节点的多条路径。对两个不同的节点，如第一节点和第二节点而言，第一节点和第二节点分别在最大游走长度内能够到达的最长路径可能会出现交集。从而，可以根据第一节点和第二节点分别在最大游走长度内能够到达的最长路径的交集，确定出第一节点和第二节点在不同步伐内能够相遇的相遇节点。46.s103、对第一节点和第二节点在每一步伐内能够相遇的相遇节点，获取第一节点到达相遇节点的概率和第二节点到达相遇节点的概率之间的乘积，得到相遇节点对应的概率乘积结果。47.例如，假设第一节点和第二节点在3步内能够相遇的相遇节点为节点x，第一节点到达节点x的概率为p1，第二节点到达节点x的概率为p2，则s103中可以获取p1和p2的乘积，作为节点x对应的概率乘积结果。48.s104、根据第一节点和第二节点在每一步伐内能够相遇的相遇节点对应的概率乘积结果，确定第一节点和第二节点之间的相似度。49.如s103中所述，对第一节点和第二节点在每一步伐内能够相遇的相遇节点，可以得到相遇节点对应的概率乘积结果。第一节点和第二节点在不同步伐内能够相遇的相遇节点可能包括多个。s104中可以根据第一节点和第二节点在每一步伐内能够相遇的相遇节点对应的概率乘积结果，来确定第一节点和第二节点之间的相似度。50.例如，一些实现方式中，s104中可以对第一节点和第二节点在每一步伐内能够相遇的相遇节点对应的概率乘积结果进行累加求和，将求和结果作为第一节点和第二节点之间的相似度。51.本公开实施例提供的该方法可以理解为是一种基于拓扑结构求节点相似度的方法，该方法实际是通过两节点随机游走相遇的期望来衡量节点之间的相似度。例如，该方法可以根据多个节点之间的关联关系，确定每个节点在最大游走长度内到达多个节点中的其他节点的概率。然后对多个节点中的任意一个第一节点、以及第一节点在最大游走长度内能够到达的第二节点，根据第一节点和第二节点分别在最大游走长度内能够到达的最长路径，确定第一节点和第二节点在不同步伐内能够相遇的相遇节点，并对每一步中第一节点到达相遇节点的概率和第二节点到达相遇节点的概率之间的乘积进行求和，可以实现将第一节点和第二节点在不同步伐内相遇的概率作为第一节点和第二节点随机游走相遇的期望，从而用第一节点和第二节点随机游走相遇的期望来衡量第一节点和第二节点之间的相似度。使用该方法计算第一节点和第二节点之间的相似度时，无需迭代多次或重复模拟，能够大大提高计算节点之间的相似度的速度，减少计算过程所消耗的资源。52.对于多个节点而言，该方法加速了多个节点中节点之间相似度的计算，能够实现以更快的频率全量更新所有节点的相似度，增加了相似度的新鲜程度。因此，使用本公开实施例提供的方法计算节点之间的相似度时，得到的相似度计算结果的实时性更强，计算结果更准确。53.图3为本公开实施例提供的图1中s104的一种实现流程示意图。如图3所示，一些实现方式中，s104可以包括：54.s301、获取第一节点和第二节点之间的初始相似度。55.s302、将第一节点和第二节点在每一步伐内能够相遇的相遇节点对应的概率乘积结果，累加到初始相似度上，得到第一节点和第二节点之间的相似度。56.一些实施例中，第一节点和第二节点之间的初始相似度可以为0。57.示例性地，本公开实施例中，可以先为多个节点构建一个初始相似度矩阵。该初始相似度矩阵中包含了任意两个节点之间的初始相似度。其中，相同的节点之间的初始相似度为1，其余不同的节点之间的初始相似度为0。58.另外一些实施例中，第一节点和第二节点之间的初始相似度也可以为大于0，在此不作限制。59.s302中将第一节点和第二节点在每一步伐内能够相遇的相遇节点对应的概率乘积结果，累加到初始相似度上，得到第一节点和第二节点之间的相似度，可以使得人工可以干预第一节点和第二节点之间的相似度的计算结果。例如，可以通过调整第一节点和第二节点之间的初始相似度的大小，来调整第一节点和第二节点之间的相似度的大小。60.图4为本公开实施例提供的图1中s101的一种实现流程示意图。如图4所示，一些实现方式中，s101可以包括：61.s401、根据多个节点之间的关联关系，为每个节点构建对应的节点树；节点树包括节点、节点在最大游走长度内能够到达的多个节点中的其他节点、以及节点与其他节点之间的路径。62.示例性地，以图2为例，图5为本公开实施例提供的节点a对应的节点树的示意图。如图5所示，节点a对应的节点树包括：节点a、节点a在最大游走长度内能够到达的多个节点中的其他节点(如b、c、d、e、f、g、h等)、以及节点与其他节点之间的路径。63.s402、根据每个节点对应的节点树，确定每个节点到达节点树种的其他节点的概率。64.本实施例中，通过先为每个节点构建对应的节点树，然后根据每个节点对应的节点树，确定每个节点到达节点树种的其他节点的概率，可以使得多个节点之间的关联关系表达的更加清楚，可以便于计算每个节点到达节点树种的其他节点的概率。65.应当理解，其他一些实施例中，也可以根据多个节点之间的关联关系，为每个节点构建类似于节点树、但与节点树具有同样表示功能的其他数据结构，在此不作限制。66.图6为本公开实施例提供的图4中s402的一种实现流程示意图。如图6所示，一些实现方式中，s402可以包括：67.s601、获取节点树中的每个父节点的子节点相对于父节点的权重。68.其中，当子节点是父节点的父节点时，子节点对父节点的权重为随机游走回头概率；当子节点是父节点的父节点的子节点时，子节点对父节点的权重为1；当子节点既不是父节点的父节点、也不是父节点的父节点的子节点时，子节点对父节点的权重为深度优先搜索游走概率。69.例如，以图5为例，假设父节点为c，则c的子节点可以包括a、d、f、g。s601中可以分别获取a、d、f、g相对于c的权重。70.s602、对节点树中的每个父节点的子节点相对于父节点的权重进行归一化，得到父节点到子节点的概率。71.s603、根据节点到达其他节点中的路径中每一层父节点到子节点的概率，确定节点到达其他节点的概率。72.一些实现方式中，s603可以包括：对节点到达其他节点中的路径中每一层父节点到子节点的概率进行累计求积，得到节点到达其他节点的概率。73.本实施例中，结合了node2vec的游走思路，优化了节点树的节点拓展方式，游走过程中，考虑了边的权重的同时，增加了随机游走回头概率和深度优先搜索游走概率两个参数来控制返回、深度优先搜索(depth-first-search，dfs)和广度/宽度优先搜索(breadthfirstsearch，bfs)的游走偏好，可以实现根据不同的业务场景选择更合适的游走偏好。74.图7为本公开实施例提供的图6中s603的一种实现流程示意图。如图7所示，另外一些实现方式中，s603可以包括：75.s701、获取节点到达其他节点中的路径中每一层父节点的子节点对父节点提供的置信度。76.s701可以包括：对节点到达其他节点中的路径中任意一层的父节点和子节点：根据父节点到子节点的权重、以及子节点的所有父节点到子节点的权重，确定子节点对父节点提供的置信度。77.其中，权重可以由业务自定义，比如说节点“关键词1”对节点“广告1”的点击率，即可作为两节点连接边的权重。或者，权重也可以是节点(如关键词)共现图中，两节点的相似度/提升度，在此不作限制。78.示例性地，置信度的计算公式可以如下述公式(1)所示。[0079][0080]公式(1)中，confi(tu,v)表示父节点tu游走到子节点v的置信度。wtu,v表示父节点tu到子节点v的边的权重；i(v)表示子节点v的所有父节点的集合，也称子节点v的所有入邻点的集合；∑t∈i(v)wt,v表示子节点v的所有父节点到子节点v的边的权重的和。[0081]s702、根据节点到达其他节点中的路径中每一层父节点的子节点对父节点提供的置信度，对节点到达其他节点中的路径中每一层父节点到子节点的概率进行累计求积，得到节点到达其他节点的概率。[0082]示例性地，s702中，在对节点到达其他节点中的路径中每一层父节点到子节点的概率进行累计求积时，可以将这一层父节点的子节点对父节点提供的置信度作为系数一并进行相乘，最终得到节点到达其他节点的概率。[0083]本实施例中，根据节点到达其他节点中的路径中每一层父节点的子节点对父节点提供的置信度，对节点到达其他节点中的路径中每一层父节点到子节点的概率进行累计求积，得到节点到达其他节点的概率，可以使得在衡量节点到达其他节点的概率时，增加了置信度来提供支撑度，能够使得后续计算得到的相似度结果更加准确。[0084]下面同样以图2所示的多个节点的关联关系为例，以一个具体的示例对本公开实施例提供的确定节点相似度的方法进行示例性说明。[0085]首先，请参考下述表1所示，示出了下述示例性说明中提到的一些参数的含义。[0086]表1[0087][0088][0089]基于表1所示的各参数的含义，请参考下述表2。表2示出了本公开实施例提供的确定节点相似度的方法的一种主要逻辑算法。该主要逻辑算法可以称为algorithm1：nodesimalgorithm。[0090]表2[0091][0092]表2中，input表示该算法的输入包括：由节点为v和边e构成的图g(v,e)、用于计算相似度的候选节点ω、simrank中定义的衰减因子(decayfactor)c。output表示该算法的输出为相似度。第1行表示先初始化一个相似度矩阵，除了相同节点之间相似度为1外，其余都为0；第2行表示初始化一个u矩阵，u矩阵记录了每个节点在l_max到达的其他节点的概率，l_max为最大游走长度；第3行表示根据crashsim提出的方法计算最大游走长度l_max；第4行至第5行表示对于图中每一个节点,计算该节点在l_max内用step步可到达其他节点的概率；第6行至第7行表示对于图中任意两个可以衡量相似度的节点；第8行表示对第6行至第7行定义的节点，通过两节点的u矩阵(matrix)计算两节点可到达的最长路径取交集；第9行至第10行表示循环迭代，找到不同步伐内可相遇的点；第10行至第12行表示对于每一步相遇的节点中，将两节点走到在相遇节点的概率乘积累加到两节点相似度上；从而，计算出了任意两节点之间的相似度。[0093]基于表2所示的算法algorithm1：nodesimalgorithm，其中，对于任意节点的l_max步内可到达的节点概率的计算方式可以参考下述表3。表3示出了本公开实施例提供的计算任意节点的l_max步内可到达的节点概率的算法，该算法可以称为algorithm2:reachprobalgorithm。[0094]表3[0095][0096]表3中，input表示该算法的输入包括：g(v,e),u∈v,lmax,c；output表示该算法的输出为任意节点的l_max步内可到达的节点概率；第1行表示初始化待计算的umatrix，u(0,-1,u)中，0表示0步到达u的概率，这里-1为伪造的节点u的入邻点；第2行表示初始化一个队列(queue)q记录待拓展的点,初始待拓展的点为0步到达节点u的元素；第3行表示初始化查询表(lookuptable)，记录每一层出现过的点；第4行表示算法开始从节点u开始拓展；第5行至第8行表示如果拓展深度大于l_max，拓展结束；否则对每一个从q中pop出的节点，拓展该节点的所有successors，拓展的概率由sampleprob算法计算,也就是算法node2vec的采样思路；successors是指该节点能够在l_max到达的节点的集合；第9行至第12行表示循环遍历节点tu的所有successors,首先判断入邻点为tu，从u出发tl+1可以到达v的元素是否已经被添加到q中，如果添加过，就不重复添加；第13行表示对于拓展的节点v，计算v对入邻点tu提供的置信度或自信度(confidence)；第14行表示对拓展出来的节点概率进行累加，其中，是代表有的概率游走，的概率停止。[0097]其中，confidence主要考虑到，入邻点太多的节点对相似度的衡量不精准。例如，图8为本公开是实力提供的一种节点a和节点b的关系示意图。如图8所示，假设图8中的(a)所示的场景下，x的父节点包括a和b；图8中的(b)所示的场景下，x的父节点包括a、b、c、d、e。则在度量点a和b之间的相似度时，图8中的(a)中节点x比在图8中的(b)中对a和b相似度计算提供的自信度要高。[0098]基于表3所示的算法algorithm2:reachprobalgorithm，其中，对于sampleprob算法(即算法node2vec的采样思路)可以参考下述表4。表4示出了本公开实施例提供的sampleprob算法，该算法可以称为algorithm3:sampleprobalgorithm。[0099]表4[0100][0101][0102]表4中，input表示该算法的输入包括：g(v,e),tr,tu∈v,p,q；tu表示要拓展的节点,tr是tu的父节点(parent节点)，p为控制随机游走回头概率的控制参数，1/p表示随机游走回头概率；q为控制随机游走偏向dfs还是bfs的控制参数，1/q表示深度优先搜索游走概率，q较大时(如q》1时)，随机游走偏向倾向于bfs，q较小时(如q《1时)，随机游走偏向倾向于dfs；output表示prob，即基于tu对子节点采样的概率，也即拓展的概率(或称为父节点到子节点的概率)；第1行表示初始化归一化因子z；第2行至第10行表示遍历每个tu的子节点，计算权重；其中，第3行至第4行表示如果子节点是tu的parent节点(line3-4)，也就是采样的子节点返回到tr，那么权重为1/p；第5行至第6行表示如果子节点是tu的parent节点的子节点，那么权重为1；第7行至第8行表示除了第3行至第4行和第5行至第6行所示的情况外，其他情况下权重为1/q。第9行至第10行表示初步计算得到各个子节点的权重；第11行至第12行表示用z进行归一化，使得tu到所有子节点的概率和为1；第13行表示返回概率结果。[0103]示例性地，本公开实施例可以适用于广告投放关键词生成的业务场景中，例如，广告投放关键词生成的业务中可能需要对广告投放的关键词进行拓展。如：对某个关键词1进行拓展时，可以查找与关键词1的相似度较高(如大于某个阈值)的关键词。本公开实施例则可以采用前述确定相似度的方法来计算其他关键词与关键词1的相似度，以实现对关键词1进行拓展。[0104]示例性实施例中，本公开实施例还提供一种确定节点相似度的装置，可以用于实现如前述实施例所述的方法实现的步骤。图9为本公开实施例提供的确定节点相似度的装置的组成示意图。如图9所示，该装置可以包括：概率确定单元901、相遇节点确定单元902、相似度确定单元903。[0105]概率确定单元901，用于根据多个节点之间的关联关系，确定每个所述节点在最大游走长度内到达所述多个节点中的其他节点、以及所述节点到所述其他节点的概率。[0106]相遇节点确定单元902，用于对第一节点和第二节点，根据所述第一节点和所述第二节点分别在所述最大游走长度内能够到达的最长路径，确定所述第一节点和所述第二节点在不同步伐内能够相遇的相遇节点；所述第一节点和所述第二节点为所述多个节点中的任意两个节点。[0107]相似度确定单元903，用于对所述第一节点和所述第二节点在每一步伐内能够相遇的相遇节点，获取所述第一节点到达所述相遇节点的概率和所述第二节点到达所述相遇节点的概率之间的乘积，得到所述相遇节点对应的概率乘积结果；以及，根据所述第一节点和所述第二节点在每一步伐内能够相遇的相遇节点对应的所述概率乘积结果，确定所述第一节点和所述第二节点之间的相似度。[0108]可选地，所述相似度确定单元903，具体用于：获取第一节点和第二节点之间的初始相似度；将第一节点和第二节点在每一步伐内能够相遇的相遇节点对应的概率乘积结果，累加到初始相似度上，得到第一节点和第二节点之间的相似度。[0109]可选地，所述概率确定单元901，具体用于：根据多个节点之间的关联关系，为每个节点构建对应的节点树；节点树包括节点、节点在最大游走长度内能够到达的多个节点中的其他节点、以及节点与其他节点之间的路径；根据每个节点对应的节点树，确定每个节点到达节点树种的其他节点的概率。[0110]可选地，所述概率确定单元901，具体用于：获取节点树中的每个父节点的子节点相对于父节点的权重；其中，当子节点是父节点的父节点时，子节点对父节点的权重为随机游走回头概率；当子节点是父节点的父节点的子节点时，子节点对父节点的权重为1；当子节点既不是父节点的父节点、也不是父节点的父节点的子节点时，子节点对父节点的权重为深度优先搜索游走概率；对节点树中的每个父节点的子节点相对于父节点的权重进行归一化，得到父节点到子节点的概率；根据节点到达其他节点中的路径中每一层父节点到子节点的概率，确定节点到达其他节点的概率。[0111]可选地，所述概率确定单元901，具体用于：获取节点到达其他节点中的路径中每一层父节点的子节点对父节点提供的置信度；根据节点到达其他节点中的路径中每一层父节点的子节点对父节点提供的置信度，对节点到达其他节点中的路径中每一层父节点到子节点的概率进行累计求积，得到节点到达其他节点的概率。[0112]可选地，所述概率确定单元901，具体用于：对节点到达其他节点中的路径中任意一层的父节点和子节点：根据父节点到子节点的权重、以及子节点的所有父节点到子节点的权重，确定子节点对父节点提供的置信度。[0113]本公开的技术方案中，所涉及的用户个人信息的获取，存储和应用等，均符合相关法律法规的规定，且不违背公序良俗。[0114]根据本公开的实施例，本公开还提供了一种电子设备、一种可读存储介质和一种计算机程序产品。[0115]示例性实施例中，电子设备，包括：至少一个处理器；以及与所述至少一个处理器通信连接的存储器；其中，所述存储器存储有可被所述至少一个处理器执行的指令，所述指令被所述至少一个处理器执行，以使所述至少一个处理器能够执行如以上实施例所述的方法。该电子设备可以是上述计算机或服务器。[0116]示例性实施例中，可读存储介质可以是存储有计算机指令的非瞬时计算机可读存储介质，所述计算机指令用于使计算机执行根据以上实施例所述的方法。[0117]示例性实施例中，计算机程序产品包括计算机程序，所述计算机程序在被处理器执行时实现根据以上实施例所述的方法。[0118]图10示出了可以用来实施本公开的实施例的示例电子设备1000的示意性框图。电子设备旨在表示各种形式的数字计算机，诸如，膝上型计算机、台式计算机、工作台、个人数字助理、服务器、刀片式服务器、大型计算机、和其它适合的计算机。电子设备还可以表示各种形式的移动装置，诸如，个人数字处理、蜂窝电话、智能电话、可穿戴设备和其它类似的计算装置。本文所示的部件、它们的连接和关系、以及它们的功能仅仅作为示例，并且不意在限制本文中描述的和/或者要求的本公开的实现。[0119]如图10所示，电子设备1000包括计算单元1001，其可以根据存储在只读存储器(rom)1002中的计算机程序或者从存储单元1008加载到随机访问存储器(ram)1003中的计算机程序，来执行各种适当的动作和处理。在ram1003中，还可存储设备1000操作所需的各种程序和数据。计算单元1001、rom1002以及ram1003通过总线1004彼此相连。输入/输出(i/o)接口1005也连接至总线1004。[0120]电子设备1000中的多个部件连接至i/o接口1005，包括：输入单元1006，例如键盘、鼠标等；输出单元1007，例如各种类型的显示器、扬声器等；存储单元1008，例如磁盘、光盘等；以及通信单元1009，例如网卡、调制解调器、无线通信收发机等。通信单元1009允许电子设备1000通过诸如因特网的计算机网络和/或各种电信网络与其他设备交换信息/数据。[0121]计算单元1001可以是各种具有处理和计算能力的通用和/或专用处理组件。计算单元1001的一些示例包括但不限于中央处理单元(cpu)、图形处理单元(gpu)、各种专用的人工智能(ai)计算芯片、各种运行机器学习模型算法的计算单元、数字信号处理器(dsp)、以及任何适当的处理器、控制器、微控制器等。计算单元1001执行上文所描述的各个方法和处理，例如确定节点相似度的方法。例如，在一些实施例中，确定节点相似度的方法可被实现为计算机软件程序，其被有形地包含于机器可读介质，例如存储单元1008。在一些实施例中，计算机程序的部分或者全部可以经由rom1002和/或通信单元1009而被载入和/或安装到电子设备1000上。当计算机程序加载到ram1003并由计算单元1001执行时，可以执行上文描述的确定节点相似度的方法的一个或多个步骤。备选地，在其他实施例中，计算单元1001可以通过其他任何适当的方式(例如，借助于固件)而被配置为执行确定节点相似度的方法。[0122]本文中以上描述的系统和技术的各种实施方式可以在数字电子电路系统、集成电路系统、现场可编程门阵列(fpga)、专用集成电路(asic)、专用标准产品(assp)、芯片上系统的系统(soc)、负载可编程逻辑设备(cpld)、计算机硬件、固件、软件、和/或它们的组合中实现。这些各种实施方式可以包括：实施在一个或者多个计算机程序中，该一个或者多个计算机程序可在包括至少一个可编程处理器的可编程系统上执行和/或解释，该可编程处理器可以是专用或者通用可编程处理器，可以从存储系统、至少一个输入装置、和至少一个输出装置接收数据和指令，并且将数据和指令传输至该存储系统、该至少一个输入装置、和该至少一个输出装置。[0123]用于实施本公开的方法的程序代码可以采用一个或多个编程语言的任何组合来编写。这些程序代码可以提供给通用计算机、专用计算机或其他可编程数据处理装置的处理器或控制器，使得程序代码当由处理器或控制器执行时使流程图和/或框图中所规定的功能/操作被实施。程序代码可以完全在机器上执行、部分地在机器上执行，作为独立软件包部分地在机器上执行且部分地在远程机器上执行或完全在远程机器或服务器上执行。[0124]在本公开的上下文中，机器可读介质可以是有形的介质，其可以包含或存储以供指令执行系统、装置或设备使用或与指令执行系统、装置或设备结合地使用的程序。机器可读介质可以是机器可读信号介质或机器可读储存介质。机器可读介质可以包括但不限于电子的、磁性的、光学的、电磁的、红外的、或半导体系统、装置或设备，或者上述内容的任何合适组合。机器可读存储介质的更具体示例会包括基于一个或多个线的电气连接、便携式计算机盘、硬盘、随机存取存储器(ram)、只读存储器(rom)、可擦除可编程只读存储器(eprom或快闪存储器)、光纤、便捷式紧凑盘只读存储器(cd-rom)、光学储存设备、磁储存设备、或上述内容的任何合适组合。[0125]为了提供与用户的交互，可以在计算机上实施此处描述的系统和技术，该计算机具有：用于向用户显示信息的显示装置(例如，crt(阴极射线管)或者lcd(液晶显示器)监视器)；以及键盘和指向装置(例如，鼠标或者轨迹球)，用户可以通过该键盘和该指向装置来将输入提供给计算机。其它种类的装置还可以用于提供与用户的交互；例如，提供给用户的反馈可以是任何形式的传感反馈(例如，视觉反馈、听觉反馈、或者触觉反馈)；并且可以用任何形式(包括声输入、语音输入或者、触觉输入)来接收来自用户的输入。[0126]可以将此处描述的系统和技术实施在包括后台部件的计算系统(例如，作为数据服务器)、或者包括中间件部件的计算系统(例如，应用服务器)、或者包括前端部件的计算系统(例如，具有图形用户界面或者网络浏览器的用户计算机，用户可以通过该图形用户界面或者该网络浏览器来与此处描述的系统和技术的实施方式交互)、或者包括这种后台部件、中间件部件、或者前端部件的任何组合的计算系统中。可以通过任何形式或者介质的数字数据通信(例如，通信网络)来将系统的部件相互连接。通信网络的示例包括：局域网(lan)、广域网(wan)和互联网。[0127]计算机系统可以包括客户端和服务器。客户端和服务器一般远离彼此并且通常通过通信网络进行交互。通过在相应的计算机上运行并且彼此具有客户端-服务器关系的计算机程序来产生客户端和服务器的关系。服务器可以是云服务器，也可以为分布式系统的服务器，或者是结合了区块链的服务器。[0128]应该理解，可以使用上面所示的各种形式的流程，重新排序、增加或删除步骤。例如，本公开中记载的各步骤可以并行地执行也可以顺序地执行也可以不同的次序执行，只要能够实现本公开公开的技术方案所期望的结果，本文在此不进行限制。[0129]上述具体实施方式，并不构成对本公开保护范围的限制。本领域技术人员应该明白的是，根据设计要求和其他因素，可以进行各种修改、组合、子组合和替代。任何在本公开的精神和原则之内所作的修改、等同替换和改进等，均应包含在本公开保护范围之内。当前第1页12当前第1页12
技术特征：1.一种确定节点相似度的方法，所述方法包括：根据多个节点之间的关联关系，确定每个所述节点在最大游走长度内到达所述多个节点中的其他节点、以及所述节点到所述其他节点的概率；对第一节点和第二节点，根据所述第一节点和所述第二节点分别在所述最大游走长度内能够到达的最长路径，确定所述第一节点和所述第二节点在不同步伐内能够相遇的相遇节点；所述第一节点和所述第二节点为所述多个节点中的任意两个节点；对所述第一节点和所述第二节点在每一步伐内能够相遇的相遇节点，获取所述第一节点到达所述相遇节点的概率和所述第二节点到达所述相遇节点的概率之间的乘积，得到所述相遇节点对应的概率乘积结果；根据所述第一节点和所述第二节点在每一步伐内能够相遇的相遇节点对应的所述概率乘积结果，确定所述第一节点和所述第二节点之间的相似度。2.根据权利要求1所述的方法，所述根据所述第一节点和所述第二节点在每一步伐内能够相遇的相遇节点对应的所述概率乘积结果，确定所述第一节点和所述第二节点之间的相似度，包括：获取所述第一节点和所述第二节点之间的初始相似度；将所述第一节点和所述第二节点在每一步伐内能够相遇的相遇节点对应的所述概率乘积结果，累加到所述初始相似度上，得到所述第一节点和所述第二节点之间的相似度。3.根据权利要求1或2所述的方法，所述根据多个节点之间的关联关系，确定每个所述节点在最大游走长度内到达所述多个节点中的其他节点的概率，包括：根据多个节点之间的关联关系，为每个所述节点构建对应的节点树；所述节点树包括所述节点、所述节点在所述最大游走长度内能够到达的所述多个节点中的其他节点、以及所述节点与所述其他节点之间的路径；根据每个所述节点对应的所述节点树，确定每个所述节点到达所述节点树种的所述其他节点的概率。4.根据权利要求3所述的方法，所述根据所述节点对应的所述节点树，确定所述节点到达所述其他节点的概率，包括：获取所述节点树中的每个父节点的子节点相对于所述父节点的权重；其中，当所述子节点是所述父节点的父节点时，所述子节点对所述父节点的权重为随机游走回头概率；当所述子节点是所述父节点的父节点的子节点时，所述子节点对所述父节点的权重为1；当所述子节点既不是所述父节点的父节点、也不是所述父节点的父节点的子节点时，所述子节点对所述父节点的权重为深度优先搜索游走概率；对所述节点树中的每个父节点的子节点相对于所述父节点的权重进行归一化，得到所述父节点到所述子节点的概率；根据所述节点到达所述其他节点中的路径中每一层父节点到子节点的概率，确定所述节点到达所述其他节点的概率。5.根据权利要求4所述的方法，所述根据所述节点到达所述其他节点中的路径中每一层父节点到子节点的概率，确定所述节点到达所述其他节点的概率，包括：获取所述节点到达所述其他节点中的路径中每一层父节点的子节点对所述父节点提供的置信度；
根据所述节点到达所述其他节点中的路径中每一层父节点的子节点对所述父节点提供的置信度，对所述节点到达所述其他节点中的路径中每一层父节点到子节点的概率进行累计求积，得到所述节点到达所述其他节点的概率。6.根据权利要求5所述的方法，所述获取所述节点到达所述其他节点中的路径中每一层父节点的子节点对所述父节点提供的置信度，包括：对所述节点到达所述其他节点中的路径中任意一层的父节点和子节点：根据所述父节点到所述子节点的权重、以及所述子节点的所有父节点到所述子节点的权重，确定所述子节点对所述父节点提供的置信度。7.一种确定节点相似度的装置，所述装置包括：概率确定单元，用于根据多个节点之间的关联关系，确定每个所述节点在最大游走长度内到达所述多个节点中的其他节点、以及所述节点到所述其他节点的概率；相遇节点确定单元，用于对第一节点和第二节点，根据所述第一节点和所述第二节点分别在所述最大游走长度内能够到达的最长路径，确定所述第一节点和所述第二节点在不同步伐内能够相遇的相遇节点；所述第一节点和所述第二节点为所述多个节点中的任意两个节点；相似度确定单元，用于对所述第一节点和所述第二节点在每一步伐内能够相遇的相遇节点，获取所述第一节点到达所述相遇节点的概率和所述第二节点到达所述相遇节点的概率之间的乘积，得到所述相遇节点对应的概率乘积结果；以及，根据所述第一节点和所述第二节点在每一步伐内能够相遇的相遇节点对应的所述概率乘积结果，确定所述第一节点和所述第二节点之间的相似度。8.根据权利要求7所述的装置，所述相似度确定单元，具体用于：获取所述第一节点和所述第二节点之间的初始相似度；将所述第一节点和所述第二节点在每一步伐内能够相遇的相遇节点对应的所述概率乘积结果，累加到所述初始相似度上，得到所述第一节点和所述第二节点之间的相似度。9.根据权利要求7或8所述的装置，所述概率确定单元，具体用于：根据多个节点之间的关联关系，为每个所述节点构建对应的节点树；所述节点树包括所述节点、所述节点在所述最大游走长度内能够到达的所述多个节点中的其他节点、以及所述节点与所述其他节点之间的路径；根据每个所述节点对应的所述节点树，确定每个所述节点到达所述节点树种的所述其他节点的概率。10.根据权利要求9所述的装置，所述概率确定单元，具体用于：获取所述节点树中的每个父节点的子节点相对于所述父节点的权重；其中，当所述子节点是所述父节点的父节点时，所述子节点对所述父节点的权重为随机游走回头概率；当所述子节点是所述父节点的父节点的子节点时，所述子节点对所述父节点的权重为1；当所述子节点既不是所述父节点的父节点、也不是所述父节点的父节点的子节点时，所述子节点对所述父节点的权重为深度优先搜索游走概率；对所述节点树中的每个父节点的子节点相对于所述父节点的权重进行归一化，得到所述父节点到所述子节点的概率；根据所述节点到达所述其他节点中的路径中每一层父节点到子节点的概率，确定所述
节点到达所述其他节点的概率。11.根据权利要求10所述的装置，所述概率确定单元，具体用于：获取所述节点到达所述其他节点中的路径中每一层父节点的子节点对所述父节点提供的置信度；根据所述节点到达所述其他节点中的路径中每一层父节点的子节点对所述父节点提供的置信度，对所述节点到达所述其他节点中的路径中每一层父节点到子节点的概率进行累计求积，得到所述节点到达所述其他节点的概率。12.根据权利要求11所述的装置，所述概率确定单元，具体用于：对所述节点到达所述其他节点中的路径中任意一层的父节点和子节点：根据所述父节点到所述子节点的权重、以及所述子节点的所有父节点到所述子节点的权重，确定所述子节点对所述父节点提供的置信度。13.一种电子设备，包括：至少一个处理器；以及与所述至少一个处理器通信连接的存储器；其中，所述存储器存储有可被所述至少一个处理器执行的指令，所述指令被所述至少一个处理器执行，以使所述至少一个处理器能够执行权利要求1-6任一项所述的方法。14.一种存储有计算机指令的非瞬时计算机可读存储介质，所述计算机指令用于使计算机执行根据权利要求1-6任一项所述的方法。15.一种计算机程序产品，包括计算机程序，所述计算机程序在被处理器执行时实现根据权利要求1-6任一项所述的方法。
技术总结本公开提供一种确定节点相似度的方法、装置、电子设备及存储介质，涉及计算机技术领域，具体涉及数据挖掘、图模型构建、相似度计算、智能推荐等技术领域。具体实现方案包括：根据多个节点之间的关联关系，确定每个节点在最大游走长度内到达多个节点中的其他节点、以及节点到其他节点的概率；根据第一节点和第二节点分别在最大游走长度内能够到达的最长路径，确定第一节点和第二节点在不同步伐内的相遇节点；第一节点和第二节点为两个节点；根据每一步伐内第一节点到达相遇节点的概率和第二节点到达相遇节点的概率之间的乘积，确定第一节点和第二节点的相似度。本公开可以提高计算节点之间的相似度的速度，减少计算过程所消耗的资源。源。源。
技术研发人员：师敏花
受保护的技术使用者：百度在线网络技术(北京)有限公司
技术研发日：2022.07.15
技术公布日：2022/11/1
