基于节点相似度的社团发现算法

对现有的社会网络社团发现算法进行研究,发现存在算法时间复杂度高、准确率低和没有充分利用节点属性信息等问题,提出了一种基于节点相似度的社团发现算法以解决这些问题。综合考虑图的拓扑结构和节点属性信息,结合构造属性扩展图的思想和基于结构情境相似度的思想得到节点的相似度,利用改进的K-means算法对所有节点进行聚类得到社团结构。编程实验结果表明,使用该算法得到的社团准确率较高,算法的时间复杂度为线性的,在带属性的数据集上和不带属性的数据集上的测试结果均验证了算法的有效性。     

基于核心节点扩散的有向网络重叠社团发现算法

复杂网络中的社团结构探测是当前复杂网络研究领域的一个热点问题。传统的社团划分算法主要以无向、无权网络作为分析对象,不能够适用于现实世界中各种有向网络、加权网络。在分析和研究各种社团划分算法的基础上,提出一种新的重叠社团发现算法。该算法从网络中的核心节点开始,不断合并适应度最大邻居节点,最终将网络划分为多个重叠的社团。最后,将该算法应用到两个有向网络中,实验表明该算法能够很好地划分出有向网络中的重叠社团。     

基于节点内聚系数的局部社团发现算法

为了能够快速有效地发现复杂网络中的局部社团,提出一种基于节点内聚系数的局部社团发现算法。该算法选取最大度节点作为起始社团,不断搜索其邻居节点,将满足条件的节点不断加入起始社团从而形成新的社团。在不同规模的真实网络数据集和人工合成数据集上进行实验,并与其他三种局部社团发现算法进行社团划分效果的对比。实验结果表明,该算法能够在较短的运行时间内保持较高模块度来识别复杂网络中的局部社团结构,更适合于大规模复杂网络的社团结构挖掘。     

基于覆盖最优划分的社团发现算法

覆盖最优划分思想是将子集间重叠区域样本通过覆盖的合并和分割,使原来有交集的覆盖划分为无交集的类误差最小.文中将覆盖的最优划分思想引入社团发现中,提出基于覆盖最优划分的社团发现算法(CDA_OPC),将社团发现问题转化为求给定覆盖的最优划分问题.首先利用节点间邻域重叠关系构造覆盖,然后运用覆盖的最优划分概念,通过覆盖子集的合并与分割达到对覆盖的最优逼近,最后计算社团间的相似度,将相似度最大的社团两两合并,在多层次合并后最终形成多粒度的社团结构.在真实网络上的实验表明,CDA_OPC可以有效划分社团.     

基于相似度的三元社团合并算法*

针对使用相似度测量进行社团划分时可能出现的判断冲突问题,提出了一种基于相似度的三元社团合并算法。首先通过对相似度阈值的选取,筛选网络中不同的三元社团,并将其作为社团合并的基本元素,通过社团相似度将其合并。然后将剩余节点和孤立三元社团分别按照节点从属度和三元社团从属度划分到相应社团。最后通过在人工合成网络和真实世界网络上进行实验测试,结果表明用本文算法可以准确高效的将网络中的节点划分到相应的社团。     

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

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

基于结构相似度仿射传播的社团检测算法

复杂网络中普遍存在着一定的社团结构,社团检测具有重要的理论意义和实际价值。为了提高复杂网络中社团检测的性能,提出了一种基于结构相似度仿射传播的社团检测算法。首先,选取结构相似度作为节点之间的相似性度量,并采用了一种优化的方法来计算复杂网络的相似度矩阵;其次,将计算得到的相似度矩阵作为输入,采用快速仿射传播(FAP)算法进行聚类;最后,得到最终的社团结构。实验结果表明,所提算法在LFR(Lancichinetti-Fortunato-Radicchi)模拟网络上的社团检测平均标准化互信息(NMI)值为65.1%,要高于标签传播算法(LPA)的45.3%以及CNM(Clauset-Newman-Moore)算法的49.8%;在真实网络上的社团检测平均模块度值为53.1%,要高于LPA算法的39.9%以及CNM算法的47.8%,具有更好的社团检测能力,能够发现更高质量的社团结构。     

一种新的基于粒计算的社团发现算法

提出了一种基于粒计算的社团挖掘模型,该模型改进了节点相似度的计算,通过不同粒空间分解问题,设计了相应的算法,从而实现了社团发现.     

基于多层节点相似度的社区发现方法

社区发现是复杂网络研究中的一项重要研究内容,基于节点相似度的凝聚方法是一种典型的社区发现方法。针对现有节点相似度计算方法中存在的不足,提出一种基于多层节点的节点相似度计算方法,该方法既可以有效地计算节点之间的相似度,又可以解决节点相似度相同时的节点合并选择问题。进一步基于这种改进的节点相似度计算方法和团体之间的连接紧密度度量准则构建社区发现模型,并在真实世界的网络上进行社区发现实验。与GN算法、Fast Newman算法和改进的标签传播算法的实验结果相比,该模型可以更加准确地找到各个社区的成员。     

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

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

基于自适应Memetic算法的多目标复杂网络社区检测

针对提高复杂网络社区检测准确度问题, 提出了一种自适应Memetic算法的多目标社区检测算法。在全局搜索中利用Logistic函数来设置与全局优化相应的交叉概率和变异概率,并将多目标优化问题转化成同时最小优化Kernel K-Means和Ratio Cut这两个目标函数;在局部搜索中利用权重将两个目标函数合并成一个局部优化目标,并采用爬山搜索来寻找个体最优。在虚拟和真实网络实验平台下,与五个基于遗传算法的方法以及Fast Modularity算法相比,结果表明算法能有效提高社区检测准确度,具有更好的寻优效果。     

