基于联合引力度扩展的加权网络重叠社区划分算法

基于引力度扩展的重叠社区发现算法(GDE),主要用于挖掘无权社交网络的重叠社区结构.真实社区更多是具有加权属性的,本文根据 GDE 算法的种子策略思想,并依据加权网络的特征,以网络节点的度与强度来综合确定重叠社区的中心节点,提出基于联合引力度扩展的加权网络重叠社区划分算法(UGDE).算法的实验检测结果表明：该算法对划分加权网络中的重叠社区具有可行性与有效性.     

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

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

基于加权边相似度的重叠社区发现算法

社区发现是复杂网络研究的基础,其目的是发现网络的真实结构,对于分析复杂网络的拓扑结构、理解其功能和寻找其潜在的性质具有重要的意义.Palla,Yong和James等人分别提出了CPM、LINK算法,此类算法基于网络拓扑结构或边密度发现复杂网络中的社区,性能较好,但不足是计算出的社区存在过度重叠问题.如何设计新算法,避免社区发现的过度重叠问题,是一个亟待解决的重要问题.本文基于加权边相似度,提出了一种社区发现算法LINKw,可以高效发现社区结构,与其他算法相比,本算法能更好地解决社区过度重叠问题.     

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

发现复杂网络中的重叠社区是目前复杂网络分析的重要内容。选择社区代表性强的节点作为种子节点进行扩展是基于种子扩展策略重叠社区发现算法的关键,提出了一种基于度信息和邻域连通性的节点邻域中心性度量指标,并在此基础上提出了一种基于局部邻域连通性的重叠社区发现算法（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分数上优于多数对比算法,可得到与网络真实社区更匹配的社区结...     

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

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

一种基于加权共同邻居相似度的局部社区发现算法

传统的社区发现算法能够找出网络中所有的社区,其时间复杂度取决于网络的规模.挖掘大网络中的全局社区结构因为时间复杂度高而难以实现,局部社区发现作为一种不需要知道网络的整体结构,从给定的节点逐步向外扩展,寻找该节点所在社区的方法,在大网络时代具有重要的应用意义.目前这方面的研究已经获得广泛关注,并提出了很多局部社区发现算法.针对已有局部社区发现算法需要人工设置参数、准确率低的问题,提出一种新的局部社区发现算法.首先,提出一种加权邻居节点的共同邻居相似度指标,用于计算网络中两个节点间的相似度;然后,基于该相似度指标,给出一种新的局部社区质量度量指标,在保证社区度量指标不下降的前提下,不断选择与当前局部社区嵌入度最大的节点加入到局部社区,逐步找出给定节点所在的社区;最后,在真实网络和仿真网络数据集上进行了实验.实验结果表明,该算法能有效地挖掘出给定节点所在的局部社区,相比具有代表性的Clauset,LWP,GMAC等局部社区发现算法有更高的准确率.     

一种基于介数和时效性的动态社区发现算法

为了发现动态变化的社区结构,在分析了动态社区划分算法的研究现状基础上,提出一种基于时效性和介数的动态社区发现算法,对历史信息的时效性进行了计算,建立了综合有权网络,基于局部边介数进行社区划分,发现了稳定社区结构。实验表明了算法的有效性。     

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

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

动态网络中基于局部介数的重叠社区发现算法

针对现有静态网络社区发现算法的失真和动态网络社区发现算法时间复杂度较高的问题,本文提出了一种动态网络中的重叠社区发现算法。在网络中,边介数最大的边或分割介数最大的节点是网络中的关键边或点,即联系最不紧密的边或节点,因此,该算法利用去除最大边介数的边和分裂最大分割介数的节点的方法,并将网络社区的动态变化和重叠性考虑在内进行社区发现。最后利用模块度对社区发现进行控制,使发现的社区结构更加合理。     

基于边信任度的混合参数自适应重叠社区发现算法

网络中的社区结构有助于简化网络拓扑结构分析,揭示系统内部的规律,能够为信息推荐和信息传播控制提供有力的支撑.网络重叠社区结构与真实生活更加接近,但其分析较非重叠社区结构更加困难.因此,针对重叠社区发现问题,在对网络的边进行峰值聚类的基础上提出了一种基于边信任度的混合参数的自适应重叠社区发现算法.定义了网络边的邻居边集合及与其邻居边之间的信任度函数,通过信息传递获取边的总信息量,并且基于此引入混合参数的概念.基于k-means算法使用混合参数对网络中的边进行聚类,即将网络中的边划分为核心边集与非核心边集,每个核心边作为一个聚类中心.根据非核心边到核心边的距离将所有非核心边划分至距离其最近的聚类中心所在社区.再根据网络中边与节点的关系实现重叠节点发现,最终实现重叠社区的发现.该算法的优点是每条边通过独立地完成信息扩散找到社区的结构,相比于传统的峰值聚类算法,不需要人为设置相关参数,实现重叠社区的自适应发现.为验证算法的可行性,对算法复杂度进行了分析,并且使用两种社区划分评价指标——标准化互信息和模块度,分别在人工数据集及6种真实数据集上进行实验,通过与其他算法进行对比分析,实验结果表明该算法更具可行性和有效性.     

