符号网络中噪声边感知的社区检测方法

1.本技术涉及社区检测领域，具体地，涉及一种符号网络中噪声边感知的社区检测方法。


背景技术：

2.随着信息化步伐的加快，微信、快手、抖音、拼多多等即时通信、短视频、直播、线上购物的社交应用软件迅速崛起。人们通过网络平台点赞、关注、收藏、打视频电话、发朋友圈、互相关注、分享自己的日常生活等，将人们生活中的各种行为关系被延伸到了网络空间中，形成了符号网络。如何聚合符号网络中的信息，并进行社区检测是当下的研究热点。
3.通过对符号网络中用户之间的拓扑信息进行节点低维向量表示，得到用户在嵌入空间中的嵌入向量，利用社区检测方法划分网络中用户的社区归属，通过用户的社区标签可以为下游很多决策失误提供帮助，例如，犯罪发现。理想的符号网络中的社区结构具有以下拓扑性质：(1)每个社区内的大多数内部连接具有正符号，(2)社区间的大多数互连接具有负符号。真实世界中的社交关系是复杂的，可能存在两种情况：两个用户属于同一个社区却相互之间充满敌意；两个用户隶属于不同的社区却相互之间非常亲近。在这里定义这两种情况的用户关系边为噪声边。
4.在现有的符号网络社区检测方法中对网络中接待你进行低维向量表示时，均未去降低噪声边对嵌入向量的影响。若属于一个社区的两个用户在嵌入过程中聚合噪声边的信息，可能使两个用户的嵌入向量相似度极低；若将分别隶属于不同社区的两个用户在嵌入过程中聚合噪声边的信息，可能使两个用户的嵌入向量相似度极高。噪声边的存在会影响网络的节点低维向量表示，进而影响社区检测的精准度。


技术实现要素：

