基于结构相似的局部社区发现方法及系统与流程

1.本发明涉及社交网络分析领域，具体涉及基于结构相似的局部社区发现方法及系统。


背景技术：

2.社区发现是一种旨在发现社交网络、交通网络、引文网络和生物网络等复杂网络中的社区结构的重要技术，对于理解这些复杂网络的特征非常重要。社交网络已成为人们生活中重要的交流和信息获取渠道，而且社交网络分析是一种研究社交网络中人际关系、信息传播和社会互动等研究领域。社交网络是一个由许多节点和边组成的图形结构，其中节点代表用户，边代表用户之间的关系。在社交网络中，可以将节点可以被划分为不同的社区，同一个社区内节点之间的联系相对紧密，不同社区之间的节点之间的联系相对稀疏，同一个社区内的节点在社交网络中通常有类似的兴趣和行为。例如公布号为cn103729467a的现有发明专利申请文献《一种社交网络中的社区结构发现方法》，该方法包括以下步骤：步骤一：将社交网络转换为邻接矩阵形式，如果两个节点之间存在边，那么相对应的元素为1，否则为0；步骤二：利用随机游走理论对邻接矩阵进行处理，得到新的节点度数p-degree以及边权值p-weight；步骤三：根据新的节点度数p-degree得到社交网络中的领袖节点；步骤四：基于领袖节点生成子社区，并通过对子社区的一系列操作来进行社区发现。前述传统的全局社区发现方法通常基于网络的全局信息将网络划分成若干个社区，在现实应用中，很难去获取网络的全局信息或者不可能获取网络的全局信息，且这些全局社区发现方法难以发现隐藏在网络中的局部社区，时间和空间复杂度相对较高。传统的局部社区发现方法主要基于节点之间的相似性和连接性进行分析，如k-means和谱聚类等社区发现方法，例如公布号为cn108647739a的现有发明专利申请文献《一种基于改进的密度峰值聚类的社交网络社区发现方法》，该方法首先为网络中的每个用户计算两个指标：局部密度和相对距离，其中局部密度的计算采用高斯核密度估计，而相对距离则表示用户与密度比它大而离它最近的点之间的距离。然后，基于高斯分布选取局部密度很大且相对距离相对较大的点作为社区中心，剩余的非中心点则被分配到密度比它大而离它最近的点所在的社区当中。最后，基于合并因子来度量两个社区之间的距离，合并因子大于给定阈值的社区被合并为一个社区。然而，这些局部社区发现方法在处理复杂的社交网络时面临着许多挑战，例如网络结构复杂、节点之间的联系难以捕捉、社区的大小和形状不确定等问题。因此，需要提出一种新的局部社区发现方法，以更好地解决这些挑战。基于对全局社区和局部社区发现算法的分析。
3.综上，现有技术存在隐藏局部社区发现困难、时空复杂度相对较高、复杂社交网络中节点所在局部社区检测难度大的技术问题。


技术实现要素：

