集合扩充的社团分解算法

社团结构是复杂网络的重要特征之一,寻找网络中的社团对于分析整个网络的结构和功能都有非常重要的意义.综述了一些经典的复杂网络社团结构划分的算法,提出了一种基于集合扩充的社团结构划分的新算法.该算法以网络中相邻的两个节点构成的集合为起点,用社团同外部联系的边的数目与社团内部边的数目的比值作为度量指标,通过计算将某一个邻居节点加入该集合后度量指标值的变化情况来判断某个邻居节点是否加入该集合,若度量指标值变小则将该邻居节点加入该集合,若度量指标值变大则不将该邻居节点加入该集合,直到不再有新的邻居节点加入时,一个社团就被划分出来.在剩下的网络中重复这个过程直到网络中的节点完全被划分.用社团结构分解中的两个经典例子测试了该算法,从测试结果来看,用该方法能够合理地划分网络中的社团结构,且运算量小,运行效率高,达到了预期目标.该社团结构的划分方法对于规模较大的复杂网络也具有普遍意义.     

面向多源社交网络的社团结构特征研究（研究生论坛）

为了研究社交网络社团结构对舆情传播的影响,本文对比分析了多源社交网络的社团结构特性及传播特性,并且利用COPRA算法和LFM算法进行了社交网络重叠社团研究,提出一种基于节点度过滤的LFM改进方法——NF-LFM算法。该算法对好友关系网络中节点度小于某一阈值的节点进行过滤,再对剩下的好友关系网络进行社团划分。实验结果表明：1）人人网、QQ空间、新浪微博都具有明显的社团结构特性,其中人人网和QQ空间的社团结构特性强于新浪微博;2）在不考虑社交网络用户活跃度的情况下,舆情信息在人人网上扩散范围最广,新浪微博次之,QQ空间扩散较慢。本文提出的改进方法能解决现有算法社团划分结果分辨率低的问题,且有效弥补了LFM算法在大规模社团发现时陷入无限的迭代过程而导致时间复杂度高的缺点,将其应用于经典数据集中也符合理论预期结果。本文的研究结果将有助于进一步理解和认识社交网络社团结构对舆情传播的影响,同时对于网络群体事件发现和舆情监控及引导等具有重要意义。     

面向多源社交网络的社团结构特征研究

为了研究社交网络社团结构对舆情传播的影响,本文对比分析了多源社交网络的社团结构特性及传播特性,并且利用COPRA算法和LFM算法进行了社交网络重叠社团研究,提出一种基于节点度过滤的LFM改进方法——NF-LFM算法。该算法先对好友关系网络中节点度小于某一阈值的节点进行过滤,再对剩下的好友关系网络进行社团划分。研究发现:1)人人网、QQ空间、新浪微博都具有明显的社团结构特性,其中,人人网和QQ空间的社团结构特性强于新浪微博;2)在不考虑社交网络用户活跃度的情况下,舆情信息在人人网上扩散范围最广,新浪微博次之,QQ空间扩散较慢。本文提出的改进方法能解决现有算法社团划分结果分辨率低的问题,且有效弥补了LFM算法在大规模社团发现时陷入无限迭代过程而导致时间复杂度高的缺点,将其应用于经典数据集中也符合理论预期结果。本文的研究结果将有助于进一步理解和认识社交网络社团结构对舆情传播的影响,同时对于网络群体事件发现和舆情监控及引导等具有重要意义。     

小世界效应加速生物地理学优化的社团识别算法

为提高基于优化方法的网络社团结构识别算法的有效性,设计一种利用小世界效应加速生物地理学优化过程的网络社团结构识别算法. 首先基于矩阵随机编码建立网络社团识别生物地理学优化框架,在栖息地中全局进化地搜索对应于最大化模块度的网络社团划分. 然后,给出基于小世界效应的生物地理学迁移策略,可以加速进化算法的信息交换过程. 最后,运用该算法在现实网络和人工合成网络上进行实验. 结果表明:引入小世界效应能够降低网络社团结构识别算法的收敛时间;在典型现实网络与人工合成网络上运行该算法能够获得较高的模块度值与标准化互信息值;信息交换的拓扑结构能够优化进化算法效率. 应用小世界效应加速生物地理学优化的网络社团识别算法具有较好的可行性与有效性.     

复杂网络中的社团结构算法综述

社团结构是复杂网络的一个极其重要的特性,网络社团结构挖掘在生物学、计算机科学和社会学等多个领域都具有很重要的意义。近年来,针对不同类型的大规模复杂网络,人们提出了很多寻找社团结构的算法。该文综述了该领域最新的比较有代表性的一些算法,重点分析了基于模块度指标的改进算法,能够体现社团层次性和重叠性的新算法,衡量社团划分算法好坏的基准图。最后展望了该领域的未来研究方向。     

