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

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

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

对基于聚类技术的复杂网络社团发现算法进行研究,分析网络中结点间的相似性度量方法,提出把复杂网络中的结点转化为向量的顶点到向量映射(MVV)算法,把网络中的结点转化成适合聚类算法的数据结构形式.对不同聚类算法及相似性度量方法的性能进行比较分析,结果表明,MVV算法可以提高发现复杂网络中社团的能力.     

基于聚类粒化的社团发现算法

为了实现复杂网络社团发现算法的复杂度和精确度间的均衡,提出一种基于聚类粒化的社团发现算法(CGCDA),将网络粒化获得的粒子视为一个社团,粒化结果即为对网络的社团划分。首先,将网络中的每个节点视为基本粒,通过初始粒化操作实现对网络的粒化;然后,针对获得的粒化集合中满足粒化系数的粒子进行聚类粒化操作,分层粒化直到不存在满足要求的粒子对;最后,将粒子对中的重叠节点视为孤立点,用邻居节点投票法把孤立节点归并到相应的粒子中,实现对复杂网络的社团划分。实验实现了Newman快速算法（NFA）、标号传播算法（LPA）和CGCDA。实验结果表明,CGCDA在四个基准数据集上可获得平均高于LPA 7.6%的模块度和低于NFA 96%的时间。CGCDA时间复杂度较低,获取的社团模块度较高,实现了社团发现时间和精确度的均衡,相比NFA、LPA总体性能更优。     

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

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

基于自适应仿射传播聚类的社团发现求解

本文对复杂网络的社团发现问题进行研究,分析社团发现问题和聚类问题的相似性,使用自适应仿射传播聚类算法对社团发现问题进行求解,给出了算法的实例,针对算法中的不同参数进行测试比较。结果表明算法具有较好的准确率和运行效率。     

基于K-means聚类算法的复杂网络社团发现新方法

提出了一种基于K-means聚类算法的复杂网络社团结构划分方法。算法基于Fortunato等人提出的边的信息中心度,定义了节点的关联度,并通过节点关联度矩阵来进行聚类中心的选择和节点聚类,从而将复杂网络划分成k个社团,然后通过模块度来确定网络理想的社团结构。该算法有效地避免了K-means聚类算法对初始化选值敏感性的问题。通过Zachary Karate Club和College Football Network两个经典模型验证了该算法的可行性。     

复杂网络中的社团结构发现方法

社团结构是真实复杂网络异质性与模块化特性的反映。深入研究网络的社团结构有助于揭示错综复杂的真 实网络是怎样由许多相对独立而又互相关联的社区形成的,使人们更好地理解系统不同层次的结构和功能,具有广泛 的实用价值。总结了目前常用的社区发现方法,包括经典的GN算法、模块度优化算法、基于网络动力学的方法以及 统计推断方法;用社区划分基准测试网络Zachary对上述算法进行了实验,对这几类算法的时间复杂度和优缺点进行 了比较分析。最后,对复杂网络的社区结构发现算法的研究进行了展望。     

基于HMM的动态社会网络社团发现算法

随着互联网的不断发展,大多数社会网络已逐渐显示出动态特性,动态社会网络社团分析对理解现实生活中社会网络结构和功能具有非常重要的意义.针对动态社会网络中的社团发现问题,提出一种基于隐Markov模型(hidden Markov model, HMM)的HMM_DC算法.该算法考虑到社会网络的动态特性,结合历史信息,将社团发现转化为求解隐马尔可夫模型中的最优状态序列问题,将网络中的社团结构和节点信息分别采用状态链和观察链表示,在无须指定额外参数的情况下实现动态网络的社团结构发现.最后,利用该算法和其他算法对VAST数据集、ENRON数据集和Facebook social network数据集进行实验仿真.仿真结果表明：该算法能够快速、准确地发现真实动态网络中的社团,其模块度Q值和互信息NMI值有很大提升.     

基于复杂网络社团划分的Web services聚类*

以单词为网络节点,由自然语言描述中单词的同现频率确定单词间的相关度并作为边的权值,构建自然语言描述集合的加权单词网络模型。利用Newman快速算法对加权单词网络模型进行社团划分,得到单词聚类结果;根据单词聚类结果与服务之间的映射关系实现服务聚类。实验结果与手工分类结果的对比表明,平均查准率达74.7%以上。     

