动态复杂网络社区挖掘—选择性聚类融合算法

针对当前研究动态复杂网络的热点问题,提出了一种基于选择性聚类融合的社区挖掘算法.该算法首先将动态过程划分为相同时间间隔的快照,利用欧几里德距离、顶点权重等技术,使用一种改进的层次聚类算法加快聚类速度,得到每个快照相应的聚类结果;然后根据这些聚类结果之间的差异性,筛选聚类结果集合,为融合过程提供多样性的聚类成员;考虑到时间衰减性,设计了加权共联矩阵,使用单链接算法来得到最终的聚类结果.在随机网络和真实世界网络上对算法的计算速度和动态特征挖掘情况两方面进行实验,结果表明了该算法的可行性和有效性.     

网络重叠社区发现的谱聚类集成算法

鉴于计算代价高昂的谱聚类无法满足海量网络社区发现的需求,提出一种用于网络重叠社区发现的谱聚类集成算法(SCEA).首先,利用高效的近似谱聚类(KASP)算法生成个体聚类集合;然后,引入个体聚类选择机制对个体聚类进行优选,并对优选后的个体聚类建立簇相似图;最后,进行层次软聚类,得到网络节点的软划分.实验结果表明,与代表性算法(CPM,Link,COPRA,SSDE)相比较,SCEA能够挖掘出具有更高规范化互信息(NMI)的网络重叠社区结构,且具有相对较好的鲁棒性.     

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

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

基于谱聚类的动态网络社区演化分析算法

针对复杂网络社区受到个体兴趣和迁移的影响随着时间推移而演化的问题,提出一种基于谱聚类的动态网络社区演化分析算法,试图揭示动态网络社区结构随时间的演变过程.算法融合当前时刻快照拓扑结构和上一时刻社区结构两个因素,并用随机分块模型和Dirichlet分布分别对上述两个因素建模,从而将社区演化分析形式化为优化问题.从理论上验证了社区演化分析与谱聚类是等价的,为利用谱聚类解决社区演化分析奠定理论基础.在合成数据集上的实验结果表明,相比于以规格化割为目标的谱聚类,所提方法能显著提升动态社区检测的准确性和稳定性.     

基于谱聚类的社交网络动态社区发现算法

动态社区发现研究是社交网络分析（SNA）的重要研究领域。随着节点加入或离开社交网络，节点间的关系也随之建立或消失，进而影响着社区结构的变化。针对社交网络静态社区发现算法缺少必要的社区节点历史信息而导致的网络结构分析、聚类信息不足和计算开销过大的问题，基于社区网络演化事件的划分并根据主要社区事件的分析，提出一种基于谱聚类的动态社区发现算法（SC-DCDA）。首先，根据实验观察使用谱映射的方法将高维数据降维，并采用改进的模糊C-均值聚类（FCM）算法确定动态社交网络中的节点与待发现社区的关联度；其次，根据演化相似度矩阵分析社区结构。通过使用真实网络数据集以及模块度得分、轮廓系数等社区发现算法衡量指标，评估所提算法的效果。实验结果表明，SC-DCDA的计算开销相较于传统谱聚类降低了8.37%，在所有数据集上的平均模块度得分是0.49，其他衡量指标的定性分析结果也较好，验证了所提算法在信息交互、聚类效果和精确度上表现较好。     

基于谱聚类的复杂网络社团发现算法

复杂网络社团发现的研究对于控制疾病传播、网络病毒的传播等具有重大意义.针对已有社团发现算法时间复杂度过高,不适用于结构未知的大型网络等问题,结合谱聚类在识别未知分布数据集聚类方面的优势,以及模块度函数能够在大型网络中搜寻出最佳社团数目的能力,提出了基于谱聚类的社团发现算法--SCCF算法.实验结果表明,与已有的社团发现算法相比,SCCF算法效率更高,并且能够在网络节点数上万的大型网络中得到高质量的社团结构.     

复杂网络社区挖掘——-基于聚类融合的遗传算法

针对当前研究复杂网络社区挖掘的热点问题, 提出了一种基于聚类融合的遗传算法用于复杂网络社区挖掘. 该算法将聚类融合引入到交叉算子中, 利用父个体的聚类信息辅以网络拓扑结构的局部信息产生新个体, 避免了传统交叉算子单纯交换字符块而忽略了聚类内容所带来的问题. 为使聚类融合的作用得以充分发挥, 本文提出了基于马尔科夫随机游走的初始群体生成算法, 使初始群体中的个体具有一定聚类精度并有较强的多样性. 初始群体生成算法与基于聚类融合的交叉算子互相配合, 有效地增强了算法的寻优能力. 此外, 算法将局部搜索机制用于变异算子, 通过迫使变异节点与其多数邻居在同一社区内, 有针对性地缩小了搜索空间, 从而加快了算法收敛速度. 在计算机生成网络和真实世界网络上进行了测试, 并与当前具有代表性的社区挖掘算法进行比较, 实验结果表明了该算法的可行性和有效性.     

