一种无向图的预估权重矩阵的确定方法及装置

技术领域

本说明书一个或多个实施例涉及图应用技术领域，尤其涉及一种无向图的预估权重矩阵的确定方法及装置。

背景技术

图论的实际应用非常的广泛，无向图作为一个图论的一个分支，同样有非常广泛的应用。实际应用无向图时，需要根据实际应用场景构建无向图，例如，无向图的每个顶点代表什么，顶点与顶点之间的边代表什么，边的权重代表什么等等。以社交关系为例，每个顶点代表一个用户，顶点之间的边代表两个顶点对应的用户之间有无直接好友关系，边的权重代表两个顶点对应的用户之间的关系紧密度。

相关技术中，在基于构建的无向图进行相关计算时，一般默认构建的图是准确的，即，是基于应用场景中全面的、准确的信息构建的无向图，那么基于所构建的无向图进行相关的计算也是准确的。

然而，实际应用中，由于数据缺失、脏数据等，使得构建的无向图并不是很准确，基于此所构建的无向图进行相关的计算也是不准确的。

发明内容

有鉴于此，本说明书一个或多个实施例提供一种无向图的预估权重矩阵的确定方法及装置。

为实现上述目的，本说明书一个或多个实施例提供技术方案如下：

根据本说明书一个或多个实施例的第一方面，提出了一种无向图的预估权重矩阵的确定方法，该方法包括：

获取无向图的原始权重矩阵W

将所述原始权重矩阵作为当前权重矩阵W

循环执行以下步骤，直至满足循环结束条件：

根据当前权重矩阵W

若不满足循环结束条件，则按照基于T的预设更新算法，更新当前权重矩阵W

循环结束后，将循环结束时的当前权重矩阵W

根据本说明书一个或多个实施例的第二方面，提出了一种无向图的预估权重矩阵的确定装置，该装置包括：

获取模块，用于获取无向图的原始权重矩阵W

初始化模块，用于将所述原始权重矩阵作为当前权重矩阵W

循环执行模块，包括计算单元、更新单元，用于循环控制所述计算单元以及所述更新单元，直至满足循环结束条件：

所述计算单元，用于根据当前权重矩阵W

所述更新单元，用于若不满足循环结束条件，则按照基于T的预设更新算法，更新当前权重矩阵W

预估权重矩阵确定模块，用于循环结束后，将循环结束时的当前权重矩阵W

根据本说明书一个或多个实施例的第三方面，提出了一种电子设备，包括：

处理器；

用于存储处理器可执行指令的存储器；

其中，所述处理器通过运行所述可执行指令以实现如上述所述的无向图的预估权重矩阵的确定方法。

根据本说明书一个或多个实施例的第四方面，提出了一种计算机可读存储介质，其上存储有计算机指令，该指令被处理器执行时实现如上述所述的无向图的预估权重矩阵的确定方法。

在本说明书一个或读个实施例中，获取无向图的原始权重矩阵W

通过本说明书的一个或多个实施例，基于权重矩阵与分组信息的关系，逐步估算出与真实正确的权重矩阵贴近的预估权重矩阵，使得基于权重矩阵的相关计算更准确。

附图说明

图1是一示例性实施例提供的一种无向图的预估权重矩阵的确定方法的流程图示意图。

图2是一示例性实施例提供的一种无向图的预估权重矩阵的确定装置的框图示意图。

图3是一示例性实施例提供的一种计算机设备的结构示意图。

具体实施方式

这里将详细地对示例性实施例进行说明，其示例表示在附图中。下面的描述涉及附图时，除非另有表示，不同附图中的相同数字表示相同或相似的要素。以下示例性实施例中所描述的实施方式并不代表与本说明书一个或多个实施例相一致的所有实施方式。相反，它们仅是与如所附权利要求书中所详述的、本说明书一个或多个实施例的一些方面相一致的装置和方法的例子。

