基于局部语义聚类的语义重叠社区发现算法

语义社会网络是一种包含信息节点及社会关系构成的新型复杂网络,因此以节点邻接关系为挖掘对象的传统社会网络社区发现算法无法有效处理语义社会网络重叠社区发现问题。针对这一问题,提出基于局部语义聚类的语义社会网络重叠社区发现算法,该算法：1）以 LDA （latent Dirichlet allocation）模型为语义信息模型,利用 Gibbs 取样法建立节点语义信息到语义空间的量化映射;2）以节点间语义坐标的相对熵作为节点语义相似度的度量,建立节点相似度矩阵;3）根据社会网络的局部小世界特性,提出语义社会网络的局部社区结构 S‐fitness 模型,并根据 S‐fitness 模型建立了局部语义聚类算法（local semantic clusterm ,LSC）;4）提出可度量语义社区发现结果的语义模块度模型,并通过实验分析,验证了算法及语义模块度模型的有效性及可行性。     

基于密度分布的社区发现算法研究

基于密度吸引点和其对相邻节点的影响度,提出了一种密度分布社区发现算法。该算法以节点度数最大的密度吸引点为初始社区,访问社区的相邻节点,把对社区影响度最大的节点加入到社区中,如果有些节点对多个社区都有影响,则把它归属为影响度最大的那个社区中,同时如果两个社区之间的相互影响度很大,可以将这两个社区合并为一个社区。将该算法应用到Zachary空手道俱乐部网络和随机无标度网络中,实验表明该算法能够很好地分出网络中的社区,同时实验还发现社区的收敛速度与幂率分布特性近似成反比。     

一种新的重叠社区发现算法*

基于节点的中心度和节点对社区的适应度,提出了一种新的重叠社区发现算法。该算法以中心度很大的节点作为初始社区,然后访问社区的邻居节点,把对社区适应度最大的节点加入到社区。如果节点对多个社区都具有很大的适应度,则这些节点归属于多个社区。考虑到社区之间的重叠性,将社区相似度很大的社区合并为一个社区。将该算法应用到Zachary空手道俱乐部网络和海豚社会网络中,实验表明该算法能够很好地划分出网络中的重叠社区。     

一种基于中心极大团扩展的社区挖掘算法

社区挖掘是复杂网络分析中的一项重要工作,目前已提出多种社区挖掘算法,但多数算法是通过节点间的连接关系来发现内聚的社区结构。结合真实网络中的节点具有不同的行为和影响力,在充分考虑网络中节点的连接关系的基础上,提出一种基于中心极大团扩展的社区挖掘两阶段算法。第一阶段发现初始社区:首先找到网络中所有的内聚子团,然后找出k个分散、内聚且有影响力的中心极大团作为初始社区;第二阶段形成最终社区划分:对初始社区外节点,充分考虑不同邻居节点对其潜在的影响力,采用局部模块度扩展的方法将节点扩展到与其连接紧密的社区内。实验结果表明,该方法能够快速揭示出网络中的社区结构,相比FN算法,具有较高的准确度和模块度,相比GN算法,不需要预先知道社区个数。     

融合标签预处理与节点影响力的重叠社区发现算法

针对节点初始标签散乱及标签传播随机性大的问题,提出一种融合标签预处理与节点影响力的重叠社区发现算法。首先,计算节点影响力,逐步选择影响力值最大的节点作为中心节点;然后,用中心节点的标签对同质的邻居节点进行标签预处理,减少了初始标签数量,降低了后续标签传播的随机性,并初步识别出了重叠节点;其次,通过标签隶属系数识别重叠节点,用节点影响力值选择非重叠节点标签,提高了算法的稳定性和准确性;最后,以最大化自适应函数增量为目标,对内聚度弱的社区进行合并,提高了社区质量。仿真实验结果表明：对于六个真实网络,所提算法在50%的数据集上具有最大的扩展模块度值;而在不同混合度、节点重叠度和节点最大归属社区数的人工基准网络上,该算法在标准化互信息（NMI）指标上都具有最好的性能。综上所述,该算法对各类网络都具有较好的适应性,且具有接近线性的时间复杂度。     

基于种子节点选择的重叠社区发现算法*

