关键词： 社团检测   节点引力   种子扩展算法   标签传播算法   个性化推荐  

摘要： 复杂网络是由节点和节点之间的复杂关系构成的网络结构,是对现实世界中的各种复杂系统的抽象,社团结构是复杂网络的显著特性。社团检测算法可以揭示网络的拓扑结构,挖掘复杂网络中的潜在信息,可广泛应用于个性化推荐、公共安全、社会科学等领域,具有重要的研究意义。本文针对常见的种子扩展算法和标签传播算法中存在的问题,提出了两种改进算法。本文的主要研究内容和成果如下:(1)针对种子扩展算法种子节点挑选欠佳和社团扩展方法不当等问题,本文提出一种基于CRITIC法和节点引力的种子扩展算法(Seed Expansion Algorithm based on CRITIC and Node Gravitation,SECNG)。该算法首先使用CRITIC法对节点的介数中心性、接近中心性、度中心性客观赋权,定义了节点综合重要性(Node Comprehensive Importance,NCI),并按照该重要性指标的递减顺序来挑选种子节点。然后提出了基于节点综合重要性的节点引力和社团引力的概念,在社团扩张阶段,按照NCI的递减顺序,将未划分社团的节点扩展至对它社团引力最大的社团。最后本文提出了基于模块度增量的社团优化方法,每次迭代时将模块度增量最大的两个社团合并,进一步提升了算法的准确度。(2)针对标签传播算法的高随机性问题,本文提出了基于节点影响力和节点引力的标签传播算法(Label Propagation Algorithm based on Node Influence and Node Gravitation,LPANING)。该算法首先基于Page Rank和度中心性定义了节点影响力(Node Influence,NI)这一指标,并按照该指标的递减顺序对节点进行排序从而确定标签初始化及标签更新的顺序。然后定义了基于节点影响力的节点引力(Node Gravitation based on Node Influence,NGNI),当节点具有多个候选标签时,选择与该节点引力最大的节点的标签。最后算法根据社团相似度将小规模社团进行合并,从而提高了算法的稳定性和准确性。相关实验表明,论文提出的SECNG算法和LPANING算法在多组人工网络和真实网络上均有良好的表现。(3)论文将上述两个算法应用于某省的科技计划项目中。根据阅读行为构建融媒体内容阅读数据中的用户复杂网络,结合社团检测算法对用户进行个性化推荐,在注重用户喜好的基础上促进主流价值观的传播。

关键词： 社团检测   网络嵌入   深度学习   重叠社团   图卷积网络  