4.本发明所要解决的技术问题在于如何解决隐藏局部社区发现困难、时空复杂度相
对较高、复杂社交网络中节点所在局部社区检测难度大的技术问题。
5.本发明是采用以下技术方案解决上述技术问题的：基于结构相似的局部社区发现方法包括：
6.s1、从预置网络图中选定源节点，以作为给定节点；
7.s2、获取其余节点与给定节点的公共邻居数，以选取与给定节点的公共邻居数最多的节点，以作为待添加节点；
8.s3、获取给定节点所在的给定局部社区，将待添加节点添加至给定局部社区，据以获取给定局部社区的邻居节点集；
9.s4、提取k-clique结构诱导子图；
10.s5、获取候选社区诱导图，根据邻居节点集，计算k-clique结构诱导子图与候选社区有导图之间的社区结构相似性值，根据社区结构相似性值，扩展给定局部社区，以得到适用社区以及适用图；
11.s6、计算给定节点以外节点与适用社区图之间的相似度，据以扩展相似社区，以得到相似局部社区。
12.本发明通过最短路径核计算k-clique结构和候选社区之间的结构相似性以及用节点的公共邻居数计算节点与社区之间的结构相似度来发现任意给定节点所在的局部社区，基于结构相似的局部社区的扩展，可以充分利用结构相似信息来检测任意给定节点所在的局部社区，来提高局部社区发现的准确性。
13.在更具体的技术方案中，步骤s1中，预置网络图为无向无权图：
14.g＝(v,e)
15.式中，v＝{v1,v2,
……
,v
n-1
,vn}表示图g中节点集合，e＝{e,e2,
……
,e
n-1
,en}表示图g边集合。
16.在更具体的技术方案中，步骤s2包括：
17.s21、利用下述逻辑，求取待添加节点u：
[0018][0019]
式中，n(v0)表示节点v0的邻居节点集合，|n(u)∩n(v0)|表示两个邻居节点集中交集的个数；
[0020]
s22、利用待添加节点以及给定节点，以构建起始节点集。
[0021]
在更具体的技术方案中，步骤s3包括：
[0022]
s31、获取并存储给定节点所在的局部社区；
[0023]
s32、将给定节点v0和待添加节点u添加至局部社区；
[0024]
s33、利用预置逻辑计算给定节点v0和待添加节点u，以得到局部社区的邻居节点集。
[0025]
本发明首先从网络中任意选择一个节点为给定种子节点，接着从给定种子节点的邻居节点集中挑选与给定种子节点公共邻居数最多的节点，仅利用给定节点所在的局部结构来检测任意给定节点所在的局部社区，未利用网络的全局信息，时间和空间复杂度相对较低。
[0026]
在更具体的技术方案中，步骤s33中，利用下述逻辑求取邻居节点集：
[0027]
n(c)＝n(v0)∪n(u)-c
[0028]
(2)
[0029]
在更具体的技术方案中，步骤s5包括：
[0030]
s51、以k-clique结构诱导子图与候选社区有导图作为图对，利用图核技术计算图对之间的图结构相似性；
[0031]
s52、给定不少于2个的无向权图，据以获取无向权图的最短路径图，以求取无向权图结构相似性；
[0032]
s53、根据无向权图结构相似性，计算第一社区相似性；
[0033]
s54、定义局部模块度m，利用预置模块度处理逻辑计算局部模块度m；
[0034]
s55、初始化平均社区相似性值以及局部社区模块度初始值；
[0035]
s56、计算邻居节点集中，每个节点的第二社区相似性；
[0036]
s57、根据第一社区相似性及第二社区相似性，处理得到给定节点所在的适用社区以及适用图。
[0037]
本发明基于图对之间的结构相似性和图与节点之间的结构相似度来进行局部社区的扩展，利用最短路径核计算k-clique结构和候选社区之间的社区结构相似性来扩展局部社区，最后通过节点的公共邻居数计算节点和候选社区之间的结构相似度来完善局部社区的扩展，最终获得的一个结构内聚性好的局部社区。
[0038]
在更具体的技术方案中，步骤s52中，利用下述逻辑求取无向权图结构相似性：
[0039][0040]
式中，sp()表示最短路径核，e
′1和e
′2表示g
′1和g
′2的边集，表示边路径长度1的正定核。
[0041]
在更具体的技术方案中，步骤s53中，利用下述逻辑，计算第一社区相似性：
[0042]
sc(v,gk)＝sp(g
c∪{v}
,gk)
[0043]
(4)
[0044]
式中，gk表示k-clique结构的诱导图，g
c∪{v}
表示n(c)中节点v和社区c的社区诱导图。
[0045]
在更具体的技术方案中，步骤s54中，利用预置模块度处理逻辑计算局部模块度m：
[0046][0047]
式中，e
in
表示局部社区c内部节点之间边的数量，e
out
表示局部社区c中节点和n(c)中节点之间有连边的数量。
[0048]
在更具体的技术方案中，基于结构相似的局部社区发现系统包括：
[0049]
源节点选定模块，用以从预置网络图中选定源节点，以作为给定节点；
[0050]
待添加节点获取模块，用以获取其余节点与给定节点的公共邻居数，以选取与给定节点的公共邻居数最多的节点，以作为待添加节点，待添加节点获取模块与源节点选定模块连接；
[0051]
邻居节点集获取模块，用以获取给定节点所在的给定局部社区，将待添加节点添加至给定局部社区，据以获取给定局部社区的邻居节点集，邻居节点集获取模块与待添加节点获取模块及源节点选定模块连接；
[0052]
诱导图提取模块，用以提取k-clique结构诱导子图；
[0053]
社区相似性计算模块，用以获取候选社区诱导图，根据邻居节点集，计算k-clique结构诱导子图与候选社区有导图之间的社区结构相似性值，根据社区结构相似性值，扩展给定局部社区，以得到适用社区以及适用图，图对相似性计算模块与诱导图提取模块连接；
[0054]
局部社区扩展模块，用以计算给定节点以外节点与适用社区图之间的相似度，据以扩展相似社区，以得到相似局部社区，局部社区扩展模块与社区相似性计算模块连接。
[0055]
本发明相比现有技术具有以下优点：本发明通过最短路径核计算k-clique结构和候选社区之间的结构相似性以及用节点的公共邻居数计算节点与社区之间的结构相似度来发现任意给定节点所在的局部社区，基于结构相似的局部社区的扩展，可以充分利用结构相似信息来检测任意给定节点所在的局部社区，来提高局部社区发现的准确性。
[0056]
本发明首先从网络中任意选择一个节点为给定种子节点，接着从给定种子节点的邻居节点集中挑选与给定种子节点公共邻居数最多的节点，仅利用给定节点所在的局部结构来检测任意给定节点所在的局部社区，未利用网络的全局信息，时间和空间复杂度相对较低。
[0057]
本发明基于图对之间的结构相似性和图与节点之间的结构相似度来进行局部社区的扩展，利用最短路径核计算k-clique结构和候选社区之间的社区结构相似性来扩展局部社区，最后通过节点的公共邻居数计算节点和候选社区之间的结构相似度来完善局部社区的扩展，最终获得的一个结构内聚性好的局部社区。
[0058]
本发明解决了现有技术中存在的隐藏局部社区发现困难、时空复杂度相对较高、复杂社交网络中节点所在局部社区检测难度大的技术问题。
附图说明
[0059]
图1为本发明实施例1的基于结构相似的局部社区发现方法基本步骤示意图；
[0060]
图2为本发明实施例1的将节点添加到局部社区的具体步骤示意图；
[0061]
图3为本发明实施例1的图对之间相似性扩展社区具体步骤示意图。
具体实施方式
[0062]
为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0063]
实施例1
[0064]
如图1所示，本发明提供的基于结构相似的局部社区发现方法，包括以下基本步骤：
[0065]
s1、任意选择源节点；
[0066]
在本实施例中，从网络图g上任意选定一个节点为给定节点v0。
[0067]
在本实施例中，给定一个无向无权图g＝(v,e)，其中的v＝{v1,v2,
……
,v
n-1
,vn}表示图g中节点集合，e＝{e,e2,
……
,e
n-1
,en}表示图g边集合，从图g上任意选择一个节点v0为给定源节点。
[0068]
s2、选择源节点公共邻居数最多的节点；
[0069]
在本实施例中，结合s1中的给定节点v0，从给定节点v0的邻居节点集中挑选与节点v0的公共邻居数最多的节点u。
[0070]
在本实施例中，为了避免种子依赖问题，将节点v0与节点v0公共邻居数最多的节点u作为基于结构相似的局部社区发现方法的起始节点集，求节点v0公共邻居数最多的节点u计算公式如公式(1)所示。
[0071][0072]
其中，的n(v0)表示节点v0的邻居节点集合，|n(u)∩n(v0)|表示两个邻居节点集中交集的个数。
[0073]
s3、将前述步骤s1及步骤s2中的节点添加到局部社区；
[0074]
在本实施例中，结合s1和s2，初始化一个空列表c，将节点v0和u添加到c中。
[0075]
如图2所示，在本实施例中，将节点添加到局部社区的步骤s3包括：
[0076]
s31、获取并存储任意给定节点所在的局部社区；
[0077]
在本实施例中，初始化一个空列表c，用来存储任意给定节点v0所在的局部社区；
[0078]
s32、将任意给定节点和公共邻居数最多的节点添加至局部社区；
[0079]
在本实施例中，将s11中的节点v0和s21中节点u一起添加到局部社区c中；
[0080]
s33、计算局部社区的邻居节点集；
[0081]
在本实施例中，局部社区c的邻居节点集n(c)的计算公式如公式(2)所示。
[0082]
n(c)＝n(v0)∪n(u)-c#(2)
[0083]
s4、提取k-clique诱导子图；
[0084]
在本实施例中，设gk表示k-clique结构形式的图结构，gc表示局部社区c结构形式的图结构，g
c∪{v}
表示c中的邻居节点v和c组成的图结构。gk、gc和g
c∪{v}
表示的图结构是计算社区相似性对应的诱导子图。
[0085]
s5、图对之间相似性扩展社区；
[0086]
在本实施例中，通过用最短路径核计算k-clique结构诱导图和候选社区诱导图之间社区结构相似性值，来扩展局部社区c。
[0087]
如图3所示，在本实施例中，图对之间相似性扩展社区的步骤s5包括：
[0088]
s51、利用图核技术中的最短路径核计算图对之间的结构相似性；
[0089]
在本实施例中，最短路径核是通过使用最短路径图计算图对之间的相似性，给定一个无向图g＝(v,e)，图g的最短路径图的表示形式为g
′
＝(v,e
′
)，其中对于任意节点u,v∈v，g
′
中节点u和节点v之间边的权重为节点u和节点v的最短路径长度。
[0090]
s52、给定两个无向权图，获取给定无向权图的最短路径图，计算无向权图之间的结构相似性；
[0091]
给定两个无向无权图g1＝(v1,e1)和g2＝(v2,e2)，从s51中可以知道图g1和g2的最短路径图的表示形式为g
′1＝(v
′1,e
′1)和g
′2＝(v
′2,e
′2)，基于最短路径图g
′1和g
′2，则通过最
短路径核计算图g1和g2之间结构相似性的公式如公式(3)所示。
[0092][0093]
其中的sp()表示最短路径核，e
′1和e
′2表示g
′1和g
′2的边集，表示边路径长度1的正定核。
[0094]
s53、计算社区相似性；
[0095]
在本实施例中，社区相似性的计算公式如公式(4)所示。
[0096]
sc(v,gk)＝sp(g
c∪{v}
,gk)#(4)
[0097]
其中，gk表示k-clique结构的诱导图，g
c∪{v}
表示n(c)中节点v和社区c的社区诱导图。
[0098]
s54、定义并计算局部模块度m；
[0099]
在本实施例中，定义一个局部模块度m来评估局部社区c的质量，社区c局部模块度m值越大，表示局部社区m的质量越高，模块度m的计算公式如公式(5)所示。
[0100][0101]
其中，e
in
表示局部社区c内部节点之间边的数量，e
out
表示局部社区c中节点和n(c)中节点之间有连边的数量。
[0102]
s55、初始化一个平均社区相似性值s
′c，平均社区相似性值s
′c初始值设为0，局部社区c的模块度m
max
初始值为0；
[0103]
s56、计算邻居节点集中每个节点的社区相似性；
[0104]
在本实施例中，计算邻居节点集n(c)中的每个节点v的社区相似性sc(v,gk)，选择社区相似性值最大的，判断是否大于s
′c，如果大于，然后用公式(5)计算候选社区c∪{v}的局部模块度mv是否大于m
max
，如果大于，将相应节点加入到局部社区c中，同时更新m
max
为mv，s
′c更新为添加到局部社区c中所有节点的sc(v,gk)的平均值。将社区相似性值sc(v,gk)最大的节点加入到局部社区c中。
[0105]
s57、在重复s56步骤的操作，当sc(v,g
cg
)小于s
′c，sc(v,gcg)大于或等于s’c则跳出s56步骤。
[0106]
s58、利用前述循环，获得给定节点v0所在的局部社区c。
[0107]
s6、图和节点之间相似度扩展社区。
[0108]
在本实施例中，结合前述步骤s5中获得的局部社区c，通过节点公共邻居数计算节点和社区之间的结构相似度，来扩展局部社区c。
[0109]
综上，本发明通过最短路径核计算k-clique结构和候选社区之间的结构相似性以及用节点的公共邻居数计算节点与社区之间的结构相似度来发现任意给定节点所在的局部社区，基于结构相似的局部社区的扩展，可以充分利用结构相似信息来检测任意给定节点所在的局部社区，来提高局部社区发现的准确性。
[0110]
本发明首先从网络中任意选择一个节点为给定种子节点，接着从给定种子节点的邻居节点集中挑选与给定种子节点公共邻居数最多的节点，仅利用给定节点所在的局部结构来检测任意给定节点所在的局部社区，未利用网络的全局信息，时间和空间复杂度相对较低。
[0111]
本发明基于图对之间的结构相似性和图与节点之间的结构相似度来进行局部社区的扩展，利用最短路径核计算k-clique结构和候选社区之间的社区结构相似性来扩展局部社区，最后通过节点的公共邻居数计算节点和候选社区之间的结构相似度来完善局部社区的扩展，最终获得的一个结构内聚性好的局部社区。
[0112]
本发明解决了现有技术中存在的隐藏局部社区发现困难、时空复杂度相对较高、复杂社交网络中节点所在局部社区检测难度大的技术问题。
[0113]
以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。

