一种社交网络中社区结构的检测方法

摘要

本发明公开了一种社交网络中社区结构的检测方法，包括：分析社交网络的拓扑结构，根据拓扑结构信息构建加权社交网络；定义社区结构的核挖掘策略，识别所有社区结构的核；构建基于集成学习的社区结构模型，所述社区结构模型结合了基于有监督学习的投票回归模型和若干个基于无监督学习社区结构的拓扑属性；设计启发式图搜索策略，用于扩展社区结构的核进而形成社交网络中完整的社区结构，根据得到的社区结构对用户进行社区分组，并根据分组结果进行相应的内容推送。本发明方法可应用于社交网络上实现对社交网络中各种拓扑类型的社区结构进行自动化地检测，有利于研究人员对用户按兴趣进行社区分组，帮助社交平台为用户及时推送感兴趣的内容。

权利要求

1.一种社交网络中社区结构的检测方法，其特征在于，包括以下步骤：S1、分析社交网络的拓扑结构，根据拓扑结构信息构建加权社交网络；

步骤S1中，所述根据拓扑结构信息构建加权社交网络具体包括：利用同一个社区结构中节点之间的拓扑结构相似性对社交网络中的边进行加权，进而构建加权社交网络；包括以下步骤：使用图嵌入方法Node2Vec学习社交网络中节点结构信息的低维特征表示，对于节点v和u，其低维特征表示对应两个向量，即Fv和Fu；

使用两个节点向量的余弦值计算节点v和u的相似性，即边(v,u)的权重，如公式(1)所示：其中Fv＝{x1,x2,…,xi,…,xn}和Fu＝{y1,y2,…,yi,…,yn}分别表示n维的相应向量；TSS(Fv,Fu)表示两个节点的拓扑结构相似性；

对于每条边，其权重w(v,u)用公式(1)表示；当权重为0时，该条边被作为噪声，将其从社交网络中删除；

S2、定义社区结构的核挖掘策略，识别所有社区结构的核；

步骤S2中，所述定义社区结构的核挖掘策略，识别所有社区结构的核，其具体包括：对于局部社区结构，选择具有最高权重边的边作为第一个种子边，所有种子边按降序方式排列，使用边的权重和边的聚集系数识别局部社区结构的核；

对于全局社区结构，利用马尔可夫聚类算法检测全局社区结构的核；

S3、构建基于集成学习的社区结构模型，所述社区结构模型结合了基于有监督学习的投票回归模型和若干个基于无监督学习社区结构的拓扑属性；

步骤S3中，所述构建基于集成学习的社区结构模型具体包括：S31、训练得到的有监督学习社区结构模型；

S32、定义社区结构的密度模型；

S33、定义社区结构的凝聚性模型；

S34、定义社区结构的结构模块化模型；

S35、融合上述训练得到的有监督学习社区结构模型和三个基于无监督学习的拓扑结构模型，最终得到基于集成学习的社区结构模型；

S4、设计启发式图搜索策略，用于扩展社区结构的核进而形成社交网络中完整的社区结构；

S5、根据得到的社区结构对用户进行社区分组，并根据分组结果进行相应的内容推送。

2.根据权利要求1所述的社交网络中社区结构的检测方法，其特征在于，步骤S31具体包括：收集已知真实社区结构并构建加权社交网络；

将真实社区结构映射到加权和非加权社交网络中，获得映射后的社区结构的各种拓扑属性信息，包括：边的数目，节点的数目；

基于映射后的社区结构包含的节点数目进行统计分布计算，进而根据同样的分布，在当前加权和非加权的社交网络中生成假的社区结构，然后分析和提取已知真实社区结构和假的社区结构的拓扑特征；

从这些映射后的真实社区结构和假的社区结构中选择对区分真实社区结构和假的社区结构具有区分度的拓扑特征；

选择合适的监督学习回归模型，利用所述拓扑特征对该监督学习回归模型进行训练；

其中，所述合适的监督学习回归模型是指集成多个单一监督学习回归模型的平均投票回归模型，即VotingRegressor模型；

具体地，选择Linear回归模型、BayesianRidge回归模型、DecisionTreeRegressor 回归模型作为基本回归模型来建立VotingRegressor模型；VotingRegressor模型定义如公式(6)所示：LR＝LinearRegression()

BSR＝BayesianRidge()

DTR＝DecisionTreeRegressor()VR(C)＝VotingRegressor([(LR),(BSR),(DTR)])    (6) 。

3.根据权利要求1所述的社交网络中社区结构的检测方法，其特征在于，步骤S4中，给定一个社区结构的核CC，它的所有直接相连的邻居被作为候选的附属节点集，N(CC)；对于每个附属节点v1∈N(CC)，定义一个候选附属节点和社区结构的核的连接紧密函数，如公式(11)所示：其中，u1为与附属节点v1有边相连且其属于社区结构的核CC的节点；

是候选附属节点v1和社区结构的核连接边的权重和，|N(v1)|是节点v1的邻居节点的数目，|CC|表示社区结构的核CC包含的节点数目，Attachscore(v1,CC)用于评估候选附属节点和社区结构的核CC之间的紧密性；

基于集成学习的社区结构模型对每个社区结构的核执行启发式图搜索策略，进而形成社区结构，启发式图搜索策略包括：对于社区结构的核，通过最大化基于集成学习的社区结构模型的分数，对其通过连接紧密函数公式(11)确定候选附属节点并利用基于集成学习的社区结构模型决定是否对社区结构的核进行扩展，迭代执行上述步骤，直到满足终止条件，最终形成社区结构。

说明书

一种社交网络中社区结构的检测方法

技术领域

