基于边图的线性流重叠社区发现算法

重叠网络的社区发现是复杂网络研究中的重要问题。为了提高网络中重叠社区发现的时间效率，提出一种基于边图的线性流重叠社区发现算法LBSA。算法首先对于边图网络中的边进行随机的依次处理，完成节点的初步社区划分，再将其中重叠小社区合并到相似度最大的其他大社区中得到最终的社区。通过以上步骤，算法能够以接近线性的时间复杂度得到网络的重叠结构。从最终的实验结果来看，与其他算法相比，该算法能够在更短的时间有质量地发现网络中的重叠社区。     

基于连边距离矩阵的重叠社区发现

现有重叠社团发现算法大多直接从相邻连边的相似性出发,不能有效利用网络的多层连边信息。基于此,本文提出了一种基于连边距离矩阵的重叠社区发现算法LDM。首先结合连边-节点-连边随机游走模型,以实现多级连边信息的有效利用,其次借助模糊聚类方法,处理连边距离矩阵以获取连边社区,最后根据扩展模块度调整和优化重叠社区结构。在人工网络和真实网络上的实验结果表明,所提算法能够有效提高重叠社区发现算法的准确度。     

基于连边密度传播的二分网络社区发现算法

依据节点在社区中的连边情况,定义社区内节点的连边密度,构造社区的平均密度评价指标。经过实例验证,社区的平均密度评价指标能够克服模块度在完全图上的分辨率限制。同时,通过节点的连边密度和最优化社区的平均密度,提出连边密度传播算法。在真实数据和人工数据上进行测试,利用该算法划分社区后求得的模块度和社区平均密度都比利用BRIM算法、边集聚系数算法和资源分布算法求得的值高。这表明相比以上三种算法,连边密度传播算法更能够有效地发现二分网络的社区结构。     

一种新的重叠社区发现算法*

基于节点的中心度和节点对社区的适应度,提出了一种新的重叠社区发现算法。该算法以中心度很大的节点作为初始社区,然后访问社区的邻居节点,把对社区适应度最大的节点加入到社区。如果节点对多个社区都具有很大的适应度,则这些节点归属于多个社区。考虑到社区之间的重叠性,将社区相似度很大的社区合并为一个社区。将该算法应用到Zachary空手道俱乐部网络和海豚社会网络中,实验表明该算法能够很好地划分出网络中的重叠社区。     

基于三级邻居影响力分析的重叠社区发现算法

针对目前重叠社区发现算法时间复杂度较高、社区发现稳定性较差的问题,基于标签传播和COPRA方法,提出一种基于三级邻居节点影响力分析的重叠社区发现算法OCDITN。使用三级邻居节点影响力度量方法TIM(three-level influence measurement)计算节点间的影响力,根据节点影响力确定选择更新节点的顺序;在节点标签更新策略中,根据计算节点与其邻居之间的相似度确定邻居节点标签的更新顺序,计算各节点标签隶属度,发现重叠社区。实验分别基于人工模拟网络数据集和真实世界网络数据集进行测试,与SLPA、LPANNI、COPRA算法相比,该算法在EQ和Qvo两个评价标准上性能分别提升7%和12%,社区划分结果更稳定,社区划分质量更高。     

基于多层节点相似度的社区发现方法

社区发现是复杂网络研究中的一项重要研究内容,基于节点相似度的凝聚方法是一种典型的社区发现方法。针对现有节点相似度计算方法中存在的不足,提出一种基于多层节点的节点相似度计算方法,该方法既可以有效地计算节点之间的相似度,又可以解决节点相似度相同时的节点合并选择问题。进一步基于这种改进的节点相似度计算方法和团体之间的连接紧密度度量准则构建社区发现模型,并在真实世界的网络上进行社区发现实验。与GN算法、Fast Newman算法和改进的标签传播算法的实验结果相比,该模型可以更加准确地找到各个社区的成员。     

边异质网络中的社区结构发现算法

为解决社区结构发现算法功能社区与拓扑社区不一致的问题,提出一种基于边类型相似性聚类(TESC)的社区结构发现算法。该算法以局部拓扑特征与异质信息为目标进行节点聚类,基于节点邻接边类型构造网络节点之间的相似矩阵,从而获取边异质信息。在该相似矩阵的基础上,通过传统层次聚类的思想将相似度大的节点进行合并,进而利用轮廓系数优化社区数量,得到最终社区划分结果。选取社区结构已知的4个真实网络和6个人工合成基准LFR网络,通过与同质网络的GN、Louvain算法以及异质网络的Hete-SPAEM、Hetero-Attractor算法对比,结果表明TESC算法获得的社区结构更接近于网络实际社区结构。     

一个基于中心度的社团结构发现新算法*