需要说明的是：在其他实施例中并不一定按照本说明书示出和描述的顺序来执行相应方法的步骤。在一些其他实施例中，其方法所包括的步骤可以比本说明书所描述的更多或更少。此外，本说明书中所描述的单个步骤，在其他实施例中可能被分解为多个步骤进行描述；而本说明书中所描述的多个步骤，在其他实施例中也可能被合并为单个步骤进行描述。

很多应用场景下，基于相关的数据得到的无向图的权重矩阵是不准确的，而很多进一步的计算都是基于权重矩阵进行的，例如图的聚类、图的分割等，都是需要基于构建的无向图的权重矩阵进行，很多情况下默认数据是正确完整的，因此默认构建的无向图也是准确的，进一步的根据构建的无向图(即，将构建的无向图的权重矩阵作为超参数)进行进一步的相关计算也是准确的。然而实际情况是，获取的相关数据并不是准确完整的，以社交场景为例，两个顶点代表的两个用户之间的互动数据的缺失或不足，导致这两个顶点之间代表关系紧密度的权重的大小比实际要小很多。

发明人在实践中发现，很多应用场景下，都会对无向图中的各个顶点进行分组，两个顶点之间的差异度越小(两个顶点的相关信息越相似)，越可能属于同一分组，而分组信息与权重有着很大的联系，属于同一分组的两个顶点之间的权重会相对更大，相对的，不属于同一分组的两个顶点之间的权重会相对更小。以社交关系为例，每个顶点为一个用户，一个亲友圈为一个分组(如，一个家族为一个分组)，每两个顶点之间的权重代表这两个顶点所代表的用户之间的关系紧密度，属于同一亲友圈的两个用户关系紧密度会相对越高，属于不同亲友圈的两个用户之间的关系紧密度会相对越低，甚至可能为0。

基于此，本说明书提出在权重矩阵和分组信息有如上关系的应用场景下的无向图的预估权重矩阵的确定方法，获取无向图的原始权重矩阵W

通过本说明书的一个或多个实施例，基于权重矩阵与分组信息的关系，逐步估算出与真实正确的权重矩阵贴近的预估权重矩阵，使得基于权重矩阵的相关计算更准确。

本说明书提供了一种无向图的预估权重矩阵的确定方法，并提供了与该方法对应的装置、设备、计算机存储介质，接下来对无向图的预估权重矩阵的确定方法进行详细的说明。

如上述，在很多应用场景下，都会对无向图中的各个顶点进行分组，而一般情况下，分组信息与权重有着很大的联系，属于同一分组的两个顶点之间的权重会相对更大，相对的，不属于同一分组的两个顶点之间的权重会相对更小。本说明书的无向图的预估权重矩阵的确定方法就是基于此前提下进行的，换而言之，若分组信息与权重矩阵没有如上述的关系，那么并不适用本说明书所示出的无向图的预估权重矩阵的确定方法。

首先对本说明无向图的预估权重矩阵的确定方法的原理进行说明，属于同一分组的两个顶点之间的权重会相对更大，而属于同一分组的两个顶点之间的差异度会相对更小，相对的，不属于同一分组的两个顶点之间的权重会相对更小，而属于不同分组的两个顶点之间的差异度会更大，基于此认识，针对任意两个顶点(顶点i与顶点j)，用W

如图1所示，为本说明书示出的无向图的预估权重矩阵的确定方法的流程示意图，包括以下步骤：

步骤101、获取无向图的原始权重矩阵W

需要说明的是，在本说明书中，对于任一权重矩阵W中的任一元素W

在本说明书中，原始权重矩阵是根据原始数据构建得到的，原始数据可能存在缺失，或者脏数据(错误的数据)，因此构建的原始权重矩阵可能不是准确的。还是以社交场景为例，每个顶点为一个用户，针对任意两个用户，根据这两个用户在社交场景下的互动确定这两个用户之间的关系紧密度，从而得到关系权重矩阵。