基于K means聚类算法的复杂网络社团发现新方法*

提出了一种基于Kmeans 聚类算法的复杂网络社团结构划分方法。算法基于Fortunato等人提出的边的信息中心度,定义了节点的关联度,并通过节点关联度矩阵来进行聚类中心的选择和节点聚类,从而将复杂网络划分成k个社团,然后通过模块度来确定网络理想的社团结构。该算法有效地避免了Kmeans 聚类算法对初始化选值敏感性的问题。通过Zachary Karate Club和College Football Network两个经典模型验证了该算法的可行性。     

基于核心图的标签传播算法

网络中的社团发现是当前的一个研究热点.在众多社团发现算法中,标签传播算法因简单快速而被广泛应用,但标签传播算法也存在结果稳定性较差的问题.基于此对标签传播算法的初始化过程进行改进,提出了基于核心图的标签传播算法.通过计算图中任意两点的k阶公共邻居,将具有最大相似性的节点及k阶邻居作为初始核心社团,并为其分配初始标签.通过上述过程,提取一些较为紧密的子结构来作为标签传播的初始社团,并给这些结构分配初始社团标签.在真实网络中的实验结果表明,该算法可以大幅提高结果的稳定性.     

基于进化谱分方法的动态社团检测

为了有效地分析动态网络中的社团结构功能和特性,在进化时间平滑框架下基于进化聚类方法对模块密度函数和否定平均关联函数进行了优化,论证了理论可行性;在此基础上提出了检测动态网络社团结构的进化谱分算法,并对两类算法进行了详细的谱分分析。分别在计算机合成的动态网络以及真实网络中检验了所提算法的准确性和有效性,并将其与其他算法进行对比。实验结果表明,所提算法对动态网络中的社团检测仍有很高的准确性和有效性。     

Evolutionary Clustering for Mining and Tracking Dynamic Multilayer Networks

This article proposes a framework for community discovery in temporal multiplex networks by extending the evolutionary clustering approach to encompass both time and multiple dimensions. In this extended framework, the problem of finding community structures for time‐evolving networks with multiple types of ties is reformulated by adding the concept of dimensional smoothness, relative to a single timestamp, to that of temporal smoothness, at the base of evolutionary clustering. At each timestamp, the method tries to maximize the quality of the clustering obtained for the current multidimensional network and to minimize the differences with respect to that obtained at the previous timestamp. Moreover, the evolution of a community between two consecutive timestamps is maintained by exploiting the Hungarian approach, which determines the best cluster correspondence between two consecutive timestamps. Experiments on synthetic and real‐world networks show the capability of the approach in discovering and tracking group organization of actors constituting the network.     

复杂网络社区发现研究进展

近年来,随着现代网络通信和社会媒体等技术的飞速发展,复杂网络成为多学科交叉研究的热点之一,社区发现是复杂网络中的一个重要问题,对其进行研究具有重要的理论意义和应用价值。该问题吸引了多个学科领域的众多学者的关注,并且已有许多社区发现算法被提出。已有的社区发现综述多是侧重某一方向或特定领域展开,基于此,文中在之前工作的基础上,对国内外社区发现工作进行了深入调研,较全面地阐述了复杂网络社区发现的研究现状。首先,针对不同网络结构,给出社区发现的问题定义和主要的评价指标。然后,介绍了不同网络结构中的经典社区发现算法,包括同质网络中的全局社区发现、局部社区发现算法,异质网络中的二分网络、三分网络和多分网络中的社区发现,结合节点内容和连接结构的社区发现算法,以及动态网络中的社区发现和社区演化工作。最后,简要介绍了社区发现的典型应用,包括影响最大化、链路预测和情感分析领域的应用。此外,探讨了当前社区发现研究面临的主要挑战,试图为社区发现研究领域勾画一个较为清晰和全面的轮廓,为初学者提供指引。     

基于节点相似度的网络社团检测算法研究

