一种面向大规模社会网络的社区发现算法

随着社会网络中顶点和边的逐渐增加,计算效率成为了大规模社会网络中社区发现面临的一大难题.为了更加高效地探测社会网络中隐含的社区结构,提出一种基于抽样与标签传播的社区发现算法.该算法首先利用基于度的随机游走技术对整体网络进行抽样得到子图,然后采用基于概要的社区发现算法对此子图进行社区发现,得到核心社区,最后依据已有社区结构与未抽样的节点的相似度迭代式地将社区标签传播到剩余节点.在真实社会网络数据集上,与已有算法通过实验进行了比较分析,结果表明该算法能够在保证有效性的同时提高计算效率.     

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

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

一种新的基于社区结构的影响最大化方法

基于传播网络的结构性,提出一种新的基于社区结构的影响最大化方法AMICS.该方法先利用已有社区挖掘算法识别出隐藏在网络中的社区结构,然后迭代选择跨越社区数最多的k个节点作为影响的初始传播者最大化影响的社区覆盖.在小型网络和中等规模网络数据集上的实验表明,该算法比传统的影响最大化方法更具优势.     

一种基于广度优先搜索的社区发现方法

由于当前的算法不能很好地将网络的联通性和单个节点的属性综合考虑,分析了凝聚和分裂层次聚类经典算法的局限性,从而给出边的载荷、边的权重、连接度门限、图形分割等定义.综合考虑网络的拓扑结构和边的权重关系,提出了基于广度优先搜索的社会网络社区发现算法SoNetCD.算法通过删除社区之间的边而得到社区结构,它对社区之间的边判断准确,对社区内部的边误删率低.运用经典数据集进行实验的结果表明,该算法具有比经典GN算法更好的结果.     

基于粒子群优化与模糊聚类的社区发现算法

针对现有基于改进的K-means模糊聚类的社区发现算法(k-means algorithm for community structures detection based on fuzzy clustering,NKFCM)执行效率较差的问题,将粒子群算法与模糊聚类算法相结合提出了基于粒子群优化与模糊聚类的社区发现算法(community detection algorithm based on particle swarm optimization and fuzzy clustering,PFCM).该算法首先进行迭代运算,找出初始聚类核心,利用以云模型为运行条件的粒子群优化算法确定最优聚类核心与最佳社区个数,最后利用模糊聚类算法(fuzzy c-means algorithm,FCM)进行具体的社区划分.理论解析与测试结果表明:该算法发现网络社区的准确性较高,且与NKFCM算法相比,PFCM在处理网络数据时执行效率获得了极大地提升.     

用最小费用流的允许边算法求解指派问题

构造指派问题的最小费用最大流模型,并将基于对偶原理的允许边算法用于该模型,提出了求解指派问题的一种新算法。该算法按照互补松驰条件,通过修改已标号节点的势,在容量-费用网络中逐步扩大允许网络,并在其中增广流量,直至求得容量-费用网络的最小费用最大流,此最大流中的非0流边即对应于指派问题的最优指派。在迭代过程中,后续迭代充分利用了上一迭代的信息,有效节省了计算量。对于非标准指派问题,可以直接求解,而不需要先将其转化为标准形式。     

大规模网络广义社区发现随机变分推理算法

流行度-生成度随机块(popularity-productivity stochastic block,PPSB)模型能发现网络广义社区,但该模型易过拟合,且不能有效处理大规模网络,故提出一个3层贝叶斯网络广义社区发现(generalized PPSB,GPPSB)模型,并给出实现大规模链接网络和内容网络广义社区发现的随机变分推理(stochastic variational inference,SVI)算法GPPSB-SVI和GPPSB-C-SVI。不同规模人工网络和实际网络上的实验结果表明:GPPSB-SVI准确性优于已有流行大规模网络社区发现算法,效率高于基于PPSB模型的广义社区发现算法;GPPSB-C-SVI准确性优于GPPSB-SVI算法;GPPSB模型引入节点隶属度和类间链接概率矩阵的先验分布,可更好地对网络建模,其参数估计算法GPPSB-SVI、GPPSB-C-SVI可更有效地实现大规模网络广义社区发现。     

一种基于图压缩的重叠社区发现算法

为提高单机处理复杂网络规模的能力,提出一种新的重叠社区发现算法.首先,通过基于图压缩的社区结构表示模型(压缩社区图),对网络进行无损压缩;然后,在压缩社区图上基于种子迭代的思想,通过不断优化社区适应度函数将种子扩展成社区;最后,将相似度高的社区进行合并,得到最终的重叠社区结果.由于压缩后的凝聚图大大降低了待处理的网络规模,并能在一定程度上减少重复计算,该方法可以大大提高计算效率和单机处理的网络规模.     

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

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

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

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

基于重叠社区发现的社会网络推荐算法研究

协同过滤算法已成为用来为用户提供个性化服务以处理海量信息最常用的方法之一.本文提出一种基于重叠社区发现的社会网络推荐算法,该算法同时考虑了群组用户的兴趣以及他们复杂的内部关系,通过将重叠社区发现算法和基于模型的社会推荐算法进行创新融合,以实现重叠社区的发现、建立,和基于社区的智能推荐.基于开放数据集,本文设计了一系列相关实验以验证算法的有效性和准确性.实验结果表明本文提出的算法可以实现高效且准确的社会网络推荐.     

基于重要结点的社区发现算法