基于黎曼流形的多视角谱聚类算法

现有的多视角谱聚类算法大多只线性结合了各视角的基拉普拉斯矩阵,未考虑不同视角数据的差异性对最优拉普拉斯矩阵的影响,存在聚类性能受限的问题。提出一种基于黎曼几何均值与高阶拉普拉斯矩阵的谱聚类算法(RMMSC),挖掘多视角数据中的高阶连接信息与流形信息,提高最优拉普拉斯矩阵对各视角的信息利用率。按一定的权重线性结合数据单一视角的各阶拉普拉斯矩阵,得到每个视角的基拉普拉斯矩阵,通过低阶与高阶连接信息的结合使用,充分体现多视角数据集的全局结构。在此基础上,计算各视角基拉普拉斯矩阵的黎曼几何均值,将其作为最优拉普拉斯矩阵输入谱聚类算法,得到聚类结果。相比于传统矩阵算数均值的计算,基于黎曼流形的黎曼几何均值能够更好地恢复互补层数据的流形信息。实验结果表明,RMMSC在多组标准数据集上聚类效果优于ONMSC、MLAN、AMGL等算法。其中,在Flower17数据集上,精确度较基准算法ONMSC提高了2.14%,纯度提高了1.7%,且收敛性较好。     

基于网络社区发现的标签传播聚类算法

高维数据的聚类特性通常难以直接观测. 将其构建为复杂网络, 节点间的拓扑结构可以反映样本之间的关系. 对网络中的节点进行社区发现, 可实现对数据更直观的聚类. 提出一种基于网络社区发现的低随机性标签传播聚类算法. 首先, 用半径和最近邻方法将数据集构建为稀疏的全连通网络. 之后, 根据节点相似度进行节点标签预处理, 使得相似的节点具有相同的标签. 用节点的影响力值改进标签传播过程, 降低标签选择的随机性. 最后, 基于内聚度进行社区的优化合并, 提高社区的质量. 在真实数据集和人工数据集上的实验结果表明, 该算法对各种类型的数据都具有较好的适应性.     

TSCAN:利用并行策略改进的图结构聚类算法

近年来,图数据聚类在学术界引起了广泛的关注,许多优秀的聚类方法,如模块度优化算法、谱聚类,以及基于密度的聚类算法在图数据上取得了很好的效果。SCAN是一种著名的基于密度的图聚类算法,该算法不仅能够找出图中的聚类,而且还能够发现不同聚类间的Hub节点,以及图中的离群点。然而,该算法存在两方面的局限性：首先,在大规模图数据上,该算法需要耗费大量的时间用于计算图中每条边的结构相似性;另一方面,该算法存在两个参数[ε]和[μ],并且对这两个参数比较敏感。为了解决其局限性,提出了一种基于OpenMP的并行算法来求解节点相似性,并且提出了两种有效的负载均衡策略;其次,提出一种基于三角形的新型图结构聚类算法TSCAN。该模型能够有效降低算法对参数的敏感性,而且还能够发现重叠以及更稠密的社区。在多个大规模数据集上实验发现,基于多核的并行算法能够达到近乎线性的加速比,而且TSCAN算法对参数不敏感,能有效发现重叠社区。     

二谱分聚类的复杂网络社团检测方法

近年来,复杂网络中的社团发现越来越受到研究人员的关注并且许多方法被提了出来。为有效地检测复杂网络中的社团结构,优化了评估与发现社团的模块密度函数(即D值)。通过模块密度的优化进程,证明了模块密度函数能写成模块密度矩阵迹的最大化表达形式。利用模块密度矩阵的谱分分解,提出了一种新的二谱分的聚类检测复杂网络社团方法。在LFR标准人工模型网络中验证了二谱分方法的有效性。实验结果显示这种新的方法在发现复杂网络社团上有较高的准确性。     

A community detection algorithm based on Quasi-Laplacian centrality peaks clustering

Searching for key nodes in social networks and clustering communities are indispensable components in community detection methods. With the wide application demand of detecting community networks, more and more algorithms have been proposed. Laplacian centrality peaks clustering (LPC) is an efficient and simple algorithm which is proposed on the basis of density peaks clustering (DPC) to identify clusters without parameters and prior knowledge. Before LPC is widely applied in community detection algorithms, some shortcomings should be addressed. Firstly, LPC fails to search for key nodes in networks accurately because of the similarity calculation method. Secondly, it takes too much time for LPC to calculate the Laplacian centrality of each point. To address these issues, a community detection algorithm based on Quasi-Laplacian centrality peaks clustering (CD-QLPC) is proposed after studying the advantages of Quasi-Laplacian centrality which can replace density or Laplacian centrality to characterize the importance of nodes in networks. Quasi-Laplacian centrality is obtained by the degree of each node directly, which needs less time than Laplacian centrality. In addition, a trust-based function is utilized to obtain the similarity accurately. Moreover, a new modularity-based merging strategy is adopted to identify the optimal number of communities adaptively. Experimental results show that CD-QLPC outperforms many state-of-the-art methods on both real-world networks and synthetic networks.

     