摘要： 随着大数据技术的愈发成熟,网络数据集复杂程度不断提高,复杂网络方向的研究受到了学者们的更多关注。社团检测是复杂网络中的重要研究方向,其目的是在复杂网络中找到连接更加紧密的节点集合。而随着深度学习技术在复杂网络方面研究的普及,越来越多的复杂网络传统问题可以获得新的解决方案。其中,网络嵌入由于其可以将图数据映射到低维向量上这一特点从而避免了直接处理复杂的非线性结构的网络数据,因此可以很好地适应对复杂数据集的后续处理以及复杂网络上的相关研究。然而,现有的基于网络嵌入的社团检测算法还存在以下问题:(1)部分网络嵌入算法训练得到的节点嵌入向量在训练过程中没有考虑社团信息,因此得到的节点嵌入在聚类之后得到的社团划分结果不是很好。(2)大部分算法无法很好的将网络结构信息映射到网络嵌入向量这个过程与社团检测联系起来进行考虑,从而在应对一些网络连接结构复杂、社团结构不明显的数据集时,社团划分结果较差。(3)目前的网络嵌入算法对于重叠社团检测的考虑不够充分。为了更好的应对这些问题,论文提出了基于多聚类损失函数的网络嵌入方法(GEMMC)以及基于改进GCN的深度网络嵌入方法(DGEMOC)分别来处理非重叠社团检测以及重叠社团检测任务。论文的主要工作如下: (1)现有的部分嵌入方法在应对社团检测任务的时候通常只使用单一聚类损失函数来指导训练。在实际的任务中,往往会出现在部分的网络数据集中由于聚类损失本身的缺陷从而造成社团划分结果较差的情况。本文提出的GEMMC方法在训练过程中,同时添加聚类距离损失函数以及高斯混合模型的损失函数来指导嵌入向量的训练,并最终得到节点嵌入向量以及聚类嵌入向量,通过聚类方法可以得到社团划分。另外为了解决社团结构不明显时社团划分结果较差的问题,还对算法的节点采样方式进行了改进,在采样节点的过程中以一定概率可以直接得到与当前节点相似度最高的邻居节点。通过这种方法可以有效提高社团划分的质量。 (2)传统的图嵌入方法由于自身的局限性在处理重叠社团检测任务时的表现很难令人满意。本文提出了一种基于图卷积神经网络的图嵌入方法DGEMOC以更好的完成重叠社团检测任务。在实验中,对传统的GCN编码器进行了改进,加入了图扩散卷积,残差连接和基于相似度的卷积矩阵来优化模型并通过编码器得到隶属度矩阵,伯努利-泊松解码器根据损失函数不断对编码器生成隶属度矩阵的过程进行优化,最终选取合适的阈值在最终生成的隶属度矩阵上获得重叠社团划分结果。 (3)为了验证文中所提算法的性能,论文采用归一化互信息(NMI)和模块度作为评估社团检测的指标分别在LFR人工网络和多个现实图中与同类型的相关算法进行比较来评估GEMMC的性能,除此之外采用重叠归一化互信息(ONMI)和Omega指标作为评估重叠社团检测的指标在LFR人工网络和现实数据集中与相关算法进行比较以评估DGEMOC的性能。实验结果表明,GEMMC和DGEMOC在社团检测表现中发挥良好,在多数情况下能明显优于同类相关算法。

关键词： 社团检测   局部扩展   高阶结构   关系强度   中心性度量  

摘要： 现实中的很多复杂系统可以被抽象为复杂网络。社团是复杂网络中重要的结构特征。社团内部的节点彼此连接紧密,而不同社团之间连接稀疏。研究复杂网络的社团结构特征对于探索和揭示复杂系统的功能特性具有重要意义。目前社团检测算法的研究已经取得了长足的进展,但同时也存在很多不足之处。其中,在基于种子的局部社团检测方法中,种子节点选取方式、社团扩展方式以及社团边界节点处理方式还需要进一步研究。本文使用邻居间结构特征来检测社团,主要的研究内容包括以下两个方面。针对网络中连接紧密且相似度高的邻居节点不能合理划分到相应社团的问题,本文提出了一个局部视角下基于高阶三角形的社团检测算法LEHT。该算法首先依据节点与其邻居节点之间的局部关系,为每个节点依次构建高阶三角形。若该节点与邻居节点构成多个高阶三角形时,使用本文定义的三角形相似度计算该节点构建的高阶三角形的稳定性,选择稳定性最大的三角形作为该节点的高阶三角形。迭代此过程,直到所有满足高阶三角形的节点都有唯一的高阶三角形,高阶三角形中的节点形成初始社团。接着,对于高阶三角形中的每个节点,若该节点满足所属的高阶三角形与邻居节点的高阶三角形之间有多个公共节点且连接紧密,就将两个高阶三角形合并。迭代此过程,直到将所有满足条件的高阶三角形都进行合并为止,初始社团的扩展完成。最后,对于不能构建成高阶三角形的节点,计算该节点在社团中的邻居节点的接近中心度,把该节点加入到邻居节点接近中心度最大的社团,形成最终社团。在真实网络和LFR基准网络上,将LEHT算法与五个经典算法的实验比较分析,结果表明算法LEHT的性能表现更好。针对局部社团检测算法对种子节点选择敏感和对社团扩展的不稳定问题,本文提出了一种基于高阶结构与关系强度的社团检测算法HTRS。该算法首先定义了一种高阶结构motif度,根据每个节点的motif度把节点划分为高阶节点和边缘节点,根据高阶节点的局部邻接密度自适应地确定社团的核心节点。通过核心节点与其连接紧密邻居节点构成的多个高阶结构motif,使用关系强度rs1选择其值最大的高阶结构motif作为初始社团。接着,在高阶扩展阶段,根据高阶节点与社团内节点连接的个数不同,继续细分为两种扩展方式。当社团内两个节点与社团外的一个高阶节点构成高阶结构motif时,通过收益函数将此高阶节点扩展到社团中。对于社团内一个节点与社团外两个高阶节点构成高阶结构motif,通过关系强度rs2将此高阶节点扩展到社团中。迭代此过程,直到将所有的高阶节点加入到社团为止。最后,在低阶扩展阶段,该算法定义了一种关系强度rs3,它同时考虑了边缘节点连接到社团内节点数量与节点的影响力两个因素来确定该节点归属的社团。把边缘节点加入到关系强度rs3值较大的邻居节点所在的社团,形成最终的社团。在真实网络和LFR基准网络上的实验结果表明,HTRS算法能够以高精度和高稳定性地检测社团。综上所述,本文提出的LEHT与HTRS算法都使用了邻居节点间的高阶结构特征,通过局部扩展的方法来检测社团。LEHT算法解决了紧密相邻的节点不能合理划分社团的问题,HTRS算法解决种子节点选取导致社团扩展不稳定的问题。本文的算法检测到了质量高且鲁棒性强的社团。它们对于检测社团结构提供了一个可行的解决方案。