针对GN算法在社团结构发现中时间复杂度高等问题,提出一种基于中心度的GN改进算法（DCGN）。该算法根据节点中心度以及节点之间的最短路径首先确定社团结构中心节点集,然后逐步删除社团结构中心节点之间的最大边介数连边,完成社团结构划分。DCGN算法避免了GN算法边介数计算开销大的问题,算法的时间复杂度约为O(cmn),其中c为常数,n为网络成员数,m为网络连边数。将DCGN和GN算法同时应用到Zachary网络及计算机随机生成网络中并进行了比较。实验结果表明,所提出的DCGN算法在运行效率和效果方面较之GN算     

基于节点拓扑结构和属性的重叠社区检测算法

近些年来,网络中的重叠社区检测应用越来越广泛,这极大引起了人们的兴趣。通常重叠社区检测只考虑节点的拓扑结构信息,忽略了节点的属性信息,这可能会遗漏数据间的重要结构。本文提出了一种基于节点拓扑结构和属性相似度的局部社区检测算法。首先,计算出节点与社区之间属性相似度。其次,为挖掘内部紧耦合的社区,计算出能够表示耦合性的模块度增量。最后,通过融合多个已检测到局部社区,计算出隶属矩阵从而获取全局重叠社区结构。在三个有真实社区的数据集上的实验结果从内部指标模块度和与真实社区的比较验证了基于节点拓扑结构和属性相似度的重叠社区检测算法比目前基于节点结构的社区检测算法在效率和有效性上有所提升。     

基于时间加权的重叠社区检测算法研究

随着网络结构的不断扩大和日益复杂, 重叠社区发现技术对挖掘复杂网络深层潜在结构具有重要意义. 本文提出一种基于时间加权的重叠社区检测算法. 该方法考虑了用户兴趣的时间因素, 构建带有时间加权链接的用户-用户图. 接着, 基于网络节点的影响力计算用户全局相似度, 在此基础上通过计算节点的中心度作为度量节点对社区结构影响力的重要性指标, 从而提出一种社区中心点的选取方法. 最后, 通过效用函数的迭代计算实现重叠社区检测. 利用人工网络和真实网络对提出的算法进行验证, 实验结果表明: 相对于传统的社区发现方法, 该算法在社区发现质量和计算效率方面都优于许多已有重叠社区发现算法.     

True-link clustering through signaling process and subcommunity merge in overlapping community detection

To overcome the difficulty in detecting reliable overlapping communities in complex networks, “true-link” and “pseudo-link” are firstly proposed on the basis of the original network graph. Then, the “true-link” graph is obtained through the preprocessing of the original network graph. And then the line graph is partitioned by means of signaling process and single-linkage hierarchical clustering. Meanwhile, the subcommunities are merged based on the proposed similarity between communities, which eradicates the inherently redundant overlapping communities to a certain extent. Compared with other overlapping community detection algorithms, this proposed algorithm is of strong robustness and high accuracy. All the results of the experiments boil down to the conclusion that this True-link Clustering Community Detection is an overlapping community detection algorithm prevailing over others.

     

基于SimRank全局矩阵平滑收敛的网络社区发现

SimRank方法是一种基于图的拓扑结构信息来衡量任意两个对象间相似程度的方法,针对在真实的大规模社交网络中节点与节点之间的迭代计算过程需要消耗大量的时间,提出了一种基于SimRank全局矩阵平滑收敛的网络社区发现方法（SimRank global smooth convergence,SGSC）。首先,该算法通过经典度量来识别网络中的初始核心节点;然后利用矩阵平滑收敛来计算SimRank得到最终核心节点;最后,基于全局收敛矩阵,将社区聚集在核心节点周围,使用Closeness指数合并两个社区,通过递归的重复该过程,聚类出最终社区。在3种真实的不同规模的社交网络中将SGSC和其他2种具有代表性的方法进行比较,并验证了提出的算法在不同规模的社交网络中社区划分的准确率和算法运行的时间性能上有所提升。     

基于线图与PSO的网络重叠社区发现

从优化模块度的角度出发,引入线图理论,给出线图的硬划分与原 图的有重叠划分相对应的理论证明, 提出了一种基于线图与粒子群优化技术的网络重叠社区发现算法(Communities discovery based on line graph and particle swarm optimization, LGPSO), 该方法通过粒子群优化 (Particle swarm optimization, PSO)算法寻找网络对应线图的最优划分来发现网络重叠社区, 实验结果显示,该方法能够在无先验信息的条件下快速有效地揭示网络的重叠社区结构.     

基于节点依赖度和相似社团融合的社团结构发现算法

