[0024] 下面通过具体实施例,并结合附图,对本发明的具体实施方式作进一步具体说明。
[0025] 实施例一:
[0026] 一种基于跨双层网络随机游走的网络表征方法,如图1所示,为实施例一网络表征方法流程框图,本实施例包括以下步骤:A)根据真实系统中实体之间的关系建立网络拓扑结构,获得网络邻接矩阵W={wij},i,j∈[1,n],n为网络拓扑结构节点数量;B)获得节点在大小不超过给定值k的诱导子图中的角色序列,记为表征向量,建立节点之间的角色相似度矩阵S={sij},i,j∈[1,n];C)根据网络邻居矩阵W以及角色相似度矩阵中节点的一一对应关系,建立双层混合网络;D)依次从每个节点开始,进行h次跨双层混合网络的随机游走,从随机游走序列中得到截断长度为l的共h组节点序列,n个节点共获得n*h个长度为l的节点序列;E)把网络中的节点作为词,把通过随机游走得到的节点序列作为语句,使用word2vec的连续词袋模型,将每个词表示成一个定长的向量,将本步骤获得的定长向量作为对应节点的表征,从而获得网络的表征。其中,网络邻接矩阵W的节点代表系统中的实体,边则表示实体之间的相互作用或者关系。若系统中实体数量为n,则网络拓扑结构可以表示为n×m的矩阵。本实施例的邻接网络也可以是带权重的网络,用wij表示节点i和j的关系权重。如果两个节点i和j之间仅有边没有权重,则令wij=1。如果两个节点i和j之间没有边,则令wij=0。
[0027] 角色相似度矩阵S的建立方法为:B1)列举所有大小小于或等于给定大小k的所有子图;B2)枚举所有子图中的非同构轨道,标记非同构轨道中的角色,全部非同构轨道中包含的角色数量记为m;B3)将每个节点参与m个角色的情况使用长度为m的向量表示,该向量作为该节点的角色表征向量;B4)将每两个节点的角色表征向量的相似度作为该两个节点的相似度,角色相似度矩阵S。
[0028] 节点之间的角色相似度矩阵S的元素
[0029]
[0030] 其中,GDV(i)、GDV(j)分别为节点i、j的角色表征向量,i,j∈[1,n]。
[0031] 步骤B中使用角色表征向量建立节点之间的角色相似度矩阵S前,对角色表征向量进行中心化和标准化处理,中心化的方法为:将角色表征向量中的每个元素减去该向量中全部元素的均值;标准化的方法为:计算中心化后角色表征向量全部元素的标准差,将角色表征向量中的每个元素除以标准差。
[0032] 在步骤D中跨双层混合网络的随机游走时,设定参数α(0≤α≤1),α为每步游走时选择邻接网络游走的概率。
[0033] 步骤A中根据真实系统中实体之间的关系建立网络拓扑结构时,若实体之间存在直接关联,则认为两个实体存在相邻关系,反之,则通过 ‑邻居方法或者K‑邻近算法(KNN)来确定二者之间是否存在相邻关系。
[0034] ‑邻居方法确定两个实体之间是否存在相邻关系的方法为:
[0035] 若两个实体之间的拓扑距离或实际距离小于人工设定值 则认为两个实体存在相邻关系,反之,则认为两个实体无相邻关系。
[0036] K‑邻近算法(KNN)确定两个实体之间是否存在相邻关系的方法为:
[0037] 获取实体与其他实体的最近距离L,认为与该实体距离小于σ*L的K个实体与该实体存在相邻关系,其余实体与该实体无相邻关系,σ为容差系数,其值大于1,其值由人工设定。
[0038] 如图2所示,为实施例一诱导子图非同构轨道示意图,当k=4时,共有8个诱导子图(G1‑G8),节点在诱导子图中的非同构轨道数为m=14。图2显示了子图大小小于等于4的全部子图中的非同构轨道数的寻找方法,图2中G0显示了当子图大小为2时,非同构位置仅有1个,图2中以数字0表示,所有参与了大小为2的子图的节点,在其角色表征向量第0个位置均记为1。图2中G1、G2显示了当子图大小为3时,的网络具有两个大小为3的子图结构,共有3个非同构位置,图2中以数字1,2,3表示,节点参与了大小为3的非环形的子图时,参与两端的情况时,在其角色表征向量第1个位置记为1,参与中间的情况时,在其角色表征向量第2个位置记为1,参与了大小为3的环形子图的节点,在其角色表征向量第3个位置均记为1,依次类推。图2中G3‑G8显示了当子图大小为4时,的网络具有六个子图结构,其中非同构位置共有11个,图2中以数字4‑14表示,所以该网络中,子图大小小于等于4的非同构轨道共有15个,同样的方法获得该网络的全部子图的非同构位置,统计其数量记为m。给定规模为k的诱导子图,网络中的每一个节点可以扮演m个不同的角色。邻接网络中每个节点参与不同非同构轨道的次数,构成一个m维向量,称为非同构子图度向量(Graphlet Degree Vector,简称GDV)。
[0039] 如图3所示,为实施例一跨双层网络示意图,邻接网络和节点相似度网络中的节点为一一对应关系。上层是基于实体关系的邻接网络,下层是基于节点角色的相似度网络,上下层之间通过一一对应的网络节点相连,虚线表示邻居网络里的节点连接关系,实线表示相似度网络里的节点连接关系。
[0040] 如图4所示,为实施例一跨双层网络的随机游走示意图,从网络任一节点i出发,跨双层网络随机游走每一步的具体步骤如下:
[0041] 1)确定参数α,以概率α选择在邻接网络游走;以概率1‑α选择在相似度网络游走;
[0042] 2)如果在邻接网络中游走,将与节点i相连的所有边的相对权重作为采样的概率,即下一步经过节点j的概率如下:
[0043]
[0044] 如果节点在相似度网络中游走,将与节点i相连的所有边的相似度比率作为采样概率,即下一步经过节点j的概率如下:
[0045]
[0046] 这里Ni表示节点i的所有邻居节点的集合。注意:这里节点j不能是节点i的上一步经过的节点。图4显示了随机游走获得的一个序列为{1,3,4,5,6,8,9},图中的实线表示在相似度网络里的游走,虚线表示在邻居网络里的游走。
[0047] 虽然从理论上而言,随机游走的采样长度越长,最后生成的表征结果越精确。但是,但当游走长度足够长时,继续增加步长所带来的精确度上的提升相对于所增加的计算开销而言,是不值得的。因此,从计算复杂度的角度,随机游走需要设定游走长度l,具体值可通过有限次试验后,由人工权衡精度和系统开销设定。按照如上步骤,从每个节点开始进行h次跨双层网络的随机游走,则对网络中的所有节点共得到n×h个长度为l的节点组合。从i点出发的采样序列记为Li={i,i1,…,il}.
[0048] 实施例二:
[0049] 本实施例对实施例步骤C获得的双层混合网络使用跳字模型,提取节点特征形成节点表征,进而形成网络表征。跳字(skip‑gram)模型实现节点表征,其过程为通过给定一个中心词,经过只有一个隐藏层的简单神经网路训练,来预测可能与其共同出现的词。本实施例中使用一个中心节点,即随机游走的出发点,预测可能出现在其随机游走采样序列中的另一节点的概率。若两个节点同时出现在同一随机游走采样序列中的概率越高,则两个节点的角色相似度越高。
[0050] 对任意采样序列Li,给定中心节点i生成背景节点ik的条件概率可以通过对向量内积做softmax运算而得到:
[0051]
[0052] 这里,uk∈Rd是背景节点ik的向量表示,vi∈Rd是中心节点i的向量表示。对于所有采样序列Li,跳字模型的似然函数如下:
[0053]
[0054] 跳字模型的参数是每个词所对应的中心节点向量和背景节点向量。通过最大化似然函数来学习模型参数训练,即最大似然估计:
[0055]
[0056] 为提高优化效率,本实施例采用负采样优化,即每次让一个训练样本仅仅更新一小部分权重参数,从而降低梯度下降过程中的计算量,提高训练速度考虑sigmoid函数。对于一对中心节点和背景节点,随机采样K个噪音节点,噪音节点采样概率p(j)设为j的节点频率与所有节点总频率之比的0.75次方:
[0057]
[0058] 综上,目标函数可以写成:
[0059]
[0060] 其中,D表示正例,D′表示负例,(w,c)表示所有随机游走产生的数据对,c表示中心节点,w表示背景节点。最后利用随机梯度下降方法,对目标函数进行优化,获得每个节点的随机游走序列,作为该节点的表征。全部节点的表征构成网络的表征。
[0061] 以上所述的实施例只是本发明的一种较佳的方案,并非对本发明作任何形式上的限制,在不超出权利要求所记载的技术方案的前提下还有其它的变体及改型。