[0001] 本发明涉及数据挖掘技术领域，特别涉及一种社交网络中社区结构的检测方法。

背景技术

[0002] 社交网络中普遍存在着“同一社区结构内节点连接紧密、不同社区结构间节点连接稀疏”之特点的“社区结构”。随着应用领域的不同，社区结构具有不同含义。

[0003] 社交网络中的社区结构检测在许多领域都具有非常重要的意义，其检测的核心思想是检测具有高内部连通性，并与外部连接稀疏的子图结构。在过去的数十年，在社交网络中检测社区结构越来越流行。社区结构检测是社交网络分析的一个基本问题，它试图挖掘特定社交网络中具有模块结构的子图。例如社交网络中的社区结构代表了具有某些相近特征的人群、蛋白质相互作用网络中的社区结构就可能对应着功能模块或者蛋白质复合物，蛋白质复合物是在同一时间和地点相互作用形成的一组节点集合。社区结构检测就是挖掘并揭示出这些不同类型社交网络中固有的社区结构，它可被用来帮助人们理解社交网络的功能、发现社交网络中隐藏的规律和预测社交网络的行为。

[0004] 以往的社区结构挖掘方法大多基于无监督学习的方法，并且通常依赖于先验假设：社区结构是一个模块，它在社交网络中具有密集结构。事实上，基于这种假设的方法，其性能是有限的，因为只有部分的社区结构是稠密的，并不是所有的社区结构都是稠密的。同时，为了检测具有不同拓扑结构的社区结构，人们又提出了一些基于有监督学习的检测方法，但是由于缺乏足够的特征和可用于训练的已知社区结构数据集，使得训练后的回归模型的检测精度还有一定的欠缺。因此，迫切需要一种高精度的社交网络中社区结构的检测方法。

[0005] 众所周知，当前社交网络包含了大量的假阳性和假阴性相互作用，即噪声。为了克服社交网络中的噪声，人们发展了许多方法来为社交网络中的每对节点分配“权重”，并构造一个加权的社交网络，以减少这种噪声的影响。

[0006] Gavin等人[Gavin A C, Aloy P, Grandi P, et al. Proteome survey reveals modularity of the yeast cell machinery[J]. Nature, 2006, 440(7084): 631‑636]对社区结构组织的研究表明，社区结构通常包含一个独特的社区结构的核心和许多的附属节点，被称为核‑附属结构。在这里，社区结构的核中的节点之间具有相对更可靠的相互作用边。附属节点是社区结构的核的周围节点，其协助社区结构的核起到一定的作用。

[0007] 一个图由节点和边组成，节点表示个体目标，边是连接不同节点，可以描述不同节点之间的关系。在很多实际应用，图通常用于表示复杂网络，因此有很多实践应用，如社交网络、生物网络和万维网[Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the national academy of sciences, 2002, 99(12): 7821‑7826]。以社交网络为例，用户生成的内容为我们提供了一种区分用户特征的替代方法，从而促进了对社交社区的分析。另一个例子可以在蛋白质相互作用网络中找到具有社区结构的蛋白质复合物，它的检测对理解生物机制和过程是重要的。

[0008] 在过去的十年中，出现了许多不同的计算方法来挖掘社交网络中的社区结构。主要是两种途径：第一，基于无监督学习的方法检测社区结构。这些方法大部分是在社交网络中挖掘具有某种拓扑属性的子图，从而实现社区结构的检测。2002年，Girvan和Newman提出了最著名的社区结构挖掘方法GN (Girvan‑Newman)。该算法通过反复计算边介数，检测社区结构间连接，删除社区结构间连接，以自顶向下的方式建立一颗层次聚类树，该算法最大的缺点是计算速度慢。随后，Girvan和Newman等人[Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical review E, 2004, 69(2): 026113]提出了一个用于刻画社交网络的社区结构优劣的量化标准，被称之为模块性函数Q。该函数Q明确给出了社区结构的清晰定义，并在实际应用中获得成功。因之前的社区结构检测算法需要巨大计算要求，因此Newman等人[Newman M E J. Fast algorithm for detecting community structure in networks[J]. Physical review E, 2004, 69(6): 066133]提出一个新的快速高效地检测社区结构算法。Radicchi等人[Radicchi F, Castellano C, Cecconi F, et al. Defining and identifying communities in networks[J]. Proceedings of the national academy of sciences, 2004, 101(9): 
2658‑2663]提出了用链接聚集系数取代算法GN中链接的边介数。Guimera 和Amaral等人[Guimera R, Amaral L A N. Functional cartography of complex metabolic networks[J]. nature, 2005, 433(7028): 895‑900]提出了基于模拟退火的模块性优化算法（SA），该算法首先随机生成一个初始解，在每次迭代中，在当前解的基础上产生一个新的候选解，由函数Q判断其优劣并采用模拟退火策略中的Metropolis准则决定是否接受该候选解。Van Dongen等人[Van Dongen S M. Graph clustering by flow simulation[D]. , 2000]提出了Markov聚类算法（Markov cluster algorithm,MCL），该算法主要是基于Markov动力学理论，通过改变和调节马尔可夫链呈现网络社区结构。它通过将转移概率强化很强的流，弱化较弱的流，通过不断重复这一过程检测社区结构。

