局部引力度扩展的重叠社区发现算法

社交网络拥有社区结构,而网络中的一些节点又被两个或更多社区共享,这就使网络呈现出重叠社区结构.在前面对重叠社区划分算法的研究中提出了基于引力度扩展的重叠社区发现算法(GDE),以引力度最大的节点为种子来扩展与发现重叠社区.这里,提出基于h-域的局部引力度扩展的改进算法(LGDE).改进算法的实验测试结果表明该算法的执行效率获得了极大的提高,并且是可行的.     

基于共邻节点相似度的加权网络社区发现方法

为实现加权网络的准确划分,发现真实的社区结构,提出一种基于模块度和共邻节点相似性的层次聚类社区划分方法IEM.首先,定义两节点间基于共邻节点的相似度.之后,基于该度量快速聚合当前节点和与其关联紧密度最强的邻居节点以形成初始社区,并进行社区扩展.最后,以最大化网络模块度为目标进行社区合并以优化划分结果.算法通过形成初始社区、扩展社区、合并社区三步,实现了加权网络合理有效的社区划分.以加权模块度作为社区划分质量的评价标准,在多个数据集上的实验结果表明,IEM算法优于加权CN、加权AA、加权RA.同时,与CRMA算法相比,IEM算法对加权网络社区划分的有效性和正确性更高.     

基于局部邻域连通性的重叠社区发现算法

发现复杂网络中的重叠社区是目前复杂网络分析的重要内容。选择社区代表性强的节点作为种子节点进行扩展是基于种子扩展策略重叠社区发现算法的关键,提出了一种基于度信息和邻域连通性的节点邻域中心性度量指标,并在此基础上提出了一种基于局部邻域连通性的重叠社区发现算法（Local Neighbor-hood Connectivitybased overlapping community detection Algorithm,LNCA）。首先计算每个节点的局部邻域连通熵和邻域中心性cc,选择中心性高的节点作为种子节点;然后采用带重启的随机游走策略扩展种子节点并得到初始社区;最后合并重叠度较大的社区得到最终社区发现结果。在6个带真实社区标签的网络和9个无真实社区标签的网络上,与SLP A、DEMON、CPM、Node_Perception、Ego_Networks、Egonet_Splitter等6个经典重叠社区发现算法进行比较,结果表明,在带标签网络上,LNCA算法在重叠NMI和F1分数上优于多数对比算法,可得到与网络真实社区更匹配的社区结...     

采用模糊层次聚类的社会网络重叠社区检测算法

为了能够发现社会网络中的重叠社区以及解决重叠社区之间关系的模糊性和层次性,提出了一种基于模糊层次聚类的重叠社区检测算法(CDHC)。算法中引入了距离加权因子来计算社区间的相似度,通过模糊层次聚类来合并相似度高的社区;针对合并生成的原始社区计算社区中节点的隶属度,再将隶属度小于阈值的节点从社区中移除,从而形成最终的网络重叠社区结构。该算法不仅可以发现重叠的社区结构,还可以处理孤立节点。在Lancichinetti基准网络和真实网络上将CDHC算法与具有代表性的重叠社区发现算法CMP和LFM进行了比较,结果表明:影响社区检测精度的主要因素是社区间的混合程度,而网络规模和网络中社区的规模的影响并不显著;CDHC算法在小社区网络上的社区检测精度优于LFM,在大社区网络上的社区检测精度优于CMP。CDHC算法在保持社区检测质量的同时,还具有较好的稳定性,是一种有效的社会网络重叠社区检测算法。     

基于标签传播的重叠社区发现算法

重叠社区发现是复杂网络研究的重要课题.提出一种基于标签传播的重叠社区发现算法.首先利用标签传播算法得到初始无重叠社区划分结果,之后通过设计新的重叠节点识别算法确定重叠节点,最后再根据重叠节点的识别结果对社区进行合并从而得到最终的重叠社区划分结果.该算法克服了已有算法重叠节点占比过大的弊端.为验证算法的有效性,在LFR人工数据集、3个标准公开测试集以及真实的大豆基因共表达网络上进行实验,并与已有算法进行对比.实验结果表明,该算法性能明显优于对比算法,极大地改善了重叠节点比重过大问题.     

基于Louvain重叠社区发现算法