技术特征：
1.基于结构相似的局部社区发现方法，其特征在于，所述方法包括：s1、从预置网络图中选定源节点，以作为给定节点；s2、获取其余节点与所述给定节点的公共邻居数，以选取与所述给定节点的所述公共邻居数最多的节点，以作为待添加节点；s3、获取所述给定节点所在的给定局部社区，将所述待添加节点添加至所述给定局部社区，据以获取所述给定局部社区的邻居节点集；s4、提取k-clique结构诱导子图；s5、获取候选社区诱导图，根据所述邻居节点集，计算所述k-clique结构诱导子图与所述候选社区有导图之间的社区结构相似性值，根据所述社区结构相似性值，扩展所述给定局部社区，以得到适用社区以及适用图；s6、计算所述给定节点以外节点与所述适用社区图之间的相似度，据以扩展所述相似社区，以得到相似局部社区。2.根据权利要求1所述的基于结构相似的局部社区发现方法，其特征在于，所述步骤s1中，所述预置网络图为无向无权图：g＝(v,e)式中，v＝{v1,v2,
……
,v
n-1
,v
n
}表示图g中节点集合，e＝{e,e2,
……
,e
n-1
,e
n
}表示图g边集合。3.根据权利要求1所述的基于结构相似的局部社区发现方法，其特征在于，所述步骤s2包括：s21、利用下述逻辑，求取所述待添加节点u：式中，n(v0)表示节点v0的邻居节点集合，|n(u)∩n(v0)|表示两个邻居节点集中交集的个数；s22、利用所述待添加节点以及所述给定节点，以构建所述起始节点集。4.根据权利要求1所述的基于结构相似的局部社区发现方法，其特征在于，所述步骤s3包括：s31、获取并存储所述给定节点所在的局部社区；s32、将所述给定节点v0和所述待添加节点u添加至局部社区；s33、利用预置逻辑计算所述给定节点v0和所述待添加节点u，以得到所述局部社区的所述邻居节点集。5.根据权利要求1所述的基于结构相似的局部社区发现方法，其特征在于，所述步骤s33中，利用下述逻辑求取所述邻居节点集：n(c)＝n(v0)∪n(u)-c
ꢀꢀꢀꢀꢀ
(2)。6.根据权利要求1所述的基于结构相似的局部社区发现方法，其特征在于，所述步骤s5包括：s51、以所述k-clique结构诱导子图与所述候选社区有导图作为图对，利用图核技术计算所述图对之间的图结构相似性；
s52、给定不少于2个的无向权图，据以获取所述无向权图的最短路径图，以求取无向权图结构相似性；s53、根据所述无向权图结构相似性，计算第一社区相似性；s54、定义局部模块度m，利用预置模块度处理逻辑计算所述局部模块度m；s55、初始化平均社区相似性值以及局部社区模块度初始值；s56、计算所述邻居节点集中，每个节点的第二社区相似性；s57、根据所述第一社区相似性及所述第二社区相似性，处理得到所述给定节点所在的所述适用社区以及所述适用图。7.根据权利要求1所述的基于结构相似的局部社区发现方法，其特征在于，所述步骤s52中，利用下述逻辑求取无向权图结构相似性：式中，sp()表示最短路径核，e
′1和e
′2表示g
′1和g
′2的边集，表示边路径长度1的正定核。8.根据权利要求1所述的基于结构相似的局部社区发现方法，其特征在于，所述步骤s53中，利用下述逻辑，计算所述第一社区相似性：s
c
(v，g
k
)＝sp(g
c∪{v}
，g
k
)
ꢀꢀꢀꢀꢀ
(4)式中，g
k
表示k-clique结构的诱导图，g
c∪{v}
表示n(c)中节点v和社区c的社区诱导图。9.基于结构相似的局部社区发现方法，其特征在于，所述步骤s54中，利用预置模块度处理逻辑计算所述局部模块度m：式中，e
in
表示局部社区c内部节点之间边的数量，e
out
表示局部社区c中节点和n(c)中节点之间有连边的数量。10.基于结构相似的局部社区发现系统，其特征在于，所述系统包括：源节点选定模块，用以从预置网络图中选定源节点，以作为给定节点；待添加节点获取模块，用以获取其余节点与所述给定节点的公共邻居数，以选取与所述给定节点的所述公共邻居数最多的节点，以作为待添加节点，所述待添加节点获取模块与所述源节点选定模块连接；邻居节点集获取模块，用以获取所述给定节点所在的给定局部社区，将所述待添加节点添加至所述给定局部社区，据以获取所述给定局部社区的邻居节点集，所述邻居节点集获取模块与所述待添加节点获取模块及所述源节点选定模块连接；诱导图提取模块，用以提取k-clique结构诱导子图；社区相似性计算模块，用以获取候选社区诱导图，根据所述邻居节点集，计算所述k-clique结构诱导子图与所述候选社区有导图之间的社区结构相似性值，根据所述社区结构相似性值，扩展所述给定局部社区，以得到适用社区以及适用图，所述图对相似性计算模块与所述诱导图提取模块连接；局部社区扩展模块，用以计算所述给定节点以外节点与所述适用社区图之间的相似
度，据以扩展所述相似社区，以得到相似局部社区，所述局部社区扩展模块与所述社区相似性计算模块连接。

技术总结
本发明提供基于结构相似的局部社区发现方法及系统，方法包括：首先从网络中任意选择一个节点为给定种子节点，接着从给定种子节点的邻居节点集中挑选与给定种子节点公共邻居数最多的节点，然后利用最短路径核计算k-clique结构和候选社区之间的社区结构相似性来扩展局部社区，最后通过节点的公共邻居数计算节点和候选社区之间的结构相似度来完善局部社区的扩展。本发明解决了隐藏局部社区发现困难、时空复杂度相对较高、复杂社交网络中节点所在局部社区检测难度大的技术问题。点所在局部社区检测难度大的技术问题。点所在局部社区检测难度大的技术问题。


技术研发人员：曹骞 陈佩树 陈兴 王愿 彭维才 卜华龙 吴其林 谈京
受保护的技术使用者：安徽省模式识别信息技术有限公司
技术研发日：2023.06.05
技术公布日：2023/9/9