关键词： 社团检测   K阶图卷积   属性信息   稀疏性  

摘要： 挖掘属性网络中的社团结构有助于对网络节点进一步分析,具有重要的现实意义。图卷积神经网络能够有效地将属性网络的结构信息进行嵌入,获取节点的特征表示,从而可获得性能良好的社团结构。然而,现有图卷积方法大多使用固定的低阶图卷积,只考虑每个节点一阶或二阶内的邻居,没有充分利用节点关系,忽略了网络结构的多样性。另外原始网络结构的稀疏性无法克服,会降低社团检测的性能。为解决上述问题,提出一种融合属性信息与结构信息的K阶图卷积社团检测方法(KGCN),该方法可以有效地克服原始网络的稀疏性并利用节点的高阶结构进行社团检测。首先根据节点的属性信息对原始网络进行重构,缓解原始网络结构的稀疏性;其次考虑到高阶结构关联,采用K阶图卷积编码器对节点进行编码,获得节点的特征表示;最后使用谱聚类算法进行社团检测。实验结果表明,在四个真实数据集上,相比现有算法,KGCN方法取得更好的社团检测结果。

关键词： 社团检测   二分网络   动态距离   自我中心  

摘要： 为了在二分网络中能够更好地利用动态距离模型,提高动态距离模型的鲁棒性,提出一种新的局部非对称边缘聚类系数(local asymmetric edge clustering coefficient,LAECC),将自我中心(Ego-Leader)从单模网络扩展到二分网络,用来判断专属邻居节点对距离产生的影响,摆脱敏感参数.同时,提出一种在二分网络中基于Ego-Leader进行社团检测的增强动态距离模型(E-BiAttractor),E-BiAttractor不仅继承了BiAttractor在检测二分网络社团时的优异表现,而且通过引入Ego-Leader来代替敏感参数,优化了模型在二分网络上的鲁棒性,并提出相应的社团检测算法.最后在8个公开数据集上进行实验对比分析,验证了所提模型的有效性.大量实验表明,相较于几种已有的算法,E-BiAttractor具有良好的性能.