一种基于局部扩展优化的重叠社区发现算法

挖掘复杂网络的重叠社区结构对研究复杂系统具有重要的理论和实践意义。提出一种基于局部扩展优化的重叠社区识别算法。 首先基于网络节点的聚集系数筛选种子节点,选取不相关的、局部聚集系数大的种子作为初始社区;然后采用贪心策略扩展初始社区,得到局部连接紧密的自然社区;最后检测并合并相似的社区,获得高覆盖率的重叠社区结构。在人工生成网络和真实网络数据集上的实验结果表明,与现有的基于局部扩展的代表性重叠社区发现算法相比,所提算法能在稀疏程度不同的网络上发现更高质量的重叠社区。     

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

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

一种加权稠密子图社区发现算法

目前,针对复杂网络的社区发现算法大多仅根据网络的拓扑结构来确定社区,然而现实复杂网络中的边可能带有表示连接紧密程度或者可信度意义的权重,这些先验信息对社区发现的准确性至关重要.针对该问题,提出了基于加权稠密子图的重叠聚类算法（overlap community detection on weighted networks,简称OCDW）.首先,综合考虑网络拓扑结构及真实网络中边权重的影响,给出了一种网络中边的权重定义方法;进而给出种子节点选取方式和权重更新策略;最终得到聚类结果.OCDW算法在无权网络和加权网络都适用.通过与一些经典的社区发现算法在9个真实网络数据集上进行分析比较,结果表明算法OCDW在F度量、准确度、分离度、标准互信息、调整兰德系数、模块性及运行时间等方面均表现出较好的性能.     

复杂网络社团的谱分检测方法

为有效地检测复杂网络中的社团结构,优化模块密度函数,展示模块密度函数怎样被优化框定到谱分聚类问题,提出一种谱分算法,进一步对该算法进行时间复杂度分析。在一个经典的真实世界网络中检验该算法,并与基于模块密度的直接核方法及基于模块函数的谱分方法做比较。特别地,当网络中社团结构变得模糊时,实验结果显示,该谱分算法在发现复杂网络社团上是有效的。     

基于社团划分的网络聚类布局算法

复杂网络日益受到广大专家和学者们的关注,对其进行可视化展示可以帮助用户发现复杂网络表征的复杂系统中隐藏的知识信息,对计算机科学、社会学、生物学等领域具有重要的意义。力导引布局算法是复杂网络可视化领域的主流算法,它用节点连接图的形式对复杂网络进行抽象表示,布局遵循一定的美学标准如节点的均匀分布、边长尽量一致等,这在一定程度上阻碍了对复杂网络的社团结构的展示。针对以上问题,本文提出引入基于度中心性的社团斥力与引力对力导引算法进行改进,以对复杂网络进行聚类布局。实验结果表明,本文算法可有效地展示复杂网络的社团结构,同时又能保留社团之间边缘节点的信息。     

基于核心图增量聚类的复杂网络划分算法

借鉴基于聚类的无监督入侵检测算法(Clustering-based method for the unsupervised intrusion detection, CBUID)聚类原理, 提出一种基于核心图增量聚类的社区划分算法(Clustering-based method for community detection, CBCD). 本文提出一种社区摘要构建方法, 给出节点与社区相似度的计算公式. 首先,对由少量高度数节点组成的核心网络采用现有算法进行核心社区划分, 然后,采用增量方式依据节点与社区相似度,将剩余节点划分到核心社区中. 算法复杂度主要依赖于网络规模、边的数量及划分的社区个数, 具有线性复杂度. 通过在几个典型真实网络数据集上测试, 所提算法能够有效地进行社区划分.     

基于信号自适应传递的社团发现算法

为了准确地检测出复杂网络的社团结构,提出一种基于信号自适应传递的社团发现方法。首先使信号在复杂网络上自适应地传递,从而获取网络中各节点对整个网络的影响向量,然后把网络中节点的拓扑结构转化成代数向量空间上的几何关系,最后结合聚类特性发现网络中的社团结构。为获取更加合理的空间向量,提出最佳传递次数,缩小搜索空间,增强算法寻优能力。该算法在计算机生成网络、Zachary网络和美国大学生足球赛网络上进行实验测试, 并与GN算法、谱聚类算法、极值优化算法和信号传递算法进行实验对比,社团划分的准确性和精确性均有所提高,证明该算法具有有效性和可行性。