COT:一种连续时间序列建模的社区发现算法

研究基于交互及内容数据发现交往密切的交互社区,以及这些社区如何随时间发展变化,对于网络营销、内容推荐等应用具有重要意义。已有的基于内容与链接分析的混合模型大都未能对交互行为中广泛存在、且显著影响社区结构的时序信息进行统一建模分析。基于贝叶斯图模型,提出了一种可综合考虑交互信息、网络结构以及交互行为时间信息的社区发现模型COT(community over time),可用于从在线社交网络的交互数据中发现具有特定主题倾向及周期性行为模式的动态交互社区。模型采用Gibbs采样进行贝叶斯统计推断,通过在新浪微博真实数据集上的实验验证,可以有效应用于在线社交网络中并取得较高的精细度和可解释性。     

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

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

一种全局与局部结合的两步式重叠社区挖掘算法

基于全局划分和局部凝聚原理,改进得到一种两步式挖掘算法,该算法以寻找最优模块性Q值为基准,最终挖掘出重叠社区.对两个经典真实世界网络的Zacharys Karate俱乐部数据和海豚网络数据进行了实验测试,实验表明该算法能够有效地划分出重叠社区.     

在线社会网络的动态社区发现及其演化

分析了目前动态社区发现及其演化所存在的问题,提出了一种新的动态社区演化方法.该方法利用静态社区挖掘算法提取不同时间快照的每个社区,然后计算出相邻快照的社区之间的演化影响力,进一步分析连续快照中社区结构的发展演化过程.在新浪微博、网络测量Gnutella等大规模实验数据集上的验证,证明了该方法的有效性.此外,实验中还分析了社会网络中节点的出现和消失的频繁程度会影响社区稳定性以及社区结构的演化.      

基于结构和适应度的社区发现

复杂社会网络无处不在,对复杂社会网络进行社区发现越来越被人们重视.基于局部结构的社区发现可以在不用了解全局的情况下对某些节点进行划分;社会网络的社区适应度特性可以找出不同适应度下的社区结构.基于局部结构以及社区适应度的网络属性,提出一种新的社区发现算法.通过实验比较,算法能较好、较快的发现社区结构,在人工网络以及真实社会网络均取得较之已有方法更好的效果.     

有向网络兴趣社区的快速挖掘算法及其在僵尸粉检测中的应用

针对传统的无向网络社区挖掘方法无法实现大规模有向网络中社区有效发现的问题,提出了一种新的有向图社区及其兴趣特征快速挖掘算法。采用贪心算法求解社区划分模块性最大化的优化问题,较好地平衡了有向图社区挖掘中准确性与有效性之间的矛盾,实现对大规模微博类有向网络社区结构的有效识别;基于发现的社区,采用tf-idf算法进一步挖掘社区用户的兴趣爱好,实现了对微博网络中兴趣小组的精确挖掘。基于新浪微博的实验结果表明:所提算法不仅可以快速有效地挖掘有向网络中的社区结构及其用户的兴趣特征,还能够准确地检测出微博网络中的僵尸粉社区,研究结果对微博系统的净化、谣言控制、网络广告的精准投放等研究具有重要的参考价值。     

基于重叠节点的社会网络最短路径算法

通过路径发现和分析可以挖掘社会网络中人与人之间的关系及其连接特性,特别是在犯罪网络的应用中具有重要意义。通过社区发现算法获得社区间的重叠节点,并构造目标网络的分层网络模型;基于社会网络的高聚集系数特性及幂律分布拓扑特征,提出了基于重叠节点的分层网络路径发现(HOLN)算法,以核心节点距离代替社区间距,优化路径搜索方向;优先搜索重叠节点,简化对节点的遍历,实现源与目标间最短路径的快速发现。实验结果表明,本文提出的HOLN算法在计算精度和运行效率上都有令人满意的表现。     

社会网络中的社区挖掘算法研究

结合点社区和边社区的优点,对边社区结构,采用网络中的局部信息进行挖掘,以边适应度和点相似性为基础,提出了新的社区挖掘算法.根据特定的中心性原则设定一条初始的边作为种子,为了得到该边所在的局部社区的社区结构,不断最大化一个适应度函数,并通过基于点相似性的模块度函数来进行边界点识别.     

基于静态和动态的社会网络挖掘算法

基于社会网络的静态和动态特征, 研究社会网络中的社区发现问题. 针对静态社会网络, 提出了边的Ξ系数及紧密度阈值等概念和Detstructure算法; 针对社会网络的动态特性, 提出了基于衰减策略的融合挖掘算法. 所提出的两种算法在应用中都取得了较好的效果.     

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

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