基于弱派系的多层社会网络重叠社团发现算法

针对现有社团发现算法中多层社会网络的重叠社团发现算法较少,且较难检测小型多层网络中社团的问题,提出一种基于弱派系的多层社会网络重叠社团发现算法.算法通过检测与合并网络中的弱派系得到社团发现结果,弱派系的构建综合考虑了节点度和节点邻居间的连接,得到更细粒度的社团结构,并同时适用于无向与有向网络.真实网络的实验结果表明,该算法可有效检测小型多层社会网络中的重叠社团,优于现有的基于局部社团的社团发现算法(local community based community detection algorithm,LC-CDA算法).     

动态网络桥系数增量聚类算法

提出了一种在动态网络中发现社团结构的增量式聚类算法.基于动态网络中相邻采样时刻网络拓扑变化较小的特点,将网络前一时刻的社团结构作为当前时刻的初始聚类结果,利用边的桥系数判断网络拓扑变化对聚类结果的影响,局部调整初始聚类,最终得到符合当前网络拓扑的社团结构.通过和马尔可夫聚类算法进行比较,验证了本算法的精确性和高效性.实验结果表明,利用增量聚类算法分析动态网络,避免了对当前网络的重新聚类,可以快速、准确地发现动态网络社团结构.     

一种基于四元加权消减的复杂网络社团划分算法

延续广泛应用的社团结构分级聚类方法,提出了衡量网络社团结构的社团稠密度概念,从而反映了网络结构整体性质的重要特征,并将参数应用于对网络社团聚类的研究当中．特别是基于社团稠密的四元结构提出了基于四元加权消减的社团划分算法．通过复杂网络实例验证了该算法的有效性,并对实验结果进行了比较分析,得出该算法在准确性方面对加权网络有较好效果．     

改进的谱二分法在重叠社团发现中的应用

社团发现算法在学术界得到了广泛的关注和研究,但是利用网络的边属性进行重叠社团发现的研究还比较新颖.通过将谱分析应用到边图上来发现重叠社团,谱二分法被改进为能够发现重叠节点的新算法.实验中改进的谱二分法与经典的边社团检测LC算法、分裂型的社区结构发现GN算法和派系过滤CPM算法在3个评价准则上进行对比,在3个真实网络上的实验结果表明本文提出的改进谱二分法效果更好,该算法不但实现了准确的社团划分,而且找到了社团之间的重叠节点.因此,可以认为基于拉普拉斯矩阵的谱二分法在以网络的边为研究对象时仍然适用,并且在边图上谱二分法实现了重叠社团发现的目的.     

社团结构生长网络模型研究

在有社团结构的网络中,为了研究社团之间的连接方式及社团内部个体之间的连接方式对整个网络结构的影响,建立了一个带有社团结构的网络模型.在社团内部仍采取度优先选择机制,在社团之间采取了社团平均度优先选择的方式.基于这样的选择方式生成了一个新的网络,获得了网络节点的度分布与联合度分布,并且发现该网络仍是一个无标度网络.最后利用数值模拟很好地验证了理论计算结果.     

模块密度谱分的网络社团发现方法

为有效地检测复杂网络中的社团结构,对评估与发现社团的模块密度函数(即D值)进行了优化．通过模块密度函数的优化进程,论证了模块密度函数被优化框定到广阔的谱分聚类方法中的矩阵松散最大化,并且提出了一种新的谱分算法．该算法允许自动选择最优的社团结构数目．在经典的计算机产生的随机网络及真实世界网络中检验了该算法．特别地,当网络中社团结构变得模糊时,实验结果显示这种新的算法在发现复杂网络社团上比基于模块密度的直接核方法及基于模块函数(Q)的谱分方法更加有效．     

基于种子节点集的社区层次结构发现算法

针对多分辨率方法无法直接给定社区层次结构的问题,提出一种基于种子节点集的社区层次结构发现算法。该算法通过选取种子节点,并根据余弦相似度的大小添加其最近邻节点共同构成种子节点集;再由种子节点集出发,基于分辨率公式进行社区层次结构探测,根据节点加入社区的度值比来判断是否到达层次边界;最后在已发现完毕的社区外选取新的种子节点集,并由此出发直到全网络的社区层次结构发现完毕。将该算法分别应用于人工网络和真实社会网络,实验表明,相较于其它算法,该算法能够更好地发现网络中全部的社区层次结构。     

稀疏网络的一个最短路算法及其实现