需要说明的是，本说明书针对的是无向图，因此权重矩阵都是对称矩阵(即，i行j列的值与j行i列的值相同，i不等于j)，矩阵中，每个顶点与自身之间没有权重(i行i列的没有值)，为非法值(NAN值)。

如表1所示，为本说明书示出的权重矩阵：

表1权重矩阵示意表

其中，A、B、C、D代表顶点，每个值代表任意两个顶点之间的权重。

实际应用中，任意两个顶点之间的权重可能由于数据的缺失，使得这两个顶点之间的权重无法确定，因此可将这两个顶点之间的权重设为0，即，针对原始权重矩阵中的任意两个顶点，若该两个顶点之间没有权重，在权重矩阵中对应的位置补0。

原始分组信息是指对各个顶点进行分类，一般情况下是将相似度高(即差异度小)分为一组，例如社交场景中的兴趣小组，亲友组等，都是某个方面的信息具有很高的相似度。

各个顶点的分组信息，可以是预先标记好的，也可以是基于相似度聚类而成的，分组数量是一定的，每个顶点属于各个分组的概率是不一定的，本说明书给出的一种示例为用分组矩阵表示各个顶点属于各个分组的概率。

令分组矩阵为P，分组矩阵中的P

如表2所示，为本说明书示出的分组矩阵示意表：

表2分组矩阵示意表

步骤103、将所述原始权重矩阵作为当前权重矩阵W

步骤105、根据当前权重矩阵W

其中，Q

在分组信息为如上述的分组矩阵的情况下，此时

此外，一般会考虑其他影响因素，那么

步骤107、判断是否满足循环结束条件，若不满足循环结束条件，则跳转至步骤109；若满足循环结束条件，则跳转至步骤111。

其中，循环结束条件可以是总网络信息T收敛，或者循环执行次数到达预设次数，或者总网络信息T收敛或循环执行次数到达预设次数。

在循环结束条件是总网络信息T收敛的情况下，认为此时的总网络信息与总网络信息最小值之间的差距可以忽略不计，那么，认为此时对应的当前权重矩阵最贴近与真实权重矩阵。

在循环结束条件是循环执行次数到达预设次数的情况下，认为循环执行预设次数后的总网络信息T与总网络信息最小值之间的差距可以忽略不计，那么，认为此时对应的当前权重矩阵最贴近与真实权重矩阵。

在循环结束条件是总网络信息T收敛或循环执行次数到达预设次数的情况下，认为循环执行预设次数后或者总网络信息T收敛后(满足任一条件)，此时的总网络信息T与总网络信息最小值之间的差距可以忽略不计，那么，认为此时对应的当前权重矩阵最贴近与真实权重矩阵。

步骤109、按照基于T的预设更新算法，更新当前权重矩阵W

可以根据T的随机方向，对当前权重矩阵W

按照预设的梯度对当前权重矩阵以及当前分组信息进行更新时，可以以如下方式进行更新：

针对当前权重矩阵W

其中，归一化时，可以以如下方式进行处理：

即，针对当前权重矩阵中的任一权重，计算该权重

针对当前分组矩阵P

其中，归一化时，可以以如下方式进行处理：

即，针对当分组矩阵中的任一分组概率，计算该分组概率

实际应用中，上述权重矩阵的学习率γ与分组矩阵的学习率δ可以相同，也可以不相同，都是根据经验设定的。

本说明书仅示意性给出了当前权重矩阵与当前分组信息的更新公式，本领域技术人员可以基于本说明书的思想衍生出更多的更新公式，本说明书不一一列举。

步骤111、将循环结束时的当前权重矩阵W

当总网络信息T收敛后或者循环执行次数达到预设后，认为此时的总网络信息T可以代替最小总网络信息T，那么认为此时的当前权重矩阵W