社团结构作为复杂网络的拓扑特性之一具有重要的理论和实践意义。提出一种基于节点依赖度和相似社团融合的社团结构发现算法,首先根据依赖度和相似度的定义将整个网络划分成若干个平均集聚系数较大的局部网络,构成网络的基础骨架社团;然后根据连接度的定义不断将社团边缘的节点和小社团吸收到相应的骨架网络中去,直到所有节点都得到准确的社团划分。算法在Zachary空手道俱乐部网络和海豚社会网络中进行了社团划分实验,并与GN算法和Newman快速算法进行了比较,结果表明该算法可以有效地划分社团边缘的模糊节点,社团划分结果具有较高的准确度。     

一种基于粗糙集和密度峰值的重叠社区发现方法

随着互联网和社会的发展,各个领域每天都会产生大量相互关联、彼此依赖的数据,这些数据根据不同的主题形成了各种复杂网络。挖掘社区结构是复杂网络领域中的一项重要研究内容,因为其在推荐系统、行为预测和信息传播等方面具有极其重要的意义。社区结构中的重叠社区结构在生活中普遍存在,更具有实际研究意义。为有效发现复杂网络中的重叠社区,文中引入了粗糙集理论对社区进行分析,识别出重叠节点,进而提出了一种基于粗糙集和密度峰值的重叠社区发现方法OCDRD(Overlapping Community Detection Algorithm Based on Rough Sets and Density Peaks)。该方法在传统网络节点局部相似性度量的基础上,结合灰色关联分析方法求出网络节点间的全局相似性,进而将其转化为节点间距离。将密度峰值聚类算法的思想应用于该算法中,以根据网络结构自动选取社区中心节点。依据网络中节点的距离比例关系,定义了社区的上近似、下近似以及边界域。最后,不断调整距离比率阈值并进行划分迭代,在每次迭代中针对社区的边界域进行计算,从而获得最佳重叠社区划分结构。在LFR基准人工网络数据集和真实网络数据集上,基于标准互信息(Normalized Mutual Information,NMI)和具有重叠性模块度EQ这两个评价指标,将OCDRD方法与近几年效果较好的其他社区发现算法进行测试比较。实验结果显示,OCDRD方法在社区划分结构方面整体优于其他社区发现算法,表明了该算法的可行性和有效性。     

基于LeaderRank和节点相似性的多标签传播重叠社团挖掘算法

针对基于多标签传播重叠社团挖掘算法COPRA因随机更新策略带来的不稳定性以及需要预先输入参数的局限性等问题,提出一种基于LeaderRank和节点相似性的多标签传播重叠社团挖掘算法.该算法首先利用LeaderRank算法对网络中的节点进行重要性排序从而确定节点的更新顺序,减少标签不必要的更新.在标签传播过程中,根据节点相似性重新设计标签的更新策略,提高算法的稳定性.将算法应用于人工网络和真实网络中进行实验,实验结果表明该算法在挖掘重叠社团上具有较高的准确性和稳定性.     

基于边密度聚类的重叠社区发现算法

基于边聚类的社区发现算法以边为聚类对象,自然发现重叠社区,但也存在生成的社区集边界归属模糊、社区结构过度重叠等问题.基于此种情况,文中提出基于边密度聚类的重叠社区发现算法.首先,以边为研究对象,通过密度聚类检测连接紧密的核心边社区.然后,根据边界边归属策略将边界边划分到离它最近的核心边社区.针对孤立边,提出基于边的度与边的社区归属的孤立边处理策略,进一步处理未划分的孤立边,避免社区结构过度重叠的问题.最后,将边社区还原为节点社区,实现重叠社区的发现.在人工数据集和真实数据集上的实验表明,文中算法可以快速准确地检测复杂网络中的重叠社区.     

基于密度聚类的增量动态社区发现算法

现实世界中社交网络中的节点和边随时间动态增加或消失,导致网络中的社区结构也随之发生变化,因此,文中提出基于密度聚类的增量动态社区发现算法.首先,基于改进后的DBSCAN生成初始时刻社区.然后,提出边变化率指标,并结合余弦相似度指标确定相邻时刻邻居发生变化的节点及其邻居节点的社区归属调整.在进行社区归属度计算时,不仅考虑节点直接邻居的影响,还考虑间接邻居的影响.最后,通过迭代更新模块度增益进行社区合并,以减少噪声社区的干扰.在人工数据集和真实数据集上的实验表明,文中算法可以有效应对网络结构突变和增量计算累积误差带来的影响,具有较低的时间复杂度.     

用于网络重叠社区发现的粗糙谱聚类算法

针对绝大多数社区发现算法都存在着网络节点仅隶属于一个社区的假设,引入谱图理论与粗糙集理论来分析复杂网络社区,提出一种用于网络重叠社区发现的粗糙谱聚类算法RSC,该算法用上下近似来刻画网络节点的社区归属,边界表示社区之间共享的节点,通过优化重叠社区结构模块度来实现重叠社区发现.通过3个不同类型真实网络的仿真实验,结果验证了该方法的可行性与有效性.