最短路算法在交通,通信等领域有非常重要的应用,许多网络问题都可以归结为一个最短路问题．Dijkstra最短路算法是一个非常有效的算法,在计算网络中某一个顶点到其他各顶点的最短路时,如果引入Fibonacci堆,则Dijkstra算法运行所需要的加法及比较次数大致为O（m＋nlogn）,其中,m,n分别为网络的边数和顶点数．但由于在算法执行过程中,对Fibonacci堆的操作也有一定的代价。本文根据大型稀疏网络的特点,对Dijkstra最短路算法提出了一些非常简单的,但是非常有用的改进,并由此得到一个针对大型稀疏网络的Dijkstra最短路算法,该算法不需要构造Fibonacci堆,并且算法在运行时也只需要加法与比较,其所需要加法和比较的次数为O（m＋nlog（n!））,其中D为网络中与顶点相关联边数的最大值．对于大型稀疏网络,如公路交通网络,D通常比较小,因此,所给算法对这类网络是非常有效的．     

密度峰值聚类的自适应社区发现算法

为减少社区发现算法中参数的选择对社区划分的影响,同时使算法能够自适应地进行社区划分,本文提出一种基于核密度估计的密度峰值聚类的社区发现算法KDED.首先,定义一种基于信任度的距离度量,将社交网络中的用户关系量化为距离矩阵,使用矩阵元素的大小度量用户关系的紧密程度;然后对距离矩阵进行核密度估计,统计各个节点在网络中的影响大小,结合热扩散模型改进计算流程,使其自适应不同规模的数据集以提高计算精度;结合密度峰值聚类原理和社区属性确定社区中心节点后,可根据节点间的距离得到社区内部层次结构和社区外部的自然结构;最后将剩余节点按距离分配到相应的社区当中以完成社区划分.仿真结果表明:通过可视化软件可观察到,通过KDED算法得到的社区划分结果具有清晰的自然结构和内部层次结构;随着社区规模的提升以及划分难度增加,KDED算法具有出色的稳定性;在真实数据集以及LFR基准网络上均得到较为接近真实划分结果的社区划分,自适应性良好,验证算法的可行性与有效性.     

密集传感器网络中节点随机调度算法研究

对于密集型传感器网络,节点交替工作能有效地延长网络的生命周期。该文基于Cover的随机节点调度算法进行深入分析,首先给出k-覆盖网络中覆盖强度的定义,并利用基本概率理论估计k-覆盖网络的覆盖强度;然后分析2-覆盖网络中节点密度、覆盖强度以及能量节省水平之间的关系(即部署节点个数n和2-覆盖网络的覆盖强度Cn2以及划分COVER个数c)。该文研究工作对部署容错性较高的能量有效性传感器网络具有一定的指导意义。     

基于矩阵运算的Ad hoc网络容量快速估计算法

采用定向天线的传输模式下,当信道带宽和端到端时延同时受到限制时,讨论了ad hoc网络容量的估计问题,提出了1种基于矩阵运算的网络容量快速估计算法,MCMFCA（写出全称）该算法与BFSA比较,前者的时间复杂度为0（N2/K）,后者的为0{[N/（K+1）]K},MCMFCA算法更能够跟踪网络拓扑的变化。     

基于传播影响力的重叠社区划分算法

在研究经典标签传播算法的基础上,提出了一种基于传播影响力的重叠社区划分算法COPRA-PI,可用于挖掘加权网络中的社区结构。该算法在COPRA算法的基础上从节点影响力、边影响力、历史标签影响力3个方面综合考虑传播影响力;同时针对COPRA算法中每个节点在每次迭代过程中均具有相同的最大标签数,且该最大标签数目需手动设置等不足,该算法中设计了一个自适应的最大标签数。实验结果表明,COPRA-PI算法在经典的数据集上对比现有经典算法更能挖掘出高质量的社区结构且收敛速度较快。     

全光网中定位故障链路的探测选择算法

文中研究了全光网中定位故障链路的探测选择算法．目前存在的随机游走算法可以惟一定位出每条故障链路,但在大型网络中定位故障链路时会消耗过多的探测以及平均波长数．首先建立关于故障检测需要的监测路径集合,其次在建立好的监测路径上同时发送探测信号,最后在有故障的路径上执行故障定位;证明了最小监测路径集合问题是非确定多项式完全问题,并提出启发式的监测路径选择算法来找最小监测路径集合; 同时证明了用一个监测站来定位k条故障链路的充分必要条件是,网络为k+1边连通的．对比随机游走算法,探测选择算法在定位故障链路的过程中明显地减少了定位故障链路所需的探测数和每条链路上消耗的平均波长数．