重叠社区发现技术对于分析网络社区间关系具有重要意义,本文提出了基于Louvain重叠社区发现算法,该算法在Louvain算法的基础上使用模块度Q的增益度函数dq判断节点是否具有重叠性,并且发现重叠社区;设计实验验证该算法,使用经典数据集American College Football对该算法与常用重叠社区发现算法CPM、LFM和COPRA进行实验对比,结果表明:增益度函数dq能判断重叠节点,且通过找到社会网络中的重叠节点发现重叠社区;该算法在重叠模块度EQ上比CPM、LFM和COPRA算法分别提高17.05%、12.81%和9.45%,在运算时间上比CPM算法、COPRA算法分别增加了12.62%、7.15%,比LFM算法减少了23.06%,表明在综合重叠模块度EQ与算法时间上,本文基于Louvain重叠社区发现算法都优于其他的算法。     

基于拓扑势的局部化重叠社区识别

针对传统社区识别算法中需要根据先验知识设定参数、 社区划分结果具有随机性及复杂度过高的问题, 提出一种基于拓扑势的局部化重叠社区识别算法. 该算法通过引入拓扑势计算节点的影响力, 利用节点间的局部相似性度量指标, 采用标签传播策略进行重叠结构的社区识别. 在真实网络及人工合成网络上与多种经典算法进行对比实验验证了算法的高效性.     

融合节点影响力与多标签传播的重叠社区发现算法

重叠社区发现是复杂网络分析研究的重要目标之一。针对传统多标签传播算法存在的社区发现结果具有随机性、不稳定性,以及忽视节点影响力对标签传播的影响等问题,提出一种基于节点影响力与多标签传播的能够生成稳定社区的重叠社区发现算法。算法在节点影响力的计算、排序和核心节点识别基础上,通过邻居节点初始标签的再处理和基于平衡系数的节点标签异步更新策略,实现复杂网络重叠社区的有效识别。在真实数据集和人工数据集上的实验综合表明,算法性能优于各对比算法,适用于大规模复杂网络。     

一种基于极大完全图扩展的社区挖掘算法

社区挖掘是复杂网络分析中一项重要工作.目前已有许多好的社区挖掘算法,但这些算法大多基于节点间的连接关系发现内聚的社会团体,而实际网络中节点大多具有不同的行为和影响力.基于此,充分考虑社区内节点相互连接紧密以及节点具有不同影响力的特性,提出一种基于极大完全图扩展的社区挖掘两阶段算法.第一阶段:从内聚的子团和度中心性节点的影响力出发,从网络中选取分散的k个内聚的且有影响力的极大完全图作为初始社区;第二阶段,基于局部社区模块度扩展方法,将重叠节点和初始社区外节点扩展到与其连接紧密的相应社区内.最后通过仿真实验验证了该算法的有效性.     

一种基于核心节点扩展的社区挖掘算法

在充分考虑网络中节点间的连接关系和节点的影响力的基础上,提出一种基于核心节点扩展的社区挖掘算法。算法分为三个阶段:首先,网络中的前k个核心节点逐层向外扩展,直至覆盖网络中大部分节点,各核心节点与其多层邻居节点组成候选初始社区;然后,对候选初始社区进行重叠处理,计算候选初始社区两两之间的重叠度,将重叠度高于阈值的两个社区中相对小的社区删掉,形成初始社区;最后,计算初始社区间的重叠节点和不在初始社区中的节点到各个初始社区的连接度,将连接度最大的节点加入相应社区,不断迭代,直到网络中所有节点都划入到相应社区内,形成最终社区结构。试验结果说明了本文方法的有效性和灵活性,相比GN算法和FN算法,能够实现准确的网络划分;相比Hub算法和Top Leaders算法,由于对候选初始社区间进行了重叠处理,对预置的社区数量k在一定范围内不敏感。     

基于最小社团链接度增量的社团结构挖掘算法

针对复杂网络社团结构挖掘算法复杂度高的问题,定义了一个衡量局部社团结构的指标,提出了一种基于最小社团链接度增量的社团结构挖掘算法.本算法的时间复杂度为O(kd),其中d为网络的平均节点度数,k为搜索的节点数.为了验证本算法的性能和计算的准确性,把本算法与一种经典的挖掘局部社团结构方法——Clauset算法,进行了比较.实验结果表明:本算法抽取的社团结构与Clauset算法相比基本一致,但在性能上有了显著提高.     

一种基于高阶组织的学习者潜在重叠社区检测算法

学习者网络拓扑结构稀疏,且传统的社区检测算法无法为惰性/冷启动学习者检测其潜在的社区。针对该类问题,提出了一种基于高阶组织的学习者潜在重叠社区检测算法(POCDL)。POCDL算法是一种局部图聚类算法,首先利用社交化在线课程平台中的好友关系、同学关系和师生关系解决学习者网络数据稀疏问题;然后挖掘学习者网络中的高阶组织并重构学习者网络;最后,根据学习者的度中心性选取初始种子集,根据社区归属度和社区亲密度进行局部社区检测。在人工网络和学者网真实网络数据集上的实验结果表明：POCDL算法能够较好地为惰性/冷启动学习者检测社区;对其他类型的复杂网络也具有一定的普适性。     