基于节点属性的社区发现博弈算法

提出一种基于节点属性的社区发现博弈算法G_NA（game algorithm based on node attributes for community detection）。将社区发现的过程看做网络中节点的博弈,当所有节点都不能提高自身收益时,博弈结束。首先,G_NA提出基于节点度属性的收益函数;然后,在迭代过程中,节点按照重要度从大到小排序,并依次选择策略提高收益;最后,将提出的算法与现有算法分别在不同的真实网络和人工网络上进行对比实验,结果表明提出的算法优于其他算法。     

基于图遍历的局部社区发现算法

针对当前局部社区发现算法扩张速度慢不适用于大规模网络的问题,提出了一种基于图遍历的局部社区发现算法。该算法首先找出网络中度数最低的节点,以该节点为起点通过影响力函数将网络中的节点分为社区节点和边界节点,形成初步的社区划分,然后通过适应度函数确定边界节点的社区得到最终划分结果。实验结果表明,该算法在真实网络上进行测试时不仅能够有效地挖掘网络中的社区结构而且具有较快的速度。     

改进的基于局部模块度的社团划分算法

针对大多复杂网络社团划分算法不能快速发现最优节点加入社团的问题,提出一种利用节点亲密度的局部社团划分算法。引入节点亲密度的概念量化社团与邻居节点的关系,按照节点亲密度由大到小选择节点加入社团,最后以局部模块度为指标终止局部社团扩展。在真实网络和人工仿真网络进行实验,并与基于信息压缩的随机游走算法等4种典型社团划分算法相比较,所提算法划分结果的综合评价指标(F1score)和标准化互信息(NMI)均好于比较算法。实验研究表明,所提算法具有较好的时间效率和准确度,适用于大规模网络社团划分。     

复杂网络局部社区挖掘的节点接近度算法

为了准确、快速地发现大规模复杂网络中的局部社区,提出了一种基于节点接近度的局部社区发现算法。该算法以最大度节点作为起始节点,利用节点接近度和局部社区Q值不断搜索其邻居节点,将接近度最大的节点加入初始社区形成新的初始社区;同时,该算法也可以应用于复杂网络全局社区结构的划分。对2个典型复杂网络进行了局部社区挖掘分析,实验结果表明,该算法能够有效识别隐藏在实验网络中的局部社区。针对稀疏网络,该算法的时间复杂度为O（nlog（n））,n为网络节点数。     

基于Monte-Carlo迭代求解策略的局部社区发现算法

针对现有的局部社区发现算法因采用贪心策略进行社区扩张而导致的过早收敛和查全率低的问题,提出一种基于Monte-Carlo迭代求解策略的局部社区发现算法。首先,在每轮迭代的社区扩张阶段,根据节点对社区紧密度增益的贡献比例为所有邻接候选节点赋予选择概率,并结合此概率,再随机选择一个节点加入社区。然后,为避免随机选择导致扩张方向偏离目标社区,根据社区质量变化情况判断本轮迭代中是否触发节点淘汰机制。若触发,计算各个已加入社区节点与社区内其他节点的相似度和,根据相似度和的倒数赋予淘汰概率,并结合此概率,再随机淘汰一个节点。最后,在给定数量的最近迭代轮次中,根据社区规模是否增加判断是否继续迭代。在三个真实的网络数据集上进行实验,相较于局部紧密度扩展（LTE）算法、Clauset算法、加权共同邻居节点（CNWNN）算法和模糊相似关系（FSR）算法,所提算法的局部社区发现结果的F-score值分别提升了32.75、17.31、20.66和25.51个百分点,且能够有效避免查询节点在社区中所处位置对局部社区发现结果的影响。     

一种融合节点与链接属性的社交网络社区划分算法

针对传统社交网络社区划分算法普遍缺乏对节点属性、链接属性的综合考虑和充分表达利用节点与链接属性信息的模型和机制等问题, 提出了一种融合节点与链接属性的社交网络社区划分算法。该算法融合节点属性的相似度、节点间链接权值等链接属性信息, 定义了相似权值, 并以此为基础, 结合凝聚算法实现了对社交网络的社区划分。实验表明, 该算法对社交网络中属性比较明显的社区划分效果显著。     

Detecting community structure in complex networks using genetic algorithm based on object migrating automata

Community structure is an important topological feature of complex networks. Detecting community structure is a highly challenging problem in analyzing complex networks and has great importance in understanding the function and organization of networks. Up until now, numerous algorithms have been proposed for detecting community structure in complex networks. A wide range of these algorithms use the maximization of a quality function called modularity. In this article, three different algorithms, namely, MEM-net, OMA-net, and GAOMA-net, have been proposed for detecting community structure in complex networks. In GAOMA-net algorithm, which is the main proposed algorithm of this article, the combination of genetic algorithm (GA) and object migrating automata (OMA) has been used. In GAOMA-net algorithm, the MEM-net algorithm has been used as a heuristic to generate a portion of the initial population. The experiments on both real-world and synthetic benchmark networks indicate that GAOMA-net algorithm is efficient for detecting community structure in complex networks.     

复杂网络重叠社团检测算法研究综述

社团结构是复杂网络的一项基本特性,对复杂网络中社团结构特别是重叠社团结构的检测,是复杂网络理论研究的一项重要且充满挑战的课题.对当前常用的重叠社团检测算法进行了分析和归纳,阐述每类算法特点,并介绍用于评价算法性能的一些基准图,对复杂网络重叠社团检测领域未来的研究方向提出了一些思考和建议.     

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

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