十亿规模网络嵌入的迭代随机投影算法及装置

摘要

本发明公开了一种十亿规模网络嵌入的迭代随机投影算法及装置，其中，方法包括：对目标网络生成随机投影矩阵，其中，目标网络为点和边为十亿及以上规模的网络；根据投影矩阵将数据分布式至不同服务器，以使每台服务器通过迭代随机投影算法得到网络嵌入的分量；根据每台服务器迭代得到的分量获得最终网络嵌入结果，并在网络动态更新时，对嵌入结果进行更新。该方法能够证明迭代投机随影可以支持分布式计算，并给出了迭代随机投影在动态网络下的更新算法，具有降低网络嵌入算法的计算复杂度及支持超大规模动态网络的网络嵌入的优点。

说明书

技术领域

本发明涉及大规模网络嵌入技术领域，特别涉及一种十亿规模网络嵌入的迭代随机投影算法及装置。

背景技术

现有的网络嵌入方法只针对节点和边为几千量级，或最多为百万级的网络，而无法处理超大规模网络，即点和边为十亿规模以上的网络。此外，因为较高的通信代价，它们都无法很好支持分布式计算。

发明内容

本发明旨在至少在一定程度上解决相关技术中的技术问题之一。

为此，本发明的一个目的在于提出一种十亿规模网络嵌入的迭代随机投影算法，。

本发明的另一个目的在于提出一种十亿规模网络嵌入的迭代随机投影装置。

为达到上述目的，本发明一方面实施例提出了一种十亿规模网络嵌入的迭代随机投影算法，包括以下步骤：对目标网络进行随机投影，以生成随机投影矩阵，其中，所述目标网络为点和边为十亿及以上规模的网络；根据所述投影矩阵将数据分布式至不同服务器，以使每台服务器通过迭代随机投影算法得到网络嵌入的分量；以及根据所述每台服务器迭代得到的分量获得最终网络嵌入结果，并在网络动态更新时，对嵌入结果进行更新。

本发明实施例的十亿规模网络嵌入的迭代随机投影算法，能够证明迭代投机随影可以支持分布式计算，并给出了迭代随机投影在动态网络下的更新算法，具有降低网络嵌入算法的计算复杂度及支持超大规模动态网络的网络嵌入的优点。

另外，根据本发明上述实施例的十亿规模网络嵌入的迭代随机投影算法还可以具有以下附加的技术特征：

进一步地，在本发明的实施例中，所述对嵌入结果进行更新，进一步包括：通过所述迭代随机投影算法的更新算法更新所述嵌入结果。

进一步地，在本发明的实施例中，其特征在于，所述迭代随机投影算法为：通过迭代正交高斯随机投影，保持网络嵌入中的半正定高阶相似度，以解决网络数据稀疏性对网络嵌入的影响；分布式的不同服务器独立计算投影的不同维度，以作为网络嵌入的分量。

进一步地，在本发明的实施例中，其特征在于，所述更新算法为：当所述网络动态更新时，通过计算所述网络嵌入的增量部分，快速更新嵌入结果，并保证嵌入向量相对算法重启没有累积误差。

为达到上述目的，本发明另一方面实施例提出了一种十亿规模网络嵌入的迭代随机投影装置。

本发明实施例的十亿规模网络嵌入的迭代随机投影装置，包括：生成模块，用于对目标网络进行随机投影，以生成随机投影矩阵，其中，所述目标网络为点和边为十亿及以上规模的网络；计算模块，用于根据所述投影矩阵将数据分布式至不同服务器，以使每台服务器通过迭代随机投影算法得到网络嵌入的分量；以及更新模块，根据所述每台服务器迭代得到的分量获得最终网络嵌入结果，并在网络动态更新时，根据所述最终网络嵌入结果对嵌入结果进行更新。

本发明实施例的十亿规模网络嵌入的迭代随机投影装置，通过

另外，根据本发明上述实施例的十亿规模网络嵌入的迭代随机投影装置还可以具有以下附加的技术特征：

进一步地，在本发明的实施例中，所述对嵌入结果进行更新，进一步包括：通过所述迭代随机投影算法的更新算法更新所述嵌入结果。

进一步地，在本发明的实施例中，其特征在于，所述迭代随机投影算法为：通过迭代正交高斯随机投影，保持网络嵌入中的半正定高阶相似度，以解决网络数据稀疏性对网络嵌入的影响；分布式的不同服务器独立计算投影的不同维度，以作为网络嵌入的分量。

进一步地，在本发明的实施例中，其特征在于，所述更新算法为：当所述网络动态更新时，通过计算所述网络嵌入的增量部分，快速更新嵌入结果，并保证嵌入向量相对算法重启没有累积误差。

本发明附加的方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本发明的实践了解到。

附图说明

本发明上述的和/或附加的方面和优点从下面结合附图对实施例的描述中将变得明显和容易理解，其中：

图1为根据本发明一个实施例的十亿规模网络嵌入的迭代随机投影算法流程图；

图2为根据本发明一个实施例的十亿规模网络嵌入的迭代随机投影装置的结构示意图。

具体实施方式

下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施例是示例性的，旨在用于解释本发明，而不能理解为对本发明的限制。