复杂网络中内部的社区结构是复杂网络结构特征和属性特征的具体体现。首先依据模块度最大化理论计算网络的模块度矩阵的最大k特征向量矩阵;然后提出聚类中心方法,并用于求出k个社团的重要结点作为k聚类中心,利用欧几里得距离计算每一个结点到k个聚类中心的距离,将结点分配到距离聚类中心最近的社区中;最后对网络应用k-means方法进行迭代计算,得到k个社区的划分。分别在Karate Club Network和American College Football数据集上对算法进行了实验验证,实验结果表明该算法可以有效发现潜在社区,其纯度与模块度比已有的社区发现算法都有一定的提高,并且迭代次数较少,效率较高。     

学习全局边函数的半监督社区检测

随着在线网络数据量激增,单纯分析网络拓扑结构、节点属性、边属性无法有效认识和理解其内在结构和特性,因此提出基于边函数的半监督社区检测算法。首先将拓扑结构和属性信息统一为先验知识,设计边函数便于引入属性等各类先验知识;在此基础上,结合传统半监督学习框架,采用半正定规划学习全局最优的节点归属矩阵。在人工合成数据、赣南客家数据和基准数据上的实验和分析表明,与已有传统半监督社区检测算法相比,该算法能有效利用各种先验知识,检测社区性能较好,并能较好地抵抗数据退化问题。     

异质网络社区发现方法研究综述

社区结构是复杂网络研究中的重要领域,也是复杂网络的重要特征之一,发现网络中的社区结构在理解网络功能方面起着重要作用。通过对国内外异质网络社区发现文献进行深入研究,较为全面地对现有异质网络社区发现算法进行了归纳总结。首先,通过对国内外异质网络社区发现文献进行归纳,给出异质网络社区发现的基本概述,明确异质网络社区发现领域相关问题的基本定义。其次,介绍了异质网络社区发现算法及主要评价指标,利用不同网络结构以及算法对现有方法进行分类概述。最后,对异质网络社区发现算法的发展趋势进行了总结与展望,提出未来可以将研究重点集中在以下几个方面:1)探索基于异质网络的社区发现评价标准,以推动该领域的快速发展;2)设计更加通用的算法模型,解决由先验知识引起的未知社区数量问题;3)开展更多关于动态网络的研究。     

基于选举标签传播的非重叠社区挖掘算法

针对邻居节点选择规则过于简单的传统标签传播算法容易导致奇异解问题,从而难以适应大型复杂网络的社区挖掘,提出了基于日常生活选举模式的标签传播算法VLPNO,重新定义节点标签传播规则,使其在传播迭代过程中能依照竞选的方式自主地更新标签,进而将网络划分为由领导者和跟随者组成的社区.实验结果表明,与LPA、SLPA与BMLPA相比较,VLPNO算法能够更快速有效地发现与真实网络社区更相吻合的社区结构.     

5G网络环境下云计算数据差分隐私保护算法研究

为了解决5G网络环境下云计算环境的复杂性和不确定性因素导致其差分隐私保护效果较差这一问题，该文研究了5G网络环境下云计算数据差分隐私保护算法。建立5G网络环境下云计算数据差分隐私保护架构，利用信息熵抑制方式，消冗处理5G网络环境下云计算数据。将5G网络环境内云计算数据看作一个社区，并对社区内的云计算数据添加拉普拉斯噪声。通过重构云计算数据社区内的边和社区之间的边，实现5G网络环境下云计算数据差分隐私保护。实验结果表明：该算法对云计算数据消冗处理后，数据结构复杂度最大降低1.2,对数据实施差分隐私保护后，信息泄露比明显降低，表明该研究方法具有较为显著的应用效果。     

基于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重叠社区发现算法都优于其他的算法。     

高度重叠社区的社区合并优化算法

当原图转换成边图后,在边图上进行社区发现可以天然地得到重叠社区,然而得到的社区往往相互大面积重叠,甚至相互包含,导致社区模块性质量较低.针对这一问题,在得到边图下重叠社区发现算法结果的基础上,我们将进一步以优化重叠社区模块化质量函数为标准进行社区合并,以获得高质量的重叠社区.本文首先提出一种描述社区间重叠程度的重叠系数,并基于此进一步提出一种构建带权社区图的启发式方法,能够快速有效地完成社区合并的过程.在人工生成网络与真实世界网络上的实验,进一步验证了该算法能够在不削弱边图方法速度优势的前提下,提高高度重叠社区的模块性.     

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

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

一种基于节点稳定性的社区发现算法

许多成功的社区发现算法已经被广泛应用于复杂网络社区发现任务中.随着数据复杂性的增加,网络中节点间的关系也呈现多样化的特点,因此提出一种基于信息熵的节点稳定性度量方法,衡量网络中节点在社区划分中的稳定性;并在此基础上提出一种基于节点稳定性的社区发现算法(Node Stability-based Algorithm,NSA).首先得到网络的t种社区划分,计算各节点的标签熵,选择熵小于一定阈值的节点作为网络的稳定节点集S;然后,利用所得到的稳定节点集S从原网络中抽取一个包含S的连通子图Gs,使Gs中节点的不稳定性尽可能低;在连通子图Gs上进行社区发现,得到初始聚类结果,再计算其他未聚类节点与初始类簇的距离,确定其社区归属,得到最终聚类结果 .在四个带标签真实网络数据集和八个不带标签的真实网络数据集上,与LPA,Infomap,Walktrap,BGLL,LPA-S等经典算法的比较实验表明,所提出的NSA算法能够较好地进行社区发现,在NMI和模块度等方面表现良好.