[0009] CFinder[Adamcsek B, Palla G, Farkas I J, et al. CFinder: locating cliques and overlapping modules in biological networks[J]. Bioinformatics, 2006, 22(8): 1021‑1023]是基于（clique percolation method，CPM）[Palla G, Derényi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. nature, 2005, 435(7043): 814‑818]算法实现的一个软件工具，虽然其时间复杂度是非多项式级的，但实际使用运行效率较高。Shen等人[Shen H, Cheng X, Cai K, et al. Detect overlapping and hierarchical community structure in networks[J]. Physica A: Statistical Mechanics and its Applications, 2009, 388(8): 1706‑1712]提出了一种能同时检测社交网络中具有重叠性和层次性的社团结构算法(EAGLE)。Whang等人[Whang J J, Gleich D F, Dhillon I S. Overlapping community detection using neighborhood‑inflated seed expansion[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(5): 1272‑
1284]提出了一种利用种子展开方法的高效重叠社区结构检测算法。Kim等人[Kim Y, Jeong H. Map equation for link communities[J]. Physical Review E, 2011, 84(2): 026110]将社区结构定义为链接社区结构，进而把社区结构挖掘算法infomap有效扩展到链接社区结构挖掘领域。Lee等人[Lee C, Reid F, McDaid A, et al. Detecting highly overlapping community structure by greedy clique expansion[J]. arXiv preprint arXiv:1002.1827, 2010]针对当前重叠社区挖掘算法大部分无法高效检测重叠社区结构的问题，提出了一个贪婪的团扩张算法（greedy clique expansion，GCE）,该算法首先找出一些明显的团结构作为种子，然后从这些种子出发，通过贪婪搜索算法对社区结构的函数进行局部优化以扩充这些种子节点形成的局部重叠社区结构。Liu等人[Liu G, Wong L, Chua  H N. Complex discovery from weighted PPI networks[J]. Bioinformatics, 2009, 25(15): 1891‑1897]使用迭代方法对社交网络进行加权，并开发了一种基于最大团方法（CMC）从加权社交网络中检测社区结构。Nepuse等人[Nepusz T, Yu H, Paccanaro A. Detecting overlapping protein complexes in protein‑protein interaction networks[J]. Nature methods, 2012, 9(5): 471‑472]提出了ClusterONE，它利用贪婪生长过程挖掘具有高内聚性的社区结构。Peng等人[Peng W, Wang J, Zhao B, et al. Identification of protein complexes using weighted pagerank‑nibble algorithm and core‑attachment structure[J]. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2014, 12(1): 179‑
192]设计了一种pagerank策略，并基于相邻节点具有不同的概率和核‑附属结构提出了WPNCA来预测社区结构。最近，Wang等人[Wang R, Wang C, Liu G. A novel graph clustering method with a greedy heuristic search algorithm for mining protein complexes from dynamic and static PPI networks[J]. Information Sciences, 
2020, 522: 275‑298]通过使用局部启发式搜索策略提出了一种新的图聚类方法来挖掘社区结构。

[0010] 第二，基于有监督学习的方法检测社区结构。这些方法首先通过提取特征来训练监督学习模型，然后用训练好的监督学习模型搜索社区结构。但是基于无监督学习的方法不需要解决一些实际问题，例如：已知社区结构特征提取不足、模型选择和训练模型不足等问题。基于无监督学习的检测方法不能利用已知社区结构的信息，也忽略了其他拓扑特性的社区结构，如“星型”模式和“辐条”模式。近年来，一些基于回归模型或分类模型的有监督学习方法也可以从社交网络中检测社区结构。例如，Qi等人[Qi Y, Balem F, Faloutsos C, et al. Protein complex identification by supervised graph local clustering[J]. Bioinformatics, 2008, 24(13): i250‑i268]提出了一个学习贝叶斯网络模型参数的社区结构检测框架。Yu等人[Yu F Y, Yang Z H, Tang N, et al. Predicting protein complex in protein interaction network‑a supervised learning based method[J]. BMC systems biology, 2014, 8(3): 1‑16]提出了一种基于监督学习的方法，该方法用团结构作为初始聚类，并使用经过训练的线性回归模型检测社区结构。Lei等人[Shi L, Lei X, Zhang A. Protein complex detection with semi‑supervised learning in protein interaction networks[C]//Proteome science. BioMed Central, 2011, 9(1): 1‑9]提出了一种半监督学习算法，他们训练了一个神经网络模型来挖掘社区结构。ClusterEPs[Liu Q, Song J, Li J. Using contrast patterns between true complexes and random subgraphs in PPI networks to predict unknown protein complexes[J]. Scientific reports, 2016, 6(1): 1‑15]通过新兴模式（EPs）估计子图是社区结构的可能性。Dong等人[Dong Y, Sun Y, Qin C. Predicting  protein complexes using a supervised learning method combined with local structural information[J]. PloS one, 2018, 13(3): e0194124]提供了ClusterSS方法，该方法提出了一个结合神经网络模型和局部内聚函数的打分函数，该函数指导社区结构的搜索检测社区结构。Liu等人[Liu X, Yang Z, Sang S, et al. Identifying protein complexes based on node embeddings obtained from protein‑protein interaction networks[J]. BMC bioinformatics, 2018, 19(1): 1‑14]提出了一种基于网络嵌入和随机森林模型的监督学习方法用于发现社区结构。Sikandar等人[Sikandar A, Anwar W, Bajwa U I, et al. Decision tree based approaches for detecting protein complex in protein protein interaction network (PPI) via link and sequence analysis[J]. IEEE Access, 2018, 6: 22108‑22120]提出了一种基于决策树的社区结构检测方法，他们使用了社区结构的生物信息和拓扑信息。2021年Zaki等人[Zaki N, Singh H, Mohamed E A. Identifying Protein Complexes in Protein‑Protein Interaction Data Using Graph Convolutional Network[J]. IEEE Access, 2021, 9: 123717‑123726]引入了各种图卷积网络（GCN）方法来改进社区结构的检测方法。Mei等人[Mei S. A framework combines supervised learning and dense subgraphs discovery to predict protein complexes[J]. Frontiers of Computer Science, 2022, 16(1): 1‑14]提出了一种结合有监督学习和密集社区结构发现的检测框架以发现社区结构。Liu等人[Liu G, Liu B, Li A, et al. Identifying Protein Complexes With Clear Module Structure Using Pairwise Constraints in Protein Interaction Networks[J]. Frontiers in Genetics, 2021, 12]提出了一种新的基于非负矩阵三因子分解的半监督模型，并提出了用于检测社交网络中具有清晰模块结构的社区结构。

[0011] 在过去的几十年中，虽然已经提出了许多社区结构的检测方法，但是构建性能优异且能识别多种拓扑结构的社区结构仍然是社交网络中社区检测的一个难题。

发明内容

[0012] 本发明的目的在于提供一种社交网络中社区结构的检测方法，所述方法利用拓扑特征构建加权社交网络，基于核‑附属结构，提出了一种社区结构的核挖掘策略，并设计了一种启发式图搜索策略来形成社区结构，该方法融合了有监督学习方法训练的模型和若干个基于无监督学习的拓扑结构属性，能够提高社区结构检测的准确性。所述方法可应用于社交网络上实现对社交网络中各种拓扑类型的社区结构进行自动化地检测，有利于研究人员对用户按兴趣进行社区分组，帮助社交平台为用户及时推送感兴趣的内容。

[0013] 为解决上述技术问题，本发明的实施例提供如下方案：

[0014] 一种社交网络中社区结构的检测方法，包括以下步骤：

[0015] S1、分析社交网络的拓扑结构，根据拓扑结构信息构建加权社交网络；

[0016] S2、定义社区结构的核挖掘策略，识别所有社区结构的核；

[0017] S3、构建基于集成学习的社区结构模型，所述社区结构模型结合了基于有监督学习的投票回归模型和若干个基于无监督学习社区结构的拓扑属性；

[0018] S4、设计启发式图搜索策略，用于扩展社区结构的核进而形成社交网络中完整的社区结构；

[0019] S5、根据得到的社区结构对用户进行社区分组，并根据分组结果进行相应的内容推送。

[0020] 优选地，步骤S1中，所述根据拓扑结构信息构建加权社交网络具体包括：

[0021] 利用同一个社区结构中节点之间的拓扑结构相似性对社交网络中的边进行加权，进而构建加权社交网络；包括以下步骤：

[0022] 使用图嵌入方法Node2Vec学习社交网络中节点结构信息的低维特征表示，对于节点 和 ，其低维特征表示对应两个向量，即 和 ；

[0023] 使用两个节点向量的余弦值计算节点 和 的相似性，如公式（1）所示：

[0024]

[0025] 其中 和 分别表示维的相应向量； 表示两个节点的拓扑结构相似性；

[0026] 对于每条边，其权重 用公式（1）表示；当权重为0时，该条边被作为噪声，将其从社交网络中删除。

[0027] 优选地，步骤S2中，所述定义社区结构的核挖掘策略，识别所有社区结构的核，其具体包括：

[0028] 对于局部社区结构，选择具有最高权重边的边作为第一个种子边，所有种子边按降序方式排列，使用边的权重和边的聚集系数识别局部社区结构的核；

[0029] 对于全局社区结构，利用马尔可夫聚类算法检测全局社区结构的核。

[0030] 优 选 地 ，对 于 边 ，它 的 权 重 是 ，邻 域 图 表 示 为，其中 ； 的平均加权
度表示为 ，如公式（2）所示：

[0031]

[0032] 基于上述分析，提出一个评分函数 ，其根据边的权重和边的局部权重连接紧密度 对所有边进行评分，以
便选择种子边；

[0033] 根据评分函数 对所有边按降序进行排序，这里只有得分大于所有边得分的平均值的边才会被按分数排序插入种子队列Q；在种子队列Q中的种子边将被用于挖掘社区结构的核；因此，边 的评分函数定义如公式（3）所示：

[0034]

[0035] 对于边 ，其聚集系数 定义为边 所属的三角形数量除以可能包括边 的三角形数量，其定义如公式（4）所示：

[0036]

[0037] 其中 表示由边 构建形成的三角形数量，是两个端节点的最小度数；

[0038] 对于局部社区结构，选择具有最高权重边的节点作为第一个种子边 ，并以其为初始局部社区结构的核，其中局部社区结构的核的邻居节点是否被填加到该局部社区结构的核中，取决于两个条件是否同时满足，第一个是该邻居节点和种子边的任意一个端点连接边的权重是否大于所有边的权重的平均值，即 ，其定义如公式（5）所示：

[0039]

[0040] 第二个条件是如果该邻居节点和种子边 的端点的边之间聚集系数，即大于所有边的聚集系数ECC的平均值 ；这两个约束能够保证该局部社区结构的核中的节点之间在拓扑结构上是相互紧密关联的，只有当上述两个条件均满足的时候，该邻居节点才被添加到该局部社区结构的核中；

[0041] 上述过程对所有邻居节点遍历判断完后，如果该局部社区结构的核包含的节点数量大于或等于2，则保留该局部社区结构的核；为避免重复计算，种子边包括的两个端节点将被标记记录，在后续的种子边选择的过程中将不能再次被用于另一局部社区结构的种子边；

[0042] 然后选择下一条权重最高的种子边，其两个端节点均也不能包含在之前访问过的种子边中，才能用于形成下一个局部社区结构的核，该过程直到种子队列Q中的种子边为空则终止；

[0043] 对于全局社区结构，首先使用马尔可夫聚类算法检测不重叠的全局社区结构的核，然后丢弃包含节点数目小于2的全局社区结构的核；这里，不同种子边扩展形成的局部社区结构的核和全局社区结构的核会有重复的，对于冗余的社区结构的核，则只保留相同的社区结构的核中的一个，其余删除。

[0044] 优选地，步骤S3中，所述构建基于集成学习的社区结构模型具体包括：

[0045] S31、训练得到的有监督学习社区结构模型；

[0046] S32、定义社区结构的密度模型；

[0047] S33、定义社区结构的凝聚性模型；

[0048] S34、定义社区结构的结构模块化模型；

[0049] S35、融合上述训练得到的有监督学习社区结构模型和三个基于无监督学习的拓扑结构模型，最终得到基于集成学习的社区结构模型。

[0050] 优选地，步骤S31具体包括：

[0051] 收集已知真实社区结构并构建加权社交网络；

[0052] 将真实社区结构映射到加权和非加权社交网络中，获得映射后的社区结构的各种拓扑属性信息，包括：边的数目，节点的数目；

[0053] 基于映射后的社区结构包含的节点的数目进行统计分布计算，进而根据同样的分布，在当前加权和非加权的社交网络中生成假的社区结构，然后分析和提取已知真实社区结构和假的社区结构的拓扑特征；

[0054] 从这些映射后的真实社区结构和假的社区结构中选择对区分真实社区结构和假的社区结构具有区分度的拓扑特征；

[0055] 选择合适的监督学习回归模型，利用所述拓扑特征对该监督学习回归模型进行训练；

[0056] 其中，所述合适的监督学习回归模型是指集成多个单一监督学习回归模型的平均投票回归模型，即VotingRegressor模型；

[0057] 具体地，选择Linear回归模型、BayesianRidge回归模型、DecisionTreeGressor回归模型作为基本回归模型来建立VotingRegressor模型；VotingRegressor模型定义如公式（6）所示：

[0058]

[0059] 优选地，步骤S32中，社区结构C的密度定义如公式（7）所示：

[0060]

[0061] 其中 是在社区结构C中所有边的权重和， 代表社区结构C中包含节点的数目，社区结构C的密度 反应社区结构的内部连接紧密程度；

[0062] 步骤S33中，对于一个社区结构 ，它的内部权值度定义为，表示社区结构C中所有边的权重和；它的外部权值度定义为
，表示在社区结构C和外部节点即不属于社区结
构C的节点边的权重和；社区结构C的总权重度 是 与 的和；

[0063] 社区结构C的凝聚分数 定义如公式（8）所示：

[0064]

[0065] 社区结构C的凝聚分数 越高，说明其内部连接越紧密且和外部连接也越稀疏；

[0066] 步骤S34中，结构模块化函数定义如公式（9）所示：

[0067]

[0068] 其中， 表示包含在社区结构C中所有内部节点的平均加权度， 表示社区结构C中的节点数目； 用于估计具有社区结构的子图内部节点之间连接紧密性， 表示社区结构C和它的邻居节点之间
连接的平均权重度，这里 表示社区结构C
的邻居节点集合， 用于评估社区结构C与其相邻节点稀疏连接的程度；

[0069] 当一个社区结构的内部具有较高的密度且与社交网络的其余部分分离良好时，它将具有较高的 。

[0070] 优选地，步骤S35中，对于社区结构C，其基于集成学习的社区结构模型如公式（10）所示：

[0071]

[0072] 优选地，步骤S4中，给定一个社区结构的核CC，它的所有直接相连的邻居被作为候选的附属节点集，N(CC)；对于每个附属节点 ，定义一个候选附属节点和社区结构的核的连接紧密函数，如公式（11）所示：

[0073] 其中， 是候选附属节点 和社区结构的核连接边的权重和， 是节点 的邻居节点的数目， 表示社区结构的核CC包含的节点数目，用于评估候选附属节点和社区结构的核CC之间的紧密性；

[0074] 基于集成学习的社区结构模型对每个社区结构的核执行启发式图搜索策略，进而形成社区结构，启发式图搜索策略包括：对于社区结构的核，通过最大化基于集成学习的社区结构模型的分数，对其通过连接紧密函数公式（11）确定候选附属节点并利用基于集成学习的社区结构模型决定是否对社区结构的核进行扩展，迭代执行上述步骤，直到满足终止条件，最终形成社区结构。

[0075] 优选地，启发式图搜索策略的具体步骤如下：

[0076] S41、输入一个社区结构的核；

[0077] S42、基于公式（10）和公式（11）获取社区结构的核的附属节点，检测社区结构的核的所有附属节点并与其社区结构的核形成社区结构；首先，确定当前社区结构的核的邻居节点，然后根据公式（11）确定拥有最大附属连接分数的邻居节点；

[0078] S43、候选附属节点 被添加到社区结构的核CC中后，计算社区结构的核的适应度分数 ，如果它的适应度分数大于社区结构CC的适应度分数，则附属节点v被添加到社区结构的核CC中，这个添加过程会被迭代进行；每次新的候选附属节点的插入后，邻居节点和候选附属节点以及社区结构的核CC都会被更新，这个过程直到利用公式（11）确定的候选附属节点的添加后的适应度分数不再大于 ，则终止该添加过程；

[0079] S44、重复步骤S41‑步骤S43直到社区结构的 不再增加，那么此时的社区结构被认为形成了一个局部最优社区结构，如果该社区结构的大小大于3，则该社区结构将被作为检测到的社区结构输出；

[0080] S45、选择下一个社区结构的核，然后使用上述启发式图搜索策略继续扩展剩余社区结构的核，进而形成下一个社区结构，直到所有的社区结构的核被遍历。

[0081] 本发明实施例提供的技术方案带来的有益效果至少包括：

[0082] 本发明首次提出一个整合平均投票回归模型和若干个社区结构的拓扑属性的基于集成学习的社区结构模型；提出一个社区结构具有核‑附属结构，并分别提出社区结构的核识别策略和图启发式搜索策略。本发明提供的社交网络中社区结构的检测方法可应用于社交网络中实现对各种拓扑结构的社区结构进行自动化地检测。本发明方法与现有的社区结构挖掘方法相比能识别多种拓扑结构的社区结构。对社交网络中社区结构的检测有利于研究人员对用户按兴趣进行社区分组，能够帮助社交平台为用户及时推送感兴趣的内容，进而根据用户的需求进行精准营销具有重要的市场应用价值。

附图说明

[0083] 为了更清楚地说明本发明实施例中的技术方案，下面将对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

[0084] 图1是本发明实施例提供的一种社交网络中社区结构的检测方法的流程示意图；

[0085] 图2是本发明实施例提供的回归模型的训练过程示意图；

[0086] 图3是本发明实施例提供的启发式图搜索策略示意图。

具体实施方式

[0087] 为使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明实施方式作进一步地详细描述。

[0088] 本发明的实施例提供了一种社交网络中社区结构的检测方法，参考图1所示，所述方法包括以下步骤：

[0089] S1、分析社交网络的拓扑结构，根据拓扑结构信息构建加权社交网络；

[0090] S2、定义社区结构的核挖掘策略，识别所有社区结构的核；

[0091] S3、构建基于集成学习的社区结构模型，所述社区结构模型结合了基于有监督学习的投票回归模型和若干个基于无监督学习社区结构的拓扑属性；

[0092] S4、设计启发式图搜索策略，用于扩展社区结构的核进而形成社交网络中完整的社区结构；

[0093] S5、根据得到的社区结构对用户进行社区分组，并根据分组结果进行相应的内容推送。

[0094] 这里首先给出本发明实施例中使用的一些专业术语。社交网络通常被描述为加权图，记为 ，其中 表示节点， 表示节点之间的边， 表示社交网络中节点之间的可靠性，即为一个 的权重矩阵。节点 的所有直接交互邻居被定义为 。

[0095] 本发明方法的具体过程如下：

[0096] S1、分析社交网络的拓扑结构，根据拓扑结构信息构建加权社交网络。

[0097] 社区结构由节点及其边组成，同一个社区结构中的节点具有相似的拓扑结构。考虑边的权重时，社区结构挖掘算法的性能将显著增强。

[0098] 本步骤中，所述根据拓扑结构信息构建加权社交网络具体包括：

[0099] 利用同一个社区结构中节点之间的拓扑结构相似性对社交网络中的边进行加权，进而构建加权社交网络；包括以下步骤：

[0100] 使用图嵌入方法Node2Vec学习社交网络中节点结构信息的低维特征表示，对于节点 和 ，其低维特征表示对应两个向量，即 和 ；

[0101] 使用两个节点向量的余弦值计算节点 和 的相似性，如公式（1）所示：

[0102]

[0103] 其中 和 分别表示维的相应向量； 表示两个节点的拓扑结构相似性；

[0104] 对于每条边，其权重 用公式（1）表示；当权重为0时，该条边被作为噪声，将其从社交网络中删除。最后，用拓扑结构相似度提高了社交网络的可靠性。综上所述，用拓扑结构相似性对社交网络中的作用边进行加权，进而构建了加权的社交网络。

[0105] S2、定义社区结构的核挖掘策略，识别所有社区结构的核。

[0106] 根据构建的加权社交网络，其利用学习得到两个相连的节点的特征向量，然后用余弦相似性方法计算这两个节点的相似性，相似性越高，它们之间的权重值越高，这两个相互作用的节点越有可能位于同一个社区结构内。此外，在社交网络中社区结构的核通常对应稠密的社区结构。

[0107] 基于以上事实，本发明挖掘社区结构的种子节点的具体步骤如下：

[0108] 对于边 ，它的权重是 ，邻域图表示为, 其中 ； 的平均加权度表示为
，如公式（2）所示：

[0109]

[0110] 基于上述分析，提出一个评分函数 ，其根据边的权重和边的局部权重连接紧密度 对所有边进行评分，以
便选择种子边；

[0111] 根据评分函数 对所有边按降序进行排序，这里只有得分大于所有边得分的平均值的边才会被按分数排序插入种子队列Q；在种子队列Q中的种子边将被用于挖掘社区结构的核；因此，边 的评分函数定义如公式（3）所示：

[0112]

[0113] 对于边 ，其聚集系数 定义为边 所属的三角形数量除以可能包括边 的三角形数量，其定义如公式（4）所示：

[0114]

[0115] 其中 表示由边 构建形成的三角形数量，是两个端节点的最小度数。

[0116] 对于局部社区结构，选择具有最高权重边的边作为第一个种子边，所有种子边按降序方式排列，使用边的权重和边的聚集系数识别局部社区结构的核；具体包括：

[0117] 选择具有最高权重边的边作为第一个种子边 ，并以其为初始局部社区结构的核，其中局部社区结构的核的邻居节点是否被填加到该局部社区结构的核中，取决于两个条件是否同时满足，第一个是该邻居节点和种子边的任意一个端点连接边的权重是否大于所有边的权重的平均值，即 ，其定义如公式（5）所示：

[0118]

[0119] 第二个条件是如果该邻居节点和种子边 的端点的边之间聚集系数，即大于所有边的聚集系数ECC的平均值 ；这两个约束能够保证该局部社区结构的核中的节点之间在拓扑结构上是相互紧密关联的，只有当上述两个条件均满足的时候，该邻居节点才被添加到该局部社区结构的核中；

[0120] 上述过程对所有邻居节点遍历判断完后，如果该局部社区结构的核包含的节点数量大于或等于2，则保留该局部社区结构的核；为避免重复计算，种子边包括的两个端节点将将被标记记录，在后续的种子边选择的过程中不能再次被用于另一局部社区结构的种子边；

[0121] 然后选择下一条权重最高的种子边，其两个端节点均也不能包含在之前访问过的种子边中，才能用于形成下一个局部社区结构的核，该过程直到种子队列Q中的种子边为空则终止。

[0122] 对于全局社区结构，利用马尔可夫聚类算法检测全局社区结构的核。具体包括：

[0123] 首先使用马尔可夫聚类算法检测不重叠的全局社区结构的核，然后丢弃包含节点数目小于2的全局社区结构的核；这里，不同种子边扩展形成的局部社区结构的核和全局社区结构的核会有重复的，对于冗余的社区结构的核，则只保留相同社区结构的核中的一个，其余删除。

[0124] S3、构建基于集成学习的社区结构模型，所述社区结构模型结合了基于有监督学习的投票回归模型和若干个基于无监督学习社区结构的拓扑属性。

[0125] 当定义一个具有社区结构的子图为 ，其中 表示属于社区结构C的节点数目， 表示社区结构C包含边的数目，而 表示C包含所有对应边集的权重集合。

[0126] 本步骤中，所述构建基于集成学习的社区结构模型具体包括：

[0127] S31、训练得到的有监督学习的社区结构模型。

[0128] 社交网络中的已知真实社区结构和假的社区结构都被建模为加权和未加权无向图。提取和选择合适的特征对区分真实社区结构和假的社区结构十分关键。以前的基于无监督学习方法通常假设在社交网络中的团结构、三角形、矩形、辐条和星图等为社区结构。当然，描述这些结构的拓扑特征如度统计、节点大小和边统计等也被用于检测具有这些属性的社区结构，但是，社区结构还有其他的拓扑结构类型。所以也需要挖掘一些新的拓扑特征用于更加完善地检测各种拓扑结构的社区结构。

[0129] 本实施例中，一方面，使用一些现有的拓扑特征来描述和检测社区结构；另一方面，也提出了一些新的拓扑特征来描述一些尚未提取出的社区结构特征（参考表1中加黑的拓扑特征）。在本实施例中，总计使用65个拓扑特征来描述社交网络中的社区结构，如表1所示。

[0130] 表1社区结构的拓扑特征列表

[0131]

[0132]

[0133] 为了获得回归模型，将进行以下几个步骤：

[0134] 收集已知真实社区结构并构建加权社交网络；

[0135] 将真实社区结构映射到加权和非加权真实社交网络中，获得映射后的社区结构的各种拓扑属性信息，包括：边的数目，节点的数目；

[0136] 基于映射后的社区结构包含节点的数目进行统计分布计算，进而根据同样的分布，在当前加权和非加权的社交网络中生成假的社区结构，然后分析和提取已知真实社区结构和假的社区结构的拓扑特征；

[0137] 从这些映射后的真实社区结构和假的社区结构中选择对区分真实社区结构和假的社区结构具有区分度的拓扑特征；

[0138] 选择合适的监督学习回归模型，利用所述拓扑特征对该监督学习回归模型进行训练。

[0139] 以往的研究选择的基于有监督学习的回归模型多数是单一的回归模型，如线性回归、决策树和支持向量机等，这些单一的回归模型最大的弊端是他们有自身模型的局限性。因此，在本发明中，选择集成了多个单一监督学习回归模型的平均投票回归模型，即VotingRegressor模型。最后，利用提取的真实社区结构和假的社区结构的拓扑特征训练选择的监督学习回归模型，最终得到训练后的监督学习回归模型。监督学习回归模型的训练流程如图2所示。

[0140] 本发明实施例中，选择Linear回归模型、BayesianRidge回归模型、DecisionTreeGressor回归模型作为基本回归模型来建立VotingRegressor模型。选择VotingRegressionor是鉴于它能减少单个基本模型的方差，并具有更好的泛化能力。此外，VotingRegressionor比单个模型预测具有更强的鲁棒性。结果表明，经过训练的VotingRegressor模型可用于从监督学习的角度评估社区结构成为真实社区结构的概率，以检测具有各种拓扑结构的社区结构。通过VotingRegressionor模型获得的分数越高，那么该预测的社区结构是真实社区结构的概率越高。

[0141] VotingRegressor模型定义如公式（6）所示：

[0142]

[0143] S32、定义社区结构的密度模型。

[0144] 鉴于社区结构在社交网络中是内部节点彼此之间连接紧密，而且与外部连接稀疏的子图，考虑到这一特性，本发明定义既考虑社区结构的模块度又考虑社区结构密度的模型，此模型可以更加真实地反应社区结构的拓扑结构。

[0145] 社区结构C的密度定义如公式（7）所示：

[0146]

[0147] 其中 是在社区结构C中所有边的权重和， 代表社区结构C中包含节点的数目，社区结构C的密度 反应社区结构的内部连接紧密程度。

[0148] S33、定义社区结构的凝聚性模型。

[0149] 对于一个社区结构 ，它的内部权值度定义为，表示社区结构C中所有边的权重和；它的外部权值度定义为
，表示在社区结构C和外部节点即不属于社区结构C的
节点边的权重和；社区结构C的总权重度 是 与 的和。

[0150] 社区结构C的凝聚分数 定义如公式（8）所示：

[0151]

[0152] 社区结构C的凝聚分数 越高，说明其内部连接越紧密且和外部连接也越稀疏。

[0153] S34、定义社区结构的结构模块化模型。

[0154] 基于社区结构的内部和模块之间以及社区结构的大小，本发明根据社交网络中社区结构具有结构模块结构的特性，提出一种有效的评估测量方法用于估计社区结构作为社交网络中社区结构的可能性，即结构模块化 模型来评估一个节点簇 是社区结构的概率，该模型可以检测社交网络中内部紧
密连接和与外界稀疏连接的社区结构。

[0155] 结构模块化函数定义如公式（9）所示：

[0156]

[0157] 其中， 表示包含在社区结构C中所有内部节点的平均加权度， 表示社区结构C中的节点数目； 用于估计具有社区结构的子图内部节点之间连接紧密性， 表示社区结构C和它的邻居节点之间
连接的平均权重度，这里 表示社区结构C
的邻居节点集合， 用于评估社区结构C与其相邻节点稀疏连接的程度；

[0158] 当一个社区结构的内部具有较高的密度且与社交网络的其余部分分离良好时，它将具有较高的 值。 能够满足检测具有高内聚和低耦合性质的社区结构，并且它可以表示社区结构中的节点在社区结构内呈现出的强而频繁的连接，而在社区结构外表现出弱而稀松的连接。

[0159] S35、融合上述有监督学习的社区结构模型和三个基于无监督学习的拓扑结构模型，得到基于集成学习的社区结构模型。

[0160] 结合上述若干个社区结构模型，本发明方法提出了一个基于集成学习的社区结构模型，该模型融合上述4种子社区结构模型包括基于有监督学习的 和3个基于无监督学习的拓扑结构模型。该模型可用于全面地量化社区结构 作为候选社区结构的可能性，从而指导社区结构检测过程。这个基于集成学习构建的社区结构模型通常通过组合多个模型的输出来提高社区结构检测的鲁棒性和稳定性，从而提高社区结构的检测精度。

[0161] 对于社区结构C，其基于集成学习的社区结构模型如公式（10）所示：

[0162]

[0163] 基于公式（10）的基于集成学习的社区结构模型，本发明将引入一种启发式图搜索策略在基于集成学习的社区结构模型的引导下检测社区结构。

[0164] S4、设计启发式图搜索策略，用于扩展社区结构的核进而形成社交网络中完整的社区结构。

[0165] 基于社区结构由社区结构的核和附属节点共同形成的事实，本发明基于已获得许多的社区结构的核和基于集成学习的社区结构模型。接下来，要做的是为社区结构的核检测附属节点，然后社区结构的核与它的附属节点共同形成社区结构。

[0166] 给定一个社区结构的核CC，它的所有直接相连的邻居被作为候选的附属节点集，N(CC)；对于每个附属节点 ，定义一个候选附属节点和社区结构的核的连接紧密函数，如公式（11）所示：

[0167]

[0168] 其中， 是候选附属节点 和社区结构的核连接边的权重和， 是节点 的邻居节点的数目， 表示社区结构的核CC包含的节点数目，用于评估候选附属节点和社区结构的核CC之间的紧密性。

[0169] 基于集成学习的社区结构模型对每个社区结构的核执行启发式图搜索策略，进而形成社区结构，启发式图搜索策略包括：对于社区结构的核，通过最大化基于集成学习的社区结构模型的分数，对其通过连接紧密函数公式（11）确定候选附属节点并利用基于集成学习的社区结构模型决定是否对社区结构的核进行扩展，迭代执行上述步骤，直到满足终止条件，最终形成社区结构。启发式图搜索策略的流程如图3所示。

[0170] 启发式图搜索策略的具体步骤如下：

[0171] S41、输入一个社区结构的核；

[0172] S42、基于公式（10）和公式（11）获取社区结构的核的附属节点，检测检测社区结构的核的所有附属节点并其社区结构的核形成社区结构；首先，确定当前社区结构的核的邻居节点，然后根据公式（11）确定拥有最大附属连接分数的邻居节点；

[0173] S43、候选附属节点 被添加到社区结构的核CC中后，计算社区结构的核的适应度分数 ，如果它的适应度分数大于社区结构CC的适应度分数，则附属节点 被添加到社区结构的核CC中，这个添加过程会被迭代进行；
每次新的候选附属节点的插入后，邻居节点和候选附属节点以及社区结构的核CC都会被更新，这个过程直到利用公式（11）确定的候选附属节点的添加后的适应度分数不再大于 ，则终止该添加过程；

[0174] S44、重复步骤S41‑步骤S43直到社区结构的 不再增加，那么此时的社区结构被认为形成了一个局部最优社区结构，如果该社区结构的大小大于3，则该社区结构将被作为检测到的社区结构输出；

[0175] S45、选择下一个社区结构的核，然后使用上述启发式图搜索策略继续扩展剩余社区结构的核，进而形成下一个社区结构，直到所有的社区结构的核被遍历。

[0176] 综上所述，本发明首次提出一个整合平均投票回归模型和若干个社区结构的拓扑属性的基于集成学习的社区结构模型；提出一个社区结构具有核‑附属结构，并分别提出社区结构的核检测策略和图启发式搜索策略。本发明方法可应用于社交网络上实现对社交网络中各种拓扑类型的社区结构进行自动化地检测。本发明方法与现有的社区结构挖掘方法相比能识别多种拓扑结构的社区结构。对社交网络中社区结构的检测有利于研究人员对用户按兴趣进行社区分组，能够帮助社交平台为用户及时推送感兴趣的内容，进而根据用户的需求进行精准营销具有重要的市场应用价值。

[0177] 以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。