由于认为得到的预估权重矩阵是贴近真实正确的权重矩阵的，因此，此时的预估权重矩阵具有较强的指导意义，通过比较预估权重矩阵与原始权重矩阵之间的差异，评估构建的原始权重矩阵。

令原始权重矩阵为W

进一步的，若

针对零权重的顶点i与顶点j，即，原始权重矩阵中

以上是对无向图的预估权重矩阵的确定方法的说明，接下来对与其对应的装置进行详细的说明。

本说明书提供了一种无向图的预估权重矩阵的确定装置，如图2所示，该装置包括：

获取模块201，用于获取无向图的原始权重矩阵W

初始化模块203，用于将所述原始权重矩阵作为当前权重矩阵W

循环执行模块205，包括计算单元2051、更新单元2052，用于循环控制所述计算单元以及所述更新单元，直至满足循环结束条件：

所述计算单元，用于根据当前权重矩阵W

所述更新单元，用于若不满足循环结束条件，则按照基于T的预设更新算法，更新当前权重矩阵W

预估权重矩阵确定模块207，用于循环结束后，将循环结束时的当前权重矩阵W

其中，循环结束条件可以为以下其中一种：

总网络信息T收敛；

循环执行次数到达预设次数；

总网络信息T收敛或循环执行次数到达预设次数。

其中，分组信息为分组矩阵P，分组矩阵中的P

此时，

此外，在分组信息为分组矩阵P的情况下，更新单元还可具体用于：

针对当前权重矩阵W

针对当前分组矩阵P

此外，该装置还可以包括：

比较模块，用于比较所述预估权重矩阵W

确定模块，用于针对

此外，该装置还可以包括：

比较模块，用于比较所述预估权重矩阵W

确定模块，用于针对

上述装置中各个模块的功能和作用的实现过程具体详见上述方法中对应步骤的实现过程，在此不再赘述。

对于装置实施例而言，由于其基本对应于方法实施例，所以相关之处参见方法实施例的部分说明即可。以上所描述的装置实施例仅仅是示意性的，其中所述作为分离部件说明的模块可以是或者也可以不是物理上分开的，作为模块显示的部件可以是或者也可以不是物理模块，即可以位于一个地方，或者也可以分布到多个网络模块上。可以根据实际的需要选择其中的部分或者全部模块来实现本说明书方案的目的。本领域普通技术人员在不付出创造性劳动的情况下，即可以理解并实施。

本说明书还提供一种电子设备，包括：

处理器；

用于存储处理器可执行指令的存储器；

其中，所述处理器通过运行所述可执行指令以实现如上述任一所述的无向图的预估权重矩阵的确定方法。

在一个典型的配置中，计算机包括一个或多个处理器(CPU)、输入/输出接口、网络接口和内存。

内存可能包括计算机可读介质中的非永久性存储器，随机存取存储器(RAM)和/或非易失性内存等形式，如只读存储器(ROM)或闪存(flash RAM)。内存是计算机可读介质的示例。

图3示出了本说明书实施例所提供的一种更为具体的计算设备硬件结构示意图，该设备可以包括：处理器310、存储器320、输入/输出接口330、通信接口340和总线350。其中处理器310、存储器320、输入/输出接口330和通信接口340通过总线350实现彼此之间在设备内部的通信连接。

处理器310可以采用通用的CPU(Central Processing Unit，中央处理器)、微处理器、应用专用集成电路(Application Specific Integrated Circuit，ASIC)、或者一个或多个集成电路等方式实现，用于执行相关程序，以实现本说明书实施例所提供的技术方案。

存储器320可以采用ROM(Read Only Memory，只读存储器)、RAM(Random AccessMemory，随机存取存储器)、静态存储设备，动态存储设备等形式实现。存储器320可以存储操作系统和其他应用程序，在通过软件或者固件来实现本说明书实施例所提供的技术方案时，相关的程序代码保存在存储器320中，并由处理器310来调用执行。