下面参照附图描述根据本发明实施例提出的十亿规模网络嵌入的迭代随机投影算法及装置，首先将参照附图描述根据本发明实施例提出的十亿规模网络嵌入的迭代随机投影算法。

图1为根据本发明一个实施例的十亿规模网络嵌入的迭代随机投影算法流程图

如图1所示，该十亿规模网络嵌入的迭代随机投影算法，包括以下步骤：

在步骤S101中，对目标网络生成随机投影矩阵，其中，目标网络为点和边为十亿及以上规模的网络。

在步骤S102中，根据投影矩阵将数据分布式至不同服务器，以使每台服务器通过迭代随机投影算法得到网络嵌入的分量。

在本发明的一个实施例中，通过迭代正交高斯随机投影，保持网络嵌入中的半正定高阶相似度，以解决网络数据稀疏性对网络嵌入的影响；分布式的不同服务器独立计算投影的不同维度，以作为网络嵌入的分量。

在步骤S103中，根据每台服务器迭代得到的分量获得最终网络嵌入结果，并在网络动态更新时，对嵌入结果进行更新。

在本发明的一个实施例中，当网络动态更新时，通过计算网络嵌入的增量部分，快速更新嵌入结果，并保证嵌入向量相对算法重启没有累积误差。

本发明实施例的十亿规模网络嵌入的迭代随机投影算法，能够证明迭代投机随影可以支持分布式计算，并给出了迭代随机投影在动态网络下的更新算法，具有降低网络嵌入算法的计算复杂度及支持超大规模动态网络的网络嵌入的优点

其次参照附图描述根据本发明实施例提出的十亿规模网络嵌入的迭代随机投影装置。

图2为根据本发明一个实施例的十亿规模网络嵌入的迭代随机投影装置的结构示意图，如图2所示，该十亿规模网络嵌入的迭代随机投影装置10包括：生成模块100，用于对目标网络生成随机投影矩阵，其中，目标网络为点和边为十亿及以上规模的网络；计算模块200，用于根据投影矩阵将数据分布式至不同服务器，以使每台服务器通过迭代随机投影算法得到网络嵌入的分量；更新模块300，根据每台服务器迭代得到的分量获得最终网络嵌入结果，并在网络动态更新时，对嵌入结果进行更新。

进一步地，在本发明的实施例中，所述根据所述最终网络嵌入结果对嵌入结果进行更新，进一步包括：通过所述迭代随机投影算法的更新算法更新所述嵌入结果。

进一步地，在本发明的实施例中，所述迭代随机投影算法为：通过迭代正交高斯随机投影，保持网络嵌入中的半正定高阶相似度，以解决网络数据稀疏性对网络嵌入的影响；分布式的不同服务器独立计算投影的不同维度，以作为网络嵌入的分量。

进一步地，在本发明的实施例中，所述更新算法为：当网络动态更新时，通过计算网络嵌入的增量部分，快速更新嵌入结果，并保证嵌入向量相对算法重启没有累积误差。

需要说明的是，前述对十亿规模网络嵌入的迭代随机投影方法实施例的解释说明也适用于该实施例的装置，此处不再赘述。

本发明实施例的十亿规模网络嵌入的迭代随机投影装置，能够证明迭代投机随影可以支持分布式计算，并给出了迭代随机投影在动态网络下的更新算法，具有降低网络嵌入算法的计算复杂度及支持超大规模动态网络的网络嵌入的优点。

在本发明的描述中，需要理解的是，术语“中心”、“纵向”、“横向”、“长度”、“宽度”、“厚度”、“上”、“下”、“前”、“后”、“左”、“右”、“竖直”、“水平”、“顶”、“底”“内”、“外”、“顺时针”、“逆时针”、“轴向”、“径向”、“周向”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本发明的限制。

此外，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括至少一个该特征。在本发明的描述中，“多个”的含义是至少两个，例如两个，三个等，除非另有明确具体的限定。

在本发明中，除非另有明确的规定和限定，术语“安装”、“相连”、“连接”、“固定”等术语应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或成一体；可以是机械连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接相连，可以是两个元件内部的连通或两个元件的相互作用关系，除非另有明确的限定。对于本领域的普通技术人员而言，可以根据具体情况理解上述术语在本发明中的具体含义。

在本发明中，除非另有明确的规定和限定，第一特征在第二特征“上”或“下”可以是第一和第二特征直接接触，或第一和第二特征通过中间媒介间接接触。而且，第一特征在第二特征“之上”、“上方”和“上面”可是第一特征在第二特征正上方或斜上方，或仅仅表示第一特征水平高度高于第二特征。第一特征在第二特征“之下”、“下方”和“下面”可以是第一特征在第二特征正下方或斜下方，或仅仅表示第一特征水平高度小于第二特征。

在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不必须针对的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任一个或多个实施例或示例中以合适的方式结合。此外，在不相互矛盾的情况下，本领域的技术人员可以将本说明书中描述的不同实施例或示例以及不同实施例或示例的特征进行结合和组合。

尽管上面已经示出和描述了本发明的实施例，可以理解的是，上述实施例是示例性的，不能理解为对本发明的限制，本领域的普通技术人员在本发明的范围内可以对上述实施例进行变化、修改、替换和变型。