识别网络社区对于了解社会网络的结构和功能具有重要意义。由于网络中某些节点可能属于多个社区,因此重叠社区的研究已经吸引了人们越来越多的关注。本文针对目前从局部社区扩展成全局社区时有关算法的种子节点选择不合理的情形,提出了一种基于种子节点选择的重叠社区发现算法。本算法首先根据影响力函数找出局部影响力最大的节点,由这些节点构成的种子集合较好的分布在整个网络中,然后以这些种子点构造初始社区,根据设定的吸引度函数选择性添加节点来进行社区扩展。实验结果表明,该算法在真实网络上进行测试时能够有效的挖掘网络中的重叠社区。     

融合拓扑势的社交网络层次化社区发现算法

社交网络的社区结构呈现层次性。针对传统凝聚式层次化社区发现算法效率不高以及生成的层次谱图复杂的问题，提出一种融合拓扑势的层次化社区发现算法，利用拓扑势场呈现的自然峰谷结构揭示社交网络社区间的层次关系。该算法搜索局部极大势值节点，并根据局部极大势值节点完成社区的初始划分；根据局部极大势值节点间的距离对初始社区进行迭代合并，直到所有社区被合并为一个社区。在真实社交网络和人工网络上的实验结果表明，该算法能够高效地发现社区的层次结构，生成的层次谱图简单直观。     

融合标签预处理与节点影响力的重叠社区发现算法

针对节点初始标签散乱及标签传播随机性大的问题，提出一种融合标签预处理与节点影响力的重叠社区发现算法。首先，计算节点影响力，逐步选择影响力值最大的节点作为中心节点；然后，用中心节点的标签对同质的邻居节点进行标签预处理，减少了初始标签数量，降低了后续标签传播的随机性，并初步识别出了重叠节点；其次，通过标签隶属系数识别重叠节点，用节点影响力值选择非重叠节点标签，提高了算法的稳定性和准确性；最后，以最大化自适应函数增量为目标，对内聚度弱的社区进行合并，提高了社区质量。仿真实验结果表明：对于六个真实网络，所提算法在50%的数据集上具有最大的扩展模块度值；而在不同混合度、节点重叠度和节点最大归属社区数的人工基准网络上，该算法在标准化互信息（NMI）指标上都具有最好的性能。综上所述，该算法对各类网络都具有较好的适应性，且具有接近线性的时间复杂度。     

基于核心节点的网络社区发现方法研究

本文充分利用社会网络中存在普适幂律分布的特性,提出了基于核心节点的局部社区发现算法（EALCN）,利 用改进的PageRank 进行节点排序,然后利用网络中的局部信息对局部目标函数进行优化,从初始的种子节点不断优化后获得 目标函数,最终获取局部社区,仿真实验表明,该算法利用少量的局部信息便能够比较快速的找出社区结构,具有较高的执行 效率。     

基于共邻节点相似度的社区划分算法

复杂网络中的社区结构能帮助人们认识网络的基本结构及其功能。针对目前多数社区划分算法准确率低、复杂度高的问题，提出了一种基于共邻节点相似度的社区划分算法。首先，为了计算节点间相似度值，提出了相似度模型，该模型通过将被测节点对的邻居节点引入一并计算，提高了相似度度量的准确性；然后，计算节点局部影响力值，能客观地表现出节点在所处网络中的重要性；其次，结合节点相似度值和节点局部影响力值对节点进行层次聚类，完成网络社区结构的初步划分；最后，通过聚合初步划分的子社区，获得复杂网络的最优模块度值。仿真结果表明，在网络的社区特征模糊时，与新的基于局部相似度的社区发现算法（CDALS）相比，所提算法的准确率提高了14%，证明了所提提法更能够准确、有效地划分复杂网络的社区结构。     

基于最大节点接近度的局部社团结构探测算法

针对复杂网络社团结构挖掘算法复杂度高的问题,提出一种基于最大节点接近度的局部社团结构挖掘算法。该算法的时间复杂度为O（kd）。为验证该方法计算的准确性和计算的速度,与一种经典的挖掘局部社团结构方法——Clauset算法进行比较。实验结果表明,该算法抽取的社团结构与Clauset算法相比基本一致,但在性能上有明显提高。     

基于亲密度和吸引力的二分网络社区发现算法

社区划分是二分网络研究中的一个热门话题,针对现有的二分网络社区发现算法存在从不同节点出发社区划分准确率低的问题,提出了基于亲密度和吸引力的二分网络社区发现算法（Intimacy and Attraction Algorithm,IAA）。该算法将[U]类中的每一个节点看作一个社区,通过计算出每一个社区的亲密度和社区间的吸引力来合并社区,从而得到[U]类节点的划分,最后[V]类节点划分到已有的社区中得到完整的社区划分结果。在人工数据集和真实网络上进行分析,分别利用互信息和模块度作为评价指标,实验结果表明,IAA能够更有效挖掘二分网络社区结构,具有良好的社区划分效果。     