5.为了克服现有技术中的至少一个不足，本技术提供一种符号网络中噪声边感知的社区检测方法。
6.第一方面，提供一种符号网络中噪声边感知的社区检测方法，包括：
7.对符号网络的拓扑信息进行嵌入，得到符号网络的嵌入矩阵；
8.基于符号网络的嵌入矩阵，确定符号网络中的噪声边集合和噪声边节点集合；
9.根据噪声边集合对符号网络中的所有噪声边进行标记，得到更新后的符号网络；
10.对更新后的符号网络的拓扑信息进行嵌入，得到更新后的符号网络的嵌入矩阵；在嵌入过程中，忽略所有噪声边；
11.根据更新后的符号网络的嵌入矩阵和噪声边节点集合，确定符号网络中每个节点所属社区。
12.在一个实施例中，对符号网络的拓扑信息进行嵌入，得到符号网络的嵌入矩阵，包括：
13.确定符号网络中每个节点的正边邻居集合和负边邻居集合；
14.根据每个节点的正边邻居集合和负边邻居集合，对符号网络的拓扑信息进行嵌入，得到符号网络的嵌入矩阵。
15.在一个实施例中，根据每个节点的正边邻居集合和负边邻居集合，对符号网络的拓扑信息进行嵌入，得到符号网络的嵌入矩阵，包括：
16.根据每个节点的正边邻居集合和负边邻居集合，确定每个节点的嵌入向量；
17.将所有节点的嵌入向量进行连接，得到符号网络的嵌入矩阵。
18.在一个实施例中，根据每个节点的正边邻居集合和负边邻居集合，确定每个节点的嵌入向量，包括：
19.对于节点u，当聚合一跳邻居的信息时，节点u的一跳邻居的平衡集合嵌入矩阵和非平衡集合嵌入矩阵采用以下公式：
[0020][0021][0022]
其中，为节点u的一跳邻居的平衡集合嵌入矩阵，为节点u的一跳邻居的非平衡集合嵌入矩阵，σ(
·
)为激活函数，为节点u的一跳邻居的平衡游走路径bu(1)的权重，为节点u的一跳邻居的非平衡游走路径uu(1)的权重，为节点u的正边邻居集合，|
·
|为集合大小，为节点u的负边邻居集合，为节点v的隐藏表示，为节点u的隐藏表示；
[0023]
当聚合多跳邻居的信息时，节点u的多跳邻居的平衡集合嵌入矩阵和非平衡集合嵌入矩阵采用以下公式：
[0024][0025][0026]
其中，为节点u的h跳邻居的平衡集合嵌入矩阵，为节点u的h跳邻居的非平衡集合嵌入矩阵，σ(
·
)为激活函数，为节点u的h跳邻居的平衡游走路径bu(h)的权重，为节点u的h跳邻居的非平衡游走路径uu(h)的权重，|
·
|为集合大小，为节点v的h-1跳邻居的平衡集合嵌入矩阵，为节点v的h-1跳邻居的非平
衡集合嵌入矩阵，为节点k的h-1跳邻居的非平衡集合嵌入矩阵，为节点k的h-1跳邻居的平衡集合嵌入矩阵，为节点u的h-1跳邻居的平衡集合嵌入矩阵，节点u的h-1跳邻居的非平衡集合嵌入矩阵；
[0027]
当聚合一跳邻居的信息时，将节点u的一跳邻居的平衡集合嵌入矩阵和非平衡集合嵌入矩阵连接在一起，得到节点u的嵌入向量；
[0028]
当聚合多跳邻居的信息时，将节点u的多跳邻居的平衡集合嵌入矩阵和非平衡集合嵌入矩阵连接在一起，得到节点u的嵌入向量。
[0029]
在一个实施例中，基于符号网络的嵌入矩阵，确定符号网络中的噪声边集合和噪声边节点集合，包括：
[0030]
针对符号网络的嵌入矩阵采用k-means聚类算法，确定符号网络中各个节点初步所属社区；
[0031]
根据符号网络中各个节点初步所属社区确定符号网络中的正关系噪声边集合和负关系噪声边集合；
[0032]
正关系噪声边集合和负关系噪声边集合构成噪声边集合，噪声边集合中所有噪声边两端的噪声边节点构成噪声边节点集合。
[0033]
在一个实施例中，根据符号网络中各个节点初步所属社区确定符号网络中的正关系噪声边集合和负关系噪声边集合，采用以下公式：
[0034][0035]
其中，n
e,pos
为正关系噪声边集合，ε
uv
为节点u和节点v之间的边，a
+
为符号网络中的正边集合，labelu为节点u所属社区，labelv为节点v所属社区，若节点u与节点v属于同一个社区，δ(labelu,labelv)的结果值为1，若节点u与节点v不属于同一个社区，δ(labelu,labelv)的结果值为0；triangle
balance
为符号网络中的平衡三角形集合；
[0036][0037]
其中，n
e,neg
为负关系噪声边集合，a-为符号网络中的负边集合。
[0038]
在一个实施例中，根据更新后的符号网络的嵌入矩阵和噪声边节点集合，确定符号网络中每个节点所属社区，包括：
[0039]
根据更新后的符号网络的嵌入矩阵，采用k-means聚类算法，确定更新后的符号网络中各个节点所属社区；符号网络中的各个节点包括非噪声边节点和噪声边节点；
[0040]
更新后的符号网络的嵌入矩阵中包括多个节点对应的嵌入向量，根据非噪声边节点对应的嵌入向量，计算更新后的符号网络中各个社区的聚类中心；
[0041]
针对噪声边节点集合中的每个噪声边节点，确定当前噪声边节点与各个社区的聚类中心之间的相似度，将相似度最高的聚类中心所属社区作为重新确定的当前噪声边节点所属社区。
[0042]
第二方面，提供一种符号网络中噪声边感知的社区检测装置，包括：
[0043]
第一嵌入矩阵获取模块，用于对符号网络的拓扑信息进行嵌入，得到符号网络的嵌入矩阵；
[0044]
噪声边确定模块，用于基于符号网络的嵌入矩阵，确定符号网络中的噪声边集合
和噪声边节点集合；
[0045]
符号网络更新模块，用于根据噪声边集合对符号网络中的所有噪声边进行标记，得到更新后的符号网络；
[0046]
第二嵌入矩阵获取模块，用于对更新后的符号网络的拓扑信息进行嵌入，得到更新后的符号网络的嵌入矩阵；在嵌入过程中，忽略所有噪声边；
[0047]
节点所属社区确定模块，用于根据更新后的符号网络的嵌入矩阵和噪声边节点集合，确定符号网络中每个节点所属社区。
[0048]
在一个实施例中，噪声边确定模块，还用于：
[0049]
针对符号网络的嵌入矩阵采用k-means聚类算法，确定符号网络中各个节点初步所属社区；
[0050]
根据符号网络中各个节点初步所属社区确定符号网络中的正关系噪声边集合和负关系噪声边集合；
[0051]
正关系噪声边集合和负关系噪声边集合构成噪声边集合，噪声边集合中所有噪声边两端的噪声边节点构成噪声边节点集合。
[0052]
在一个实施例中，节点所属社区确定模块，还用于：
[0053]
根据更新后的符号网络的嵌入矩阵，采用k-means聚类算法，确定更新后的符号网络中各个节点所属社区；符号网络中的各个节点包括非噪声边节点和噪声边节点；
[0054]
更新后的符号网络的嵌入矩阵中包括多个节点对应的嵌入向量，根据非噪声边节点对应的嵌入向量，计算更新后的符号网络中各个社区的聚类中心；
[0055]
针对噪声边节点集合中的每个噪声边节点，确定当前噪声边节点与各个社区的聚类中心之间的相似度，将相似度最高的聚类中心所属社区作为重新确定的当前噪声边节点所属社区。
[0056]
相对于现有技术而言，本技术具有以下有益效果：
[0057]
1、本技术考虑到符号网络中存在的噪声边对社区检测的影响，结合平衡理论，并考虑到社区结构存在非平衡态与弱平衡态，从而允许属于平衡三角形的负边位于社区内部，允许属于平衡三角形的正边位于两个社区之间，从而降低了符号网络中噪声边的影响并提高了社区检测的精准度。
[0058]
2、本技术基于平衡理论对符号网络中的拓扑信息进行嵌入，优化设计目标函数使得网络中的正边节点对在嵌入空间中互相之间的距离短于负边节点对在嵌入空间中的距离，更接近正边与负边所代表的不同语义。
附图说明
[0059]
本技术可以通过参考下文中结合附图所给出的描述而得到更好的理解，附图连同下面的详细说明一起包含在本说明书中并且形成本说明书的一部分。在附图中：
[0060]
图1示出了平衡理论示意图；
[0061]
图2示出了根据本技术实施例的符号网络中噪声边感知的社区检测方法的流程框图；
[0062]
图3示出了面向社区检测的节点低维度向量表示模型示意图；
[0063]
图4示出了符号网络中噪声边示意图；
[0064]
图5示出了根据本技术实施例的符号网络中噪声边感知的社区检测装置的结构框图；
[0065]
图6示出了nepcd算法与基线算法在社区数为2-10时在数据集bitcoin_otc中的错误率对比图；
[0066]
图7示出了nepcd算法与基线算法在社区数为2-10时在数据集wikielect中的错误率对比图；
[0067]
图8示出了nepcd算法与基线算法在社区数为2-10时在数据集wikirfa中的错误率对比图；
[0068]
图9示出了nepcd算法与不进行噪声边感知去忽略的算法(non-nepcd算法)在社区数为2-10时在数据集bitcoin_otc中的错误率对比图；
[0069]
图10示出了nepcd算法与不进行噪声边感知去忽略的算法(non-nepcd算法)在社区数为2-10时在数据集wikielect中的错误率对比图；
[0070]
图11示出了nepcd算法与不进行噪声边感知去忽略的算法(non-nepcd算法)在社区数为2-10时在数据集wikirfa中的错误率对比图；
[0071]
图12示出了nepcd算法与与基线算法在数据集spp中的nmi值对比图；
[0072]
图13示出了nepcd算法与与基线算法在数据集ggs中的nmi值对比图。
具体实施方式
[0073]
在下文中将结合附图对本技术的示例性实施例进行描述。为了清楚和简明起见，在说明书中并未描述实际实施例的所有特征。然而，应该了解，在开发任何这种实际实施例的过程中可以做出很多特定于实施例的决定，以便实现开发人员的具体目标，并且这些决定可能会随着实施例的不同而有所改变。
[0074]
在此，还需要说明的一点是，为了避免因不必要的细节而模糊了本技术，在附图中仅仅示出了与根据本技术的方案密切相关的装置结构，而省略了与本技术关系不大的其他细节。
[0075]
应理解的是，本技术并不会由于如下参照附图的描述而只限于所描述的实施形式。在本文中，在可行的情况下，实施例可以相互组合、不同实施例之间的特征替换或借用、在一个实施例中省略一个或多个特征。
[0076]
现有技术对符号网络进行社区检测的过程中并未考虑噪声边的存在，噪声边的存在违背符号网络中的社区结构原则，对符号网络中噪声边的信息进行低维向量表示，最终会影响社区检测结果的精准度。若属于一个社区的两个用户在嵌入过程中聚合噪声边的信息，可能使两个用户的嵌入向量相似度极低；若将分别隶属于不同社区的两个用户在嵌入过程中聚合噪声边的信息，可能使两个用户的嵌入向量相似度极高。噪声边的存在会影响网络的节点低维向量表示，进而影响社区检测的精准度。
[0077]
以下对涉及的相关概念进行定义：
[0078]
符号网络：符号网络的边具有“正”或“负”的涵义，用符号“+”或
“‑”
对边进行对应标注，带正号的边代表积极关系，表示朋友、支持、信任等；带负号的边代表消极关系，表示敌对、反对、对抗等。而普通社交网络的边默认均为“+”，即积极关系，符号网络采用无向图g(v,e)表示，其中v代表用户节点集合，e代表用户之间的边集合，e∈[-1,0,1]。
[0079]
噪声边：符号网络中位于两个社区之间的正边且不属于任一平衡三角形，符号网络中位于社区之内的负边且不属于任一平衡三角形。
[0080]
理想的符号网络社区结构：社区内紧密且只存在正边，社区之间稀疏且只存在负边。
[0081]
图1示出了平衡理论示意图，参见图1，将(a)和(b)称为平衡三角形，将(c)和(d)称为非平衡三角形。针对于符号网络中平衡的状态，平衡理论采用如下定义方式：如图1中的(a)所示，平衡理论认为“节点i的朋友节点j的朋友节点k就是节点i的朋友节点”；如图1中的(b)所示，平衡理论认为“节点i的敌人节点j的朋友节点k就是节点i的敌人节点”。平衡理论将符号网络中的三角形分类为平衡或不平衡，不符合上述思想的三角形都被认为是不平衡的。简单来说，平衡三角形由偶数个负边组成，而具有奇数个负边的三角形被认为是不平衡的。符号网络中的所有平衡三角形构成平衡三角形集合triangle
balance
，所有非平衡三角形构成非平衡三角形集合triangle
unbalance
。
[0082]
本技术实施例提供一种符号网络中噪声边感知的社区检测方法，图2示出了根据本技术实施例的符号网络中噪声边感知的社区检测方法的流程框图，参见图2，方法包括：
[0083]
步骤s1，对符号网络的拓扑信息进行嵌入，得到符号网络的嵌入矩阵。
[0084]
步骤s2，基于符号网络的嵌入矩阵，确定符号网络中的噪声边集合和噪声边节点集合。
[0085]
步骤s3，根据噪声边集合对符号网络中的所有噪声边进行标记，得到更新后的符号网络。
[0086]
步骤s4，对更新后的符号网络的拓扑信息进行嵌入，得到更新后的符号网络的嵌入矩阵；在嵌入过程中，忽略所有噪声边；该步骤的具体实现方式与步骤s1一致。
[0087]
步骤s5，根据更新后的符号网络的嵌入矩阵和噪声边节点集合，确定符号网络中每个节点所属社区。
[0088]
该实施例中，符号网络中包括用户节点集合v与边集合e，用户节点集合v的大小为n，即节点个数为n，边集合中存在代表“积极关系”的正边与代表“消极关系”的负边，在这些边中存在噪声边，本技术感知符号网络中的噪声边并进行标记，在进行节点低维表示过程中忽略掉噪声边的信息，以获得高精准度的社区检测结果。
[0089]
在一个实施例中，步骤s1中，对符号网络的拓扑信息进行嵌入，得到符号网络的嵌入矩阵，包括：
[0090]
步骤s11，确定符号网络中每个节点的正边邻居集合和负边邻居集合；这里，正边邻居集合采用如下定义：节点u与节点v之间的边为正边，则节点v即为节点u的正边邻居，节点u的所有正边邻居构成节点u的正边邻居集合；负边邻居集合采用如下定义：节点u与节点v之间的边为负边，则节点v即为节点u的负边邻居，节点u的所有负边邻居构成节点u的负边邻居集合。
[0091]
步骤s12，根据每个节点的正边邻居集合和负边邻居集合，对符号网络的拓扑信息进行嵌入，得到符号网络的嵌入矩阵。
[0092]
具体地，首先，根据每个节点的正边邻居集合和负边邻居集合，确定每个节点的嵌入向量：
[0093]
对于节点u，当聚合一跳邻居的信息时，节点u的一跳邻居的平衡集合嵌入矩阵和
非平衡集合嵌入矩阵采用以下公式：
[0094][0095][0096]
其中，为节点u的一跳邻居的平衡集合嵌入矩阵，为节点u的一跳邻居的非平衡集合嵌入矩阵，σ(
·
)为激活函数，为节点u的一跳邻居的平衡游走路径bu(1)的权重，为节点u的一跳邻居的非平衡游走路径uu(1)的权重，为节点u的正边邻居集合，为节点u的负边邻居集合，为节点v的隐藏表示，为节点u的隐藏表示；
[0097]
当聚合多跳邻居的信息时，节点u的多跳邻居的平衡集合嵌入矩阵和非平衡集合嵌入矩阵采用以下公式：
[0098][0099][0100]
其中，为节点u的h跳邻居的平衡集合嵌入矩阵，为节点u的h跳邻居的非平衡集合嵌入矩阵，σ(
·
)为激活函数，为节点u的h跳邻居的平衡游走路径bu(h)的权重，为节点u的h跳邻居的非平衡游走路径uu(h)的权重，为节点u的正边邻居集合，为节点u的负边邻居集合，为节点v的h-1跳邻居的平衡集合嵌入矩阵，为节点v的h-1跳邻居的非平衡集合嵌入矩阵，为节点k的h-1跳邻居的非平衡集合嵌入矩阵，为节点k的h-1跳邻居的平衡集合嵌入矩阵，为节点u的h-1跳邻居的平衡集合嵌入矩阵，节点u的h-1跳邻居的非平衡集合嵌入矩阵；
[0101]
当聚合一跳邻居的信息时，将节点u的一跳邻居的平衡集合嵌入矩阵和非平衡集合嵌入矩阵连接在一起，得到节点u的嵌入向量；当聚合多跳邻居的信息时，将节点u的多跳邻居的平衡集合嵌入矩阵和非平衡集合嵌入矩阵连接在一起，得到节点u的嵌入向量。
[0102]
然后，将所有节点的嵌入向量进行连接，得到符号网络的嵌入矩阵。
[0103]
该实施例中，节点u的平衡游走路径和非平衡游走路径，采用以下方式确定：
[0104]
当聚合一跳邻居的信息时，平衡游走路径和非平衡游走路径采用以下公式：
[0105][0106][0107]
其中，bu(1)为节点u的一跳邻居的平衡游走路径，uu(1)为节点u的一跳邻居的非平衡游走路径，v为节点，为节点u的正边邻居集合，为节点u的负边邻居集合；
[0108]
当聚合多跳邻居的信息时，平衡游走路径与非平衡游走路径采用以下公式：
[0109][0110][0111]
其中，k为节点，bu(h+1)为节点u的h+1跳邻居的平衡游走路径，bu(h)为节点u的h跳邻居的平衡游走路径，为节点v的正边邻居集合，uu(h)节点u的h跳邻居的非平衡游走路径，为节点v的负边邻居集合。
[0112]
该实施例中，本技术基于平衡理论对符号网络中的拓扑信息进行嵌入，优化设计目标函数使得网络中的正边节点对在嵌入空间中互相之间的距离短于负边节点对在嵌入空间中的距离，更接近正边与负边所代表的不同语义。
[0113]
图3示出了面向社区检测的节点低维度向量表示模型示意图，如图3所示，对于节点u聚合邻居信息，该符号社交网络中实线表示用户节点之间存在积极关系，虚线表示用户节点之间存在消极关系，虚线箭头表示的是对目标节点进行非平衡路径邻居的信息聚合，实线箭头表示的是对目标节点进行平衡路径邻居的信息聚合。
[0114]
在一个实施例中，图4示出了符号网络中噪声边示意图，如图4所示，符号网络中噪声边的定义，其中符号网络由12个节点、17条正边和5条负边组成。假设网络存在如下社区c1＝{va,vb,vc,vd},c2＝{ve,vf,vg}，c3＝{vh,vi,vj,vk,v
l
}。在这里，边e
eh
不被认为是噪声边，虽然e
eh
是位于两个社区之间的正边，但e
eh
是一个平衡三角形中的边，是一个稳定的社区关系。同样，e
hj
不被认为是噪声边，虽然e
hj
是位于社区内的负边，但e
hj
是平衡三角形中的边，社区关系稳定。另一方面，e
bf
和e
cd
边是噪声边：(1)vb和vf之间存在一条正边连接，尽管它们位于不同的邻域，不属于任何一种平衡三角形；(2)vc和vd虽然在同一邻域内，不属于任何一种平衡三角形，但存在一条负边。模型可以将e
bf
和e
cd
识别为噪声边，并将其排除在学习之外，因为在这两条边上进行学习会影响社区发现的准确性。因此，步骤s2中基于符号网络的嵌入矩阵，确定符号网络中的噪声边集合和噪声边节点集合，可以包括：
[0115]
步骤s21，针对符号网络的嵌入矩阵采用k-means聚类算法，确定符号网络中各个节点初步所属社区；
[0116]
步骤s22，根据符号网络中各个节点初步所属社区确定符号网络中的正关系噪声边集合和负关系噪声边集合；对于正关系噪声边的确定标准是这条边属于正边集合、这条边位于两个社区之间且不属于任一个平衡三角形；对于负关系噪声边的确定标准是这条边属于负边集合、这条边位于一个社区内且不属于任一个平衡三角形。
[0117]
该步骤中，采用以下公式确定正关系噪声边集合和负关系噪声边集合：
[0118]
[0119]
其中，n
e,pos
为正关系噪声边集合，ε
uv
为节点u和节点v之间的边，a
+
为符号网络中的正边集合，labelu为节点u所属社区，labelv为节点v所属社区，若节点u与节点v属于同一个社区，δ(labelu,labelv)的结果值为1，若节点u与节点v不属于同一个社区，δ(labelu,labelv)的结果值为0；triangle
balance
为符号网络中的平衡三角形集合；
[0120][0121]
其中，n
e,neg
为负关系噪声边集合，a-为符号网络中的负边集合。
[0122]
步骤s23，正关系噪声边集合和负关系噪声边集合构成噪声边集合，即ne＝n
e,pos
∪n
e,neg
，其中ne为噪声边集合，噪声边集合中所有噪声边两端的噪声边节点构成噪声边节点集合。
[0123]
在一个实施例中，步骤s6中，根据更新后的符号网络的嵌入矩阵和噪声边节点集合，确定符号网络中每个节点所属社区，包括：
[0124]
步骤s61，根据更新后的符号网络的嵌入矩阵，采用k-means聚类算法，确定更新后的符号网络中各个节点所属社区；符号网络中的各个节点包括非噪声边节点和噪声边节点；
[0125]
步骤s62，更新后的符号网络的嵌入矩阵中包括多个节点对应的嵌入向量，根据非噪声边节点对应的嵌入向量，计算更新后的符号网络中各个社区的聚类中心；采用的公式如下：
[0126][0127]
其中，centi为第i个社区的聚类中心，ci表示的是网络中的第i个社区的节点集合，|ci|表示的是第i个社区中的节点数，zu表示的是节点u的嵌入向量。
[0128]
步骤s63，针对噪声边节点集合中的每个噪声边节点，确定当前噪声边节点与各个社区的聚类中心之间的相似度，将相似度最高的聚类中心所属社区作为重新确定的当前噪声边节点所属社区。这里，相似度可以采用欧式距离来计算。
[0129]
该实施例中，通过k-means聚类算法对更新后的符号网络进行粗粒度的划分，得到新的社区检测结果c，即各个节点所属社区，然后，针对噪声边节点进行细粒度的划分，重新确定噪声边节点所属社区，以替换k-means聚类算法得到的噪声边节点所属社区，得到准确的噪声边节点所属社区。
[0130]
基于与符号网络中噪声边感知的社区检测方法相同的发明构思，本实施例还提供与之对应的符号网络中噪声边感知的社区检测装置，图5示出了根据本技术实施例的符号网络中噪声边感知的社区检测装置的结构框图，包括：
[0131]
第一嵌入矩阵获取模块51，用于对符号网络的拓扑信息进行嵌入，得到符号网络的嵌入矩阵；
[0132]
噪声边确定模块52，用于基于符号网络的嵌入矩阵，确定符号网络中的噪声边集合和噪声边节点集合；
[0133]
符号网络更新模块53，用于根据噪声边集合对符号网络中的所有噪声边进行标记，得到更新后的符号网络；
[0134]
第二嵌入矩阵获取模块54，用于对更新后的符号网络的拓扑信息进行嵌入，得到
更新后的符号网络的嵌入矩阵；在嵌入过程中，忽略所有噪声边；
[0135]
节点所属社区确定模块55，用于根据更新后的符号网络的嵌入矩阵和噪声边节点集合，确定符号网络中每个节点所属社区。
[0136]
该实施例中，本技术感知符号网络中的噪声边并进行标记，在进行节点低维表示过程中忽略掉噪声边的信息，并通过目标函数使得网络中的正边节点对在嵌入空间中互相之间的距离短于负边节点对在嵌入空间中的距离，以获得高精准度的社区检测结果。
[0137]
在一个实施例中，噪声边确定模块52，还用于：
[0138]
针对符号网络的嵌入矩阵采用k-means聚类算法，确定符号网络中各个节点初步所属社区；
[0139]
根据符号网络中各个节点初步所属社区确定符号网络中的正关系噪声边集合和负关系噪声边集合；
[0140]
正关系噪声边集合和负关系噪声边集合构成噪声边集合，噪声边集合中所有噪声边两端的噪声边节点构成噪声边节点集合。
[0141]
在一个实施例中，节点所属社区确定模块55，还用于：
[0142]
根据更新后的符号网络的嵌入矩阵，采用k-means聚类算法，确定更新后的符号网络中各个节点所属社区；符号网络中的各个节点包括非噪声边节点和噪声边节点；
[0143]
更新后的符号网络的嵌入矩阵中包括多个节点对应的嵌入向量，根据非噪声边节点对应的嵌入向量，计算更新后的符号网络中各个社区的聚类中心；
[0144]
针对噪声边节点集合中的每个噪声边节点，确定当前噪声边节点与各个社区的聚类中心之间的相似度，将相似度最高的聚类中心所属社区作为重新确定的当前噪声边节点所属社区。
[0145]
为了验证本技术的符号网络中噪声边感知的社区检测方法及装置的有效性，将社区检测方法应用至符号社交网络数据集以测试该社区检测方法的性能，选取的数据集为：bitcoin_otc来自于专注于开放市场的站点，用户可以使用比特币买卖商品；wikirfa是由维基百科管理员候选人的投票来定义的；wikielec是维基百科管理员的选举和投票数据，其定义与wikirfa相似；ggsn是基于对新几内亚东部中部高地文化的研究而创建的，拥有真实的社区标签；spp展示了1994年斯洛文尼亚议会10个政党之间的关系。实验数据集属性情况如下表1所示：
[0146]
表1数据集介绍
[0147]
数据集节点数正边数负边数bitcoin_otc6006640587126wikielect712616412044208wikirfa1125828890282352spp103654ggs165858
[0148]
本技术提供的社区检测方法(nepcd算法)与现有技术的sne算法与sine算法搭配k-means聚类算法进行比较。sne通过节点的所有游走路径预测目标节点。sine通过优化满足结构平衡理论的目标函数来学习嵌入的多层神经网络。通过两种基线算法得到符号网络的嵌入矩阵，通过k-means聚类算法得到社区检测结果。nepcd算法同时会对符号网络中被
视为噪声边的边进行感知并忽略，重新进行节点嵌入以达到精准的社区划分的目的，在这里会证明对噪声边的忽略对社区检测精准度的重要性。在spp与ggs两个具有真实社区标签的数据集上验证nepcd算法与基线算法是否能够检测出正确的社区标签。
[0149]
图6示出了nepcd算法与基线算法在社区数为2-10时在数据集bitcoin_otc中的错误率对比图，图7示出了nepcd算法与基线算法在社区数为2-10时在数据集wikielect中的错误率对比图，图8示出了nepcd算法与基线算法在社区数为2-10时在数据集wikirfa中的错误率对比图；图9示出了nepcd算法与不进行噪声边感知去忽略的算法(non-nepcd算法)在社区数为2-10时在数据集bitcoin_otc中的错误率对比图，图10示出了nepcd算法与不进行噪声边感知去忽略的算法(non-nepcd算法)在社区数为2-10时在数据集wikielect中的错误率对比图，图11示出了nepcd算法与不进行噪声边感知去忽略的算法(non-nepcd算法)在社区数为2-10时在数据集wikirfa中的错误率对比图；图12示出了nepcd算法与与基线算法在数据集spp中的nmi值对比图，图13示出了nepcd算法与与基线算法在数据集ggs中的nmi值对比图；错误率表示的是社区之间的正边数与社区之内的负边数之和同网络中总边数的比值，错误率越低，表明本技术的社区检测算法对符号网络的社区精准都越高。nmi(normalized mutual information)，归一化互信息。常用在聚类中，度量两个聚类结果的相近程度(通常都是将聚类结果和真实标签进行比较相似程度)。值域是[0,1]，值越高表示两个聚类结果越相似。
[0150]
如图6、图7、图8所示，在社区数目不同的情况下，本技术提供的社区检测方法具有最低的错误率。
[0151]
对比图6、图7、图8，在不同数据集内，相比较于基线算法，在wikirfa数据集中社区数目为2时，sne算法的错误率略低于nepcd算法，在其于情况下nepcd的社区检测结果都是明显优于基线算法。
[0152]
如图9、图10、图11所示，在不同的社区数，本技术进行噪声边感知与忽略错误率显著低于不进行噪声边感知与忽略。
[0153]
对比图9、图10、图11，本技术在社区数目取为2-6时，优势并不明显，但在社区数目取为8-11时进行噪声边感知与忽略错误率显著低于不进行噪声边感知与忽略。
[0154]
为证明算法能够完美的对符号网络进行社区检测，分别使用两个具有真是社区标签的数据集spp、ggs通过nepcd算法与与基线算法进行社区检测。如图12和图13所示，nepcd能够完美的对两个社区进行社区检测，得到真实的社区标签，sne算法对spp数据集有较强的社区检测能力，对于ggs数据集则不能很好的进行社区检测，sine算法在两种数据集中的社区检测表现性能最差。实验证明，本技术能够很好的检测出符号网络中节点的真实社区标签。本技术提供的社区检测方法对噪声便进行感知与忽略，使社区检测结果的精准度得到大大提升。
[0155]
以上所述，仅为本技术的各种实施方式，但本技术的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本技术揭露的技术范围内，可轻易想到变化或替换，都应涵盖在本技术的保护范围之内。因此，本技术的保护范围应以所述权利要求的保护范围为准。

