1.一种基于子图电导的社区搜索方法,其特征在于,包括下述步骤:
S1:获取社交网络图,采用广度优先搜索从社交网络图中采样得到社交子图;
S2:在社交子图中选择包含查询顶点的多个最大团作为初始社区;
S3:在每个初始社区中添加能降低初始社区电导的用户节点,得到多个完整社区;得到完整社区的过程包括:S31:设置单次节点加入阈值count,初始化单次节点加入数为0,计算加入邻居节点后初始社区的质量评分;
S32:选择质量评分最大的邻居节点加入当前社区,单次节点加入数加1并计算加入邻居节点后社区的质量增益;
S33:若单次节点加入数不大于count且质量增益小于0,则计算加入邻居节点后社区的质量评分,返回步骤S32,直到质量增益大于0,完成一次用户节点添加;
S34:若单次节点加入数不大于count且质量增益大于0,则计算加入邻居节点后社区的质量评分,返回步骤S32,完成一次用户节点添加;
S35:若单次节点加入数达到count且质量增益小于0,或者无邻居节点,则去除最近一次添加的用户节点,得到完整社区;
S4:对完整社区进行边界修剪,得到多个高质量社区;
S5:从多个高质量社区选择性能最好的高质量社区作为最终的社区搜索结果。
2.根据权利要求1所述的一种基于子图电导的社区搜索方法,其特征在于,所述步骤S1中,从社交网络图中采样得到社交子图的过程包括:S11:初始化最大深度dp,最小阈值l和最大阈值h;
S12:将查询顶点放入子图顶点集合,并记录集合深度为0;
S13:遍历子图顶点集合中的用户节点的邻居节点;将邻居节点加入子图顶点集合,将邻居节点与用户节点的连边加入边集合中,当前子图顶点集合深度加一;
S14:判断子图顶点集合中的用户节点数是否达到最小阈值l且达到最大深度dp,若是,保存当前子图顶点集合和对应的边集合,否则,返回步骤S13;
S15:判断子图顶点集合中的用户节点数是否超过最大阈值h,若是,得到子图顶点集合和对应的边集合,即社交子图;否则,返回步骤S13。
3.根据权利要求1所述的一种基于子图电导的社区搜索方法,其特征在于,所述步骤S2中,选择的多个最大团表示为:其中,initialCom表示初始社区集合,clique表示初始社区集合中的非重叠最大团,cliquei和cliquej分别表示initialCom中第i个和第j个非重叠最大团,I表示第i个和第j个非重叠最大团的交集,q表示查询顶点。
4.根据权利要求1所述的一种基于子图电导的社区搜索方法,其特征在于,计算社区的质量评分的公式为:其中,f(S)表示社区S的质量评分,Din(S,S)表示S的内部度数之和, 表示社区S与社区的补集 的割边数量。
5.根据权利要求1所述的一种基于子图电导的社区搜索方法,其特征在于,计算加入邻居节点后社区的质量增益的公式为:Δf(S∪Ai)=f(S∪Ai)‑f(S)
其中,Δf(S∪Ai)表示添加节点集合Ai中的邻居节点后的社区S的质量增益,f(S∪Ai)表示添加节点集合Ai中的邻居节点后的社区S的质量评分,f(S)表示社区S的质量评分,Din(S,S)表示S的内部度数之和,Din(S,Ai)表示S与Ai之间的度数之和, 表示社区S与社区的补集 的割边数量,Eout(Ai)表示第一中间参数, 表示 与Ai之间的割边数量,Eout(S,Ai)表示S与Ai之间的割边数量。
6.根据权利要求1所述的一种基于子图电导的社区搜索方法,其特征在于,所述步骤S4中,对完整社区进行边界修剪的过程包括:S41:获取完整社区中的不包括查询顶点且至少存在一条边在剩余社区中的所有用户节点组成的边界顶点集合;
S42:遍历边界顶点集合中的用户节点,判断移除用户节点后社区是否能保持社区连通性,若能保持连通性,计算移除该用户节点后的社区的质量增益并剔除使社区质量增益大于0的用户节点,否则,保持该用户节点;遍历完成后,得到高质量社区。
7.根据权利要求6所述的一种基于子图电导的社区搜索方法,其特征在于,计算移除用户节点后的社区的质量增益的公式为:Δf(S‑Bj)=f(S‑Bj)‑f(S)
其中,Δf(S‑Bj)表示移除顶点集合Bj后社区的质量增益,f(S‑Bj)表示移除顶点集合Bj后社区的质量评分,f(S)表示社区S的质量评分,Din(S,S)表示S的内部度数和,Din(S,Bj)表示S与Bj之间的度数之和, 表示社区S与社区的补集 的割边数量,Eout(Bj)表示第二中间参数,Bj表示含有j个用户节点的顶点集合, 表示 与Bj之间的割边数量,Eout(S,Bj)表示S与Bj之间的割边数量。
8.根据权利要求1所述的一种基于子图电导的社区搜索方法,其特征在于,所述步骤S5中,从多个高质量社区选择性能最好的高质量社区的过程包括:计算每个高质量社区的电导,将电导值最小的高质量社区作为最终的社区搜索结果。