输入/输出接口330用于连接输入/输出模块，以实现信息输入及输出。输入输出/模块可以作为组件配置在设备中(图中未示出)，也可以外接于设备以提供相应功能。其中输入设备可以包括键盘、鼠标、触摸屏、麦克风、各类传感器等，输出设备可以包括显示器、扬声器、振动器、指示灯等。

通信接口340用于连接通信模块(图中未示出)，以实现本设备与其他设备的通信交互。其中通信模块可以通过有线方式(例如USB、网线等)实现通信，也可以通过无线方式(例如移动网络、WIFI、蓝牙等)实现通信。

总线350包括一通路，在设备的各个组件(例如处理器310、存储器320、输入/输出接口330和通信接口340)之间传输信息。

需要说明的是，尽管上述设备仅示出了处理器310、存储器320、输入/输出接口330、通信接口340以及总线350，但是在具体实施过程中，该设备还可以包括实现正常运行所必需的其他组件。此外，本领域的技术人员可以理解的是，上述设备中也可以仅包含实现本说明书实施例方案所必需的组件，而不必包含图中所示的全部组件。

本说明书还提供一种计算机可读存储介质，其上存储有计算机指令，该指令被处理器执行时实现如上述任一所述无向图的预估权重矩阵的确定方法的步骤。

计算机可读介质包括永久性和非永久性、可移动和非可移动媒体可以由任何方法或技术来实现信息存储。信息可以是计算机可读指令、数据结构、程序的模块或其他数据。计算机的存储介质的例子包括，但不限于相变内存(PRAM)、静态随机存取存储器(SRAM)、动态随机存取存储器(DRAM)、其他类型的随机存取存储器(RAM)、只读存储器(ROM)、电可擦除可编程只读存储器(EEPROM)、快闪记忆体或其他内存技术、只读光盘只读存储器(CD-ROM)、数字多功能光盘(DVD)或其他光学存储、磁盒式磁带、磁盘存储、量子存储器、基于石墨烯的存储介质或其他磁性存储设备或任何其他非传输介质，可用于存储可以被计算设备访问的信息。按照本文中的界定，计算机可读介质不包括暂存电脑可读媒体(transitory media)，如调制的数据信号和载波。

还需要说明的是，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、商品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、商品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、商品或者设备中还存在另外的相同要素。

上述对本说明书特定实施例进行了描述。其它实施例在所附权利要求书的范围内。在一些情况下，在权利要求书中记载的动作或步骤可以按照不同于实施例中的顺序来执行并且仍然可以实现期望的结果。另外，在附图中描绘的过程不一定要求示出的特定顺序或者连续顺序才能实现期望的结果。在某些实施方式中，多任务处理和并行处理也是可以的或者可能是有利的。

在本说明书一个或多个实施例使用的术语是仅仅出于描述特定实施例的目的，而非旨在限制本说明书一个或多个实施例。在本说明书一个或多个实施例和所附权利要求书中所使用的单数形式的“一种”、“所述”和“该”也旨在包括多数形式，除非上下文清楚地表示其他含义。还应当理解，本文中使用的术语“和/或”是指并包含一个或多个相关联的列出项目的任何或所有可能组合。

应当理解，尽管在本说明书一个或多个实施例可能采用术语第一、第二、第三等来描述各种信息，但这些信息不应限于这些术语。这些术语仅用来将同一类型的信息彼此区分开。例如，在不脱离本说明书一个或多个实施例范围的情况下，第一信息也可以被称为第二信息，类似地，第二信息也可以被称为第一信息。取决于语境，如在此所使用的词语“如果”可以被解释成为“在……时”或“当……时”或“响应于确定”。

以上所述仅为本说明书一个或多个实施例的较佳实施例而已，并不用以限制本说明书一个或多个实施例，凡在本说明书一个或多个实施例的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本说明书一个或多个实施例保护的范围之内。