社团结构是众多复杂网络的统计特性之一,挖掘网络中存在的社团结构日益受到人们的普遍关注。网络中的社团结构检测本质上类似于传统机器学习领域的聚类分析,其关键问题在于如何定义网络中节点间的相似度。首先提出了基于节点相似度的节点分裂算法SUN,相比传统的基于边界数(betweenness)的节点分裂算法GN, SGN在速度和精度上都有明显改善;接着,在利用各种节点相似度计算方法得到节点间的相似度之后,采用几种经典的聚类分析算法对网络进行社团划分,在模拟数据和真实数据上的实验表明:基于网络拓扑结构信息的signal和regular方法优于基于网络节点局部信息的Jaccard方法,而且对于复杂网络社团划分问题,如果选择好的网络节点相似度构造方法,已有的基于相似度矩阵的聚类分析算法都能快速有效地对网络社团进行划分。     

基于社区划分的多线程潜在好友推荐算法

针对基于社区划分的潜在好友推荐算法FRCD运行速度慢的问题,提出了一种基于社区划分的多线程潜在好友推荐算法MTFRCD。该算法在网络拓扑图上利用多线程技术寻找核心关系子网,以核心关系子网作为标签种子节点,使用多线程并发传播标签来发现网络拓扑图上的社区结构,利用社区发现结果在社区内部推荐潜在好友。人工网络的实验结果表明,MTFRCD相比于传统的FRCD,在性能近似的前提下具有明显的速度增长。因此,将该算法应用于真实社交网络（学者网）平台的潜在好友挖掘和推荐,根据推荐结果的评测,验证了算法具有良好的推荐效果。     

基于社区的动态网络节点介数中心度更新算法

随着互联网技术的迅猛发展,社会网络呈现出爆炸增长的趋势,传统的静态网络分析方法越来越难以达到令人满意的效果,于是对网络进行动态分析就成为社会网数据管理领域的一个研究热点。节点介数中心度衡量的是一个节点对图中其他点对最短路径的控制能力,有利于挖掘社会网络中的重要节点。在图结构频繁变化的场合,若每次变化后都重新计算整个图中所有节点的介数中心度,则效率将会很低。针对动态网络中节点介数中心度计算困难的问题,本文提出一种基于社区的节点介数中心度更新算法。通过维护社区与社区、社区与节点的最短距离集合,快速过滤掉那些在网络动态更新中不受影响的点对,从而大大提高节点介数中心度的更新效率。真实数据集和合成数据集上的实验结果表明了论文所提算法的有效性。     

基于拟态计算的社会网络划分算法

信息社会中,社会网络结构的形成与演变是一个动态过程,拟态计算(Mimic Computing,MC)是根据资源、任务、安全、服务和时效性等不同约束条件,动态适应用户不同的应用需求,改进计算模式的一种计算架构,是当前适应动态多变网络环境的一种有效方法。基于拟态计算,应用当前研究前沿的传染病SIR模型,提出了基于拟态计算的社会网络划分算法(Mimic Community Clustering,MCC)。应用该方法进行网络社区划分,并用真实数据来验证模型的可行性和有效性。     

基于多目标演化聚类的大规模动态网络社区检测

动态网络社区检测能揭示社区结构随时间演变的规律,是目前网络社区研究领域的热点之一.基于演化聚类的方法被广泛采用,但存在2个主要问题：1)缺乏结果校正机制,容易产生“结果漂移”和“误差累积”问题;2)问题的NP-难本质,导致基于模块度的精确社区结构检测在效率上存在很大问题.针对以上问题,通过对传统演化聚类框架和离散粒子群算法的改进及有效结合,提出一种高效且有效的多目标动态社区检测方法(multi-objective discrete particle swarm optimization for dynamic network, DYN-MODPSO),主要工作包括：1)提出基于最近未来参考策略的初始聚类结果校正方法,提高动态社区检测结果的有效性;2)改进传统粒子群算法,使其能与演化聚类框架有效结合;3)提出基于去冗余的随机游走初始群体生成方法,提高传统粒子群算法中的个体多样性并保证个体的初始精度;4)提出多个体交叉算子及改进的干扰算子,提高算法的局部搜索能力与收敛能力.大量基于真实和人工动态网络数据的实验结果证实,提出的方法在效率和有效性方面,显著优于同类比较算法.