技术特征：
1.一种符号网络中噪声边感知的社区检测方法，其特征在于，包括：对所述符号网络的拓扑信息进行嵌入，得到所述符号网络的嵌入矩阵；基于所述符号网络的嵌入矩阵，确定所述符号网络中的噪声边集合和噪声边节点集合；根据所述噪声边集合对所述符号网络中的所有噪声边进行标记，得到更新后的符号网络；对所述更新后的符号网络的拓扑信息进行嵌入，得到所述更新后的符号网络的嵌入矩阵；在所述嵌入过程中，忽略所述所有噪声边；根据所述更新后的符号网络的嵌入矩阵和所述噪声边节点集合，确定所述符号网络中每个节点所属社区。2.如权利要求1所述的方法，其特征在于，其中，对所述符号网络的拓扑信息进行嵌入，得到所述符号网络的嵌入矩阵，包括：确定所述符号网络中每个节点的正边邻居集合和负边邻居集合；根据所述每个节点的正边邻居集合和负边邻居集合，对所述符号网络的拓扑信息进行嵌入，得到所述符号网络的嵌入矩阵。3.如权利要求2所述的方法，其特征在于，其中，根据所述每个节点的正边邻居集合和负边邻居集合，对所述符号网络的拓扑信息进行嵌入，得到所述符号网络的嵌入矩阵，包括：根据所述每个节点的正边邻居集合和负边邻居集合，确定所述每个节点的嵌入向量；将所有节点的嵌入向量进行连接，得到所述符号网络的嵌入矩阵。4.如权利要求3所述的方法，其特征在于，其中，根据所述每个节点的正边邻居集合和负边邻居集合，确定所述每个节点的嵌入向量，包括：对于节点u，当聚合一跳邻居的信息时，节点u的一跳邻居的平衡集合嵌入矩阵和非平衡集合嵌入矩阵采用以下公式：衡集合嵌入矩阵采用以下公式：其中，为节点u的一跳邻居的平衡集合嵌入矩阵，为节点u的一跳邻居的非平衡集合嵌入矩阵，σ(
·
)为激活函数，为节点u的一跳邻居的平衡游走路径b
u
(1)的权重，为节点u的一跳邻居的非平衡游走路径u
u
(1)的权重，为节点u的正边邻居集合，|
·
|为集合大小，为节点u的负边邻居集合，为节点v的隐藏表示，为节点u的隐藏表示；当聚合多跳邻居的信息时，节点u的多跳邻居的平衡集合嵌入矩阵和非平衡集合嵌入
矩阵采用以下公式：矩阵采用以下公式：其中，为节点u的h跳邻居的平衡集合嵌入矩阵，为节点u的h跳邻居的非平衡集合嵌入矩阵，σ(
·
)为激活函数，为节点u的h跳邻居的平衡游走路径b
u
(h)的权重，为节点u的h跳邻居的非平衡游走路径u
u
(h)的权重，|
·
|为集合大小，为节点v的h-1跳邻居的平衡集合嵌入矩阵，为节点v的h-1跳邻居的非平衡集合嵌入矩阵，为节点k的h-1跳邻居的非平衡集合嵌入矩阵，为节点k的h-1跳邻居的平衡集合嵌入矩阵，为节点u的h-1跳邻居的平衡集合嵌入矩阵，节点u的h-1跳邻居的非平衡集合嵌入矩阵；当聚合一跳邻居的信息时，将节点u的一跳邻居的平衡集合嵌入矩阵和非平衡集合嵌入矩阵连接在一起，得到节点u的嵌入向量；当聚合多跳邻居的信息时，将节点u的多跳邻居的平衡集合嵌入矩阵和非平衡集合嵌入矩阵连接在一起，得到节点u的嵌入向量。5.如权利要求1所述的方法，其特征在于，其中，基于所述符号网络的嵌入矩阵，确定所述符号网络中的噪声边集合和噪声边节点集合，包括：针对所述符号网络的嵌入矩阵采用k-means聚类算法，确定所述符号网络中各个节点初步所属社区；根据所述符号网络中各个节点初步所属社区确定所述符号网络中的正关系噪声边集合和负关系噪声边集合；所述正关系噪声边集合和所述负关系噪声边集合构成噪声边集合，所述噪声边集合中所有噪声边两端的噪声边节点构成噪声边节点集合。6.如权利要求5所述的方法，其特征在于，其中，根据所述符号网络中各个节点初步所属社区确定所述符号网络中的正关系噪声边集合和负关系噪声边集合，采用以下公式：其中，n
e,pos
为正关系噪声边集合，ε
uv
为节点u和节点v之间的边，a
+
为符号网络中的正边集合，label
u
为节点u所属社区，label
v
为节点v所属社区，若节点u与节点v属于同一个社区，δ(label
u
,label
v
)的结果值为1，若节点u与节点v不属于同一个社区，δ(label
u
,label
v
)的结果值为0；triangle
balance
为符号网络中的平衡三角形集合；
其中，n
e,neg
为负关系噪声边集合，a-为符号网络中的负边集合。7.如权利要求1所述的方法，其特征在于，其中，根据所述更新后的符号网络的嵌入矩阵和所述噪声边节点集合，确定所述符号网络中每个节点所属社区，包括：根据所述更新后的符号网络的嵌入矩阵，采用k-means聚类算法，确定所述更新后的符号网络中各个节点所属社区；所述符号网络中的各个节点包括非噪声边节点和噪声边节点；所述更新后的符号网络的嵌入矩阵中包括多个节点对应的嵌入向量，根据所述非噪声边节点对应的嵌入向量，计算所述更新后的符号网络中各个社区的聚类中心；针对所述噪声边节点集合中的每个噪声边节点，确定当前噪声边节点与所述各个社区的聚类中心之间的相似度，将所述相似度最高的聚类中心所属社区作为重新确定的所述当前噪声边节点所属社区。8.一种符号网络中噪声边感知的社区检测装置，其特征在于，包括：第一嵌入矩阵获取模块，用于对所述符号网络的拓扑信息进行嵌入，得到所述符号网络的嵌入矩阵；噪声边确定模块，用于基于所述符号网络的嵌入矩阵，确定所述符号网络中的噪声边集合和噪声边节点集合；符号网络更新模块，用于根据所述噪声边集合对所述符号网络中的所有噪声边进行标记，得到更新后的符号网络；第二嵌入矩阵获取模块，用于对所述更新后的符号网络的拓扑信息进行嵌入，得到所述更新后的符号网络的嵌入矩阵；在所述嵌入过程中，忽略所述所有噪声边；节点所属社区确定模块，用于根据所述更新后的符号网络的嵌入矩阵和所述噪声边节点集合，确定所述符号网络中每个节点所属社区。9.如权利要求8所述的装置，其特征在于，所述噪声边确定模块，还用于：针对所述符号网络的嵌入矩阵采用k-means聚类算法，确定所述符号网络中各个节点初步所属社区；根据所述符号网络中各个节点初步所属社区确定所述符号网络中的正关系噪声边集合和负关系噪声边集合；所述正关系噪声边集合和所述负关系噪声边集合构成噪声边集合，所述噪声边集合中所有噪声边两端的噪声边节点构成噪声边节点集合。10.如权利要求8所述的装置，其特征在于，所述节点所属社区确定模块，还用于：根据所述更新后的符号网络的嵌入矩阵，采用k-means聚类算法，确定所述更新后的符号网络中各个节点所属社区；所述符号网络中的各个节点包括非噪声边节点和噪声边节点；所述更新后的符号网络的嵌入矩阵中包括多个节点对应的嵌入向量，根据所述非噪声边节点对应的嵌入向量，计算所述更新后的符号网络中各个社区的聚类中心；针对所述噪声边节点集合中的每个噪声边节点，确定当前噪声边节点与所述各个社区的聚类中心之间的相似度，将所述相似度最高的聚类中心所属社区作为重新确定的所述当前噪声边节点所属社区。

技术总结
本申请涉及一种符号网络中噪声边感知的社区检测方法，包括：确定符号网络中的噪声边集合和噪声边节点集合；对符号网络中的所有噪声边进行标记，得到更新后的符号网络；对更新后的符号网络的拓扑信息进行嵌入，得到更新后的符号网络的嵌入矩阵，在嵌入过程中，忽略所有噪声边；根据更新后的符号网络的嵌入矩阵和噪声边节点集合，确定符号网络中每个节点所属社区。本申请考虑到符号网络中噪声边对社区检测的影响，感知忽略噪声边，结合平衡理论，并考虑到社区结构存在非平衡态与弱平衡态，从而允许属于平衡三角形的负边位于社区内部，允许属于平衡三角形的正边位于两个社区之间，从而降低了符号网络中噪声边的影响并提高了社区检测的精准度。测的精准度。测的精准度。


技术研发人员：尹小燕 王季 贺帅帅 龚志敏 崔瑾 陈晓江 房鼎益
受保护的技术使用者：西北大学
技术研发日：2023.03.22
技术公布日：2023/7/12