交联网络中的可重叠社团结构分析算法的研究

社团结构是复杂网络呈现出的一个重要特征。现有的社团结构分析算法都是针对非交联结构的复杂网络，并且大多数是将网络划分为若干相互分离的社团，无法对彼此重叠、互相关联的社团结构进行分析。本文根据交联网络的结构特点，提出了交联网络中可重叠社团结构分析算法（IBCPM算法）。本文利用该算法对用户收藏文章的交联网络进行了社团结构分析，并对所获得的社团结构进行了统计分析。实验结果显示了该算法的有效性及效率，并且发现社团重叠量的累积分布与节点所属社团数的累积分布也具有幂律分布的特征。     

有向网络下的CoDA社区发现算法评估

CoDA算法是一种基于概率模型的能识别二分结构的社区发现算法。为了验证该算法的社区划分效果,采用信息检索领域的F-measure标准,对有向网络下重叠社区和非重叠社区的CoDA社区发现算法进行评估。F-measure标准中F1-measure值的大小能反映CoDA算法社区划分效果的优劣。实验所用的数据集由LFR Benchmark工具生成,数据集中节点数最小为100,最大为20 000,每增加100节点对CoDA算法社区划分效果评估一次。分析实验结果可以得出,当节点数小于1 600时,CoDA算法的划分效果较好。当节点数大于1 600时,随着节点个数增多,CoDA算法社区划分效果逐渐变差。由此说明,基于概率模型的CoDA算法适用于小规模社交网络社区的划分。     

面向延迟容忍移动传感器网络的重叠社区节点检测方法

延迟容忍移动传感器网络(DTMSN)呈现重叠社区结构特征,对重叠社区节点进行准确检测可有效提高网络运行效率。提出了适用于DTMSN的重叠社区节点检测方法。依据节点相遇信息挖掘节点移动轨迹规律,从而对其所属初始社区进行判定;进而,设计了节点社区隶属度估计方法,据此进行重叠社区节点的准确检测。仿真结果表明,相比已有方法,所提方法可分别提高平均检出率、平均负载率14%、15%以上。     

面向大规模在线社交网络的社团抽取算法

针对现有的社团分析算法无法在大规模网络上应用的问题,提出一种社团抽取算法,可以高效地分析网络的社团特征.该方法无需事先获取网络的全部拓扑结构,采用网络搜索与社团判定相结合的思路,可有效地抽取结构未知的社交网络上的某个特定社团,从而使分析超大规模网络社团结构成为可能.在仿真数据集上进行实验,分析抽取准确率的影响因素,得出网络平均度越大抽取准确率越高.进一步实验结果表明,社团抽取算法的准确率与现有方法接近,并且执行效率明显高于现有方法,验证了该算法的可行性和有效性.     

基于社区森林模型的分布式重叠社区发现算法

重叠社区发现是复杂网络挖掘中的重要基础工作,可以应用于社交网络、通讯网络、蛋白质相互作用网络、代谢路径网络、交通网络等多种网络的数据分析,从而服务智慧交通、传染病防治、舆情分析、新药研制和人力资源管理等领域.传统的单机运算架构已经难以满足各类大规模复杂网络的分析和计算要求.人工智能领域的研究人员提出将社区发现应用到网络...     

基于标签传播的稳定重叠社区挖掘算法研究

为解决重叠社区挖掘算法中效率与稳定性不能兼顾的情况,本文提出了一种基于标签传播的稳定重叠社区挖掘算法（SOCLP）。该算法首先利用两种标签选择策略解决了基于标签传播算法中的稳定性问题,然后又通过引入平衡因子对算法的稳定性进行了有效的控制。实验结果证明,本文所提出的SOCLP算法可以同时关注社区挖掘的质量、效率和稳定性。     

基于先验知识与模块性的网络社区结构探测算法

在分析模块性指标和Newman有关网络社区结构探测算法的基础上，提出了一种基于先验知识与模块性的社区结构探测算法．利用节点度等社会网络结构先验知识，获得一个社区结构的基本划分，然后进行社区的合并，以此获得一个清晰的社区结构．经计算机模拟网络、Ucinet软件网络和中国农民工社会网络的社区结构探测，结果表明所提算法比Newman的迭代次数减少近50％，并且可以获得更好的模块性指标．