关键词： 社团检测   重叠社团结构   节点向量   密度峰值   标签传播   归属度  

摘要： 在真实世界网络中,数据量往往较大、维度较高,这使得数据难以处理,并且所包含的社团大多重叠,而大多数已经存在的算法针对的是非重叠社团,基于改进的密度峰值和标签传播的重叠社团检测算法(DPCL算法).采用低维向量表示网络中节点信息,根据节点的局部密度和相对距离选出中心节点.将只与一个中心节点直接相邻的节点分配到该中心节点所在的社团内,对剩余节点通过计算归属度进行分配,从而实现对重叠社团进行检测;在真实世界网络和LFR基准合成网络上与其他社团检测方法进行比较,实验结果表明能够有效的检测重叠社团.

关键词： 复杂网络   社团检测   标准体系  

摘要： 传统标准体系往往采用“自上而下”的思维方式,在新技术和产业融合快速发展的背景下,传统模式无法从容应对海量标准数据信息。本文基于工业机器人领域的标准引用网络,通过设计数学模型引入BGLL社团发现算法来探索标准集合重新划分,后借助Jieba分词和TF-IDF关键词提取算法,识别划分结果中的标准主题,以此来丰富工业机器人标准体系结构图,为工业机器人领域的标准化工作提供有益参考,为标准数字化转型提供技术支持。

关键词： 社团检测   k核   加权图   紧密子图   贪婪策略  

摘要： k核查询是一种社团查询,由于其可以在线性时间内被有效计算,因此在社团检测中具有较广泛的应用。图中边的权值在很多场景下具有较强的语义关系,但现有研究较少考虑图中边的权值。为提升k核查询的效率,在k核的基础上定义加权图中的紧密k核子图查询(CRKSQ)问题,并使用归约方法证明该问题是NP-难的。基于贪婪策略设计启发式算法CRK-G,通过迭代删除节点为CRKSQ问题找到一个近似解。在此基础上,从降低图规模和减少迭代次数两方面研究CRK-G算法的优化策略,分别提出使用图压缩策略的算法CRK-C及使用单次多节点删除策略的算法CRK-F。在Bio-GRID、Email-Enron、DBLP 3个数据集上的实验结果表明,相对于CRK-G算法,CRK-C、CRK-F算法在查询速度上有较大的提升,且平均误差均在8%以内。

关键词： 动态网络   社团发现   增量   网络突变   累积误差  

摘要： 当前主流的动态社团检测算法通常基于社团结构平稳变化的假设,不能很好地处理网络突变和累积误差,提出一种增量式动态社团检测模型。将前一时刻的社团结构作为初始聚类结果,利用链路变化找出增量相关社团,利用网络变化度和社团稳定度局部调整初始聚类,得到符合当前网络拓扑的社团结构。在真实网络和合成的动态网络中的实验结果表明,所提算法可以准确地发现动态网络社团结构,能有效解决网络突变和累积误差等问题。

关键词： 院校竞争网络   社团检测   复杂网络   平行志愿  

摘要： 平行志愿录取规则与优质生源的紧缺使得院校在高考招生时存在激烈的竞争关系。从网络科学视角正确理解院校竞争关系,能够合理地指导考生进行志愿填报。利用2019年山西省高考理科录取成绩,通过改进的Jaccard相似度计算方法,构建院校竞争网络的邻接矩阵。基于复杂网络度量方法,实证研究院校竞争网络得到:1)度分布存在一定的异质性,且具有较大的平均度;2)簇度负相关表明院校竞争网络存在层次结构;3)富人俱乐部连通性表明度数大于375的院校完全连通构成富人俱乐部;4)利用基于节点标签与网络结构的社团划分算法,通过基尼不纯度评估社团内院校的同质性,进一步利用Louvain算法识别社团内院校存在层次化差异结构。这些实证结果刻画了院校竞争关系,在此基础上归纳了一些指导考生进行合理、分梯度志愿填报的建议和策略。