基于共享邻居数的社团结构发现算法

为了快速准确地找到复杂网络的社团结构,提出一种基于共享邻居数和局部模块度的社团结构发现算法。该方法通过不断寻找节点之间的共享邻居数找出与社团连接性最强的节点,并以局部模块度为衡量标准,判断是否将该节点加入到社团中。对3个典型复杂网络的划分结果表明,该算法是可行和有效的。     

基于弹簧模型的重要节点排序算法

重要节点排序是复杂网络研究的重要问题.用网络的鲁棒性和脆弱性指标评价基于引力模型的重要节点排序算法GM(gravity model)和其局部算法LGM(local gravity model)时,当度大的节点从网络中移除后,其引力较大的近邻节点的后续移除通常并不能在很大程度上影响网络的结构与功能,说明算法在重要节点排序...     

基于节点相似性和网络嵌入的复杂网络社区发现算法

社区发现算法对分析复杂网络的拓扑和层次结构、预测复杂网络的演化趋势等具有十分重要的意义.传统的社区发现算法划分精度不高,忽略了网络嵌入的重要性.针对这样的问题,提出了基于节点相似性和网络嵌入Node2Vec方法的无参数社区发现算法.首先,使用网络嵌入Node2Vec方法将网络节点映射成欧氏空间中低维向量表示的数据点,计...     

基于广义后缀树的二分网络社区挖掘算法

近年来,二分网络的社区挖掘问题得到了极大的关注。提出了一种基于广义后缀树的二分网络社区挖掘算法。首先从二分网络的邻接矩阵中提取网络中每个节点的链接节点序列,然后构建广义后缀树。广义后缀树的每个节点表示二分网络的一个完全二分团,由此获取并调整完全二分团。通过引入二分团的紧密度得到初始的社区划分,最后再对孤立点进行处理以得到最终的社区划分。所提算法不仅能发现重叠社区,而且能得到一对多关系的社区。在人工数据集和真实数据集上的实验表明,所提算法能准确地识别二分网络中的社区个数,获得很好的划分效果。     

重叠社区发现的两段策略

复杂网络中的社区特别是重叠社区在信息传播与推荐、舆情控制、商业营销等领域中具有重要作用。在实际的网络中,由于有些节点天然地属于多个功能团体,重叠社区的挖掘越来越受到重视。提出了一种重叠社区挖掘的两段策略算法:初始社区抽取与社区合并。在社区抽取阶段,选择网络中最大度节点及其紧密的邻居节点作为初始社区,将与此初始社区联系紧密的节点也一并加入;在社区合并阶段,如果两个社区合并之后使得模块度增加,则合并这两个社区。用包括大规模网络在内的3个实际网络对所提算法进行了测试,结果表明,该算法可有效挖掘网络中的重叠社区。     

基于共同好友数的在线社会网络社区发现算法

为了快速准确地找到在线社会网络的社区结构,提出了一种基于共同好友数和节点邻居信息的社区结构发现算法。该算法以共同好友数最多的两个节点为初始社区,不断寻找与社区连接性最强的节点,并以节点Q值为衡量标准,判断是否将该节点加入到初始社区中,最后根据节点邻居所在初始社区信息确定最终的社区划分。针对两个经典社会网络和人工生成网络数据的实验划分结果表明,该算法是可行和有效的。     

一种基于节点相异度的社团层次划分算法

当前层次划分社团算法难以选取合适的初始节点,导致社团结构划分结果较差。为此,提出一种基于节点相异度的层次社团划分算法。给出度和接近度的评估标准,根据评估标准筛选网络的初始核心节点。为克服相异性指数在度量社团内节点相似度时的不足,引入节点的相异度评价准则,计算初始核心节点间的相似度,得到具有较高相似度的初始节点集。采用全局优化模块度的策略,从而实现对复杂网络的社团划分。应用于标准数据集的实验结果表明,与GN算法、FN算法相比,该算法划分效果更好,时间复杂度更低。     

社交网络节点中心性测度

研究节点影响力以及扩大节点影响力的范围在社交网络传播中具有重大意义。为了综合分析节点自身影响力与其潜在影响力,提出了PPI（Personal-Potential Influence,PPI）算法,用介数中心性值,紧密中心性值及k-shell值加权来评估节点自身影响力,再通过节点间的相互影响来评估其潜在影响力。实验结果表明PPI算法在评估节点影响力上有较好的准确性。