边异质网络中的社区结构发现算法

为解决社区结构发现算法功能社区与拓扑社区不一致的问题,提出一种基于边类型相似性聚类(TESC)的社区结构发现算法。该算法以局部拓扑特征与异质信息为目标进行节点聚类,基于节点邻接边类型构造网络节点之间的相似矩阵,从而获取边异质信息。在该相似矩阵的基础上,通过传统层次聚类的思想将相似度大的节点进行合并,进而利用轮廓系数优化社区数量,得到最终社区划分结果。选取社区结构已知的4个真实网络和6个人工合成基准LFR网络,通过与同质网络的GN、Louvain算法以及异质网络的Hete-SPAEM、Hetero-Attractor算法对比,结果表明TESC算法获得的社区结构更接近于网络实际社区结构。     

异质网络社区发现研究进展*

异质网络将复杂系统中的信息抽象成不同类型的节点和链接关系,不同于同质网络,基于异质网络的社区发现能够挖掘出更加精确的社区结构。异质网络的社区发现通过对异质网络中的多维结构、多模信息、语义信息、链接关系等信息进行建模表示和提取分析,以发现其中相对紧密稳定的社区结构,对网络信息的获取与挖掘、信息推荐以及网络演化预测具有重要的研究价值。首先对社区发现当前研究的不足进行了简单阐述,接着引出了异质网络的定义;随后结合实例介绍了异质网络社区发现的现有研究方法,包括基于主题模型、基于排序和聚类相结合、基于数据重构和基于降维的方法等,并针对各类方法指出了其特点和局限性;最后讨论了当前该领域在结构复杂性、信息多样性、数据规模等方面面临的挑战。在将来,基于并行化、可扩展、动态增量的研究更能适应当前的变化环境。     

基于联合矩阵分解的动态异质网络社区发现方法

动态网络的社区发现是目前复杂网络分析领域的重要研究内容,然而现有动态网络社区发现方法主要针对同质网络,当网络包含多种异质信息时,现有方法不再适用。针对这个问题,本文提出了一个基于联合矩阵分解的动态异质网络社区发现方法,首先计算动态异质网路中各个快照图的拓扑相似度矩阵和多关系相似度矩阵,其次利用时序联合非负矩阵分解方法,约束各个时刻快照图的社区划分,最后在真实网络数据集上的实验结果表明,该算法可以有效检测出动态异质网络中潜在的社区结构。     

基于超图和K-means改进的异质网络社区发现算法

为解决异质信息网络社区发现问题,提出一种基于超图和K-means改进的算法.引入超图对异质网络进行建模,通过DeepWalk的深度随机游走产生节点序列,利用Skip-gram模型将网络节点序列映射到一个低维的向量空间,通过节点向量间距离进行聚类完成社区发现.针对传统K-means在初始聚类中心选择的敏感性问题,提出一种基于密度基尼系数的聚类中心选取方法.在两个真实数据集上进行了实验,实验结果表明,该算法不仅能够完成异质信息网络的社区划分,且社区识别精度高.     

融合属性信息的异质网络嵌入方法

现有的异质网络嵌入方法不仅忽略了网络中的异质边及其对节点嵌入的不同影响,还未考虑到网络结构与节点属性的融合。为此提出了一种融合属性信息的异质网络嵌入方法（SHANE）。将序列到序列（seq2seq）模型应用到依据边类型划分的子图中,无缝融合节点的结构信息和属性信息,同时捕捉节点的高阶语义信息。实验表明,SHANE在两个不同类型的数据集中进行链接预测任务,可以取得相对显著的效果。     

图正则化非负矩阵分解的异质网社区发现

挖掘数据网络中有价值的、具有稳定性的社区,对网络信息的获取、推荐及网络的演化预测具有重要的价值。针对现有异质网络聚类方法难以在同一维度有效整合网络中异质信息的问题,提出了一种基于图正则化非负矩阵分解的异质网络聚类方法。通过加入图正则项,将中心类型子空间和属性类型子空间的内部连接关系作为约束项,引入到非负矩阵分解模型中,从而找到高维数据在低维空间的紧致嵌入,成功消除了异质节点之间的部分噪声,同时,对反映不同子网络共有潜在结构的共识矩阵进行优化,有效整合异质信息,并且在降维过程中较大限度地保留了异质信息的完整性,提高了异质网络聚类方法的精度,在真实世界数据集上的实验结果也验证了该方法的有效性。     

一种面向语义重叠社区发现的 Block 场取样算法

语义社会网络(Semantic social network, SSN)是一种包含信息节点及社会关系构成的新型复杂网络. 传统语义社会网络分析算法在进行社区挖掘时, 需要预先设定社区个数且无法发现重叠社区. 针对这一问题, 提出一种面向语义重叠社区发现的block场采样算法, 该算法首先以LDA (Latent dirichlet allocation)模型为语义分析模型, 建立了以取样节点为核心节点的block 场BAT (Block-author-topic)模型; 其次, 根据节点的语义分析结果, 建立可度量block区域的语义凝聚力方法, 实现了语义信息的可度量化; 最后, 以节点的语义凝聚力为输入, 改进了重叠社区发现的标签传播算法(Label propagation algorithm, LPA)及可评价语义社区的SQ度量模型, 并通过实验分析, 验证了本文算法及SQ 度量模型的有效性及可行性.     

基于社区与结构熵的异质网络影响力最大化

影响力最大化的目的是在网络中发现能够触发最大数量的剩余节点参与到信息传播过程的一小群节点.目前异质信息网络中影响力最大化的研究通常从网络中抽取同质子图、或基于节点局部结构的元路径进行节点影响力的评估,没有考虑节点的全局特征和网络中高影响力节点间的集群现象给种子集合最终扩散范围造成的影响损失.文中提出了一种基于社区与结构熵的异质信息网络影响力最大化算法,该算法能够有效地从局部和全局两个方面度量节点的影响.首先,通过构建元结构保留节点在网络中的局部结构信息和异质信息度量节点的局部影响;其次,利用节点所属社区在整个网络中的权重占比对节点的全局影响进行度量;最后,综合求出节点的最终影响并选出种子集合.在真实数据集上进行的大量实验结果表明所提算法有较好的有效性和效率.     

基于随机游走的语义重叠社区发现算法

语义社会网络是由信息节点及社会关系构成的一类新型复杂网络,因此语义社会网络重叠社区发现是传统社区发现研究的新方向.针对这一问题,提出基于随机游走的语义社会网络重叠社区发现算法,该算法首先以LDA(latent Dirichlet allocation)算法为基础建立语义空间,实现节点语义信息到语义空间的量化映射;其次,以语义空间中节点信息熵作为节点语义信息比重,以节点的度分布比率作为节点关系比重,建立节点语义影响力模型及语义社会网络的加权邻接矩阵;再次,以语义影响力模型和加权邻接矩阵为参数,提出一种改进的语义社会网络重叠社区发现的随机游走策略,并提出可度量语义社区发现结果的语义模块度模型;最后,通过实验分析,验证了所提出的算法及语义模块度模型的有效性和可行性.     

基于超图卷积的异质网络半监督节点分类

近几年,图神经网络(Graph Neural Network)由于能够较好地提取网络结构信息以获得网络表示,逐渐成为网络节点分类的主流算法.然而,与广泛研究的同质信息网络相比,真实世界中网络往往是由不同类型的对象通过复杂关系相互连接所构成的异质信息网络.异质信息网络包含复杂的结构信息和丰富的语义信息,这也给网络节点分类提供了新的机遇与挑战.在异质信息网络中,网络模体(Motif)能够用于理解和探索复杂网络,其既能描述复杂的语义信息,又能保存网络中高阶近邻结构信息.因此,提出基于网络模体的异质超图卷积网络模型MHGCN(Motif-based HyperGraph Convolutional Network).首先,将重复出现的高阶网络模体建模为多个相关节点所构成的超边(hyperedge),进而将整个异质信息网络转换成由不同超边构成的超图,以克服同质网络中只能描述节点之间(pair-wise)关系的缺点;然后,利用超图的基本性质和谱理论设计超图上的卷积操作,同时引入超边自注意力机制聚合超图内部不同类型的节点,并通过在超图网络中加入自环解决在模型的前向传播过程中对异质信息网络覆盖不足的问题;最后,通过注意力机制对于不同语义的超图表示进行聚合,从而使最终的节点表示可以有效保持高阶近邻关系和复杂的语义信息.由于MHGCN是端到端的,最终模型直接学习得到节点的分类标签,并通过半监督节点分类任务进行验证,与其它方法相比,MHGCN在DBLP-P、DBLP-A数据集上比最好的基准方法micro-F1提高了0.56％～3.51％,macro-F1提高了0.54％～4.37％,验证了MHGCN模型的有效性.     

基于动态投影嵌入的多维异质网络可视化研究

异质网络是包含多种类型节点和边的复杂信息网络,因此异质网络的可视化通常涉及异质信息的有效处理与可视技术,传统的网络可视化技术对于异质网络可视化来说布局效果混乱、异质信息难以体现。为此提出一种基于动态投影嵌入的多维度异质网络可视化方法。该方法从异质网络的表示学习方法入手,提出动态投影嵌入模型来学习异质网络的节点表示,在此基础上,提出了多维度（空间）的可视化方法,将异质网络节点根据不同属性映射至不同关系空间中进行可视化分析,从而挖掘出潜在的语义信息。实验结果表明,提出的方法不仅使异质网络表示学习的评价指标（MRR）提升了10%,而且从多维度（空间）对异质网络进行可视化,有效地展示和挖掘了网络中的异质信息与潜在语义信息。     

基于图卷积的异质网络节点分类方法

图神经网络能够有效学习网络语义信息,在节点分类任务上取得了良好的效果.但仍面临挑战：如何充分利用异质网络丰富语义信息和全面结构信息使节点分类更精准.针对上述问题,提出了一种基于图卷积的异质网络节点分类框架(heterogeneous network node classification framework, HNNCF),包括异质网络约简和图卷积节点分类,解决异质网络节点分类问题.通过设计转换规则约简异质网络,将异质网络化简为语义化同质网络,利用节点间的关系表示保留异质网络多语义信息,降低网络结构建模复杂度;基于消息传递框架设计图卷积节点分类方法,在语义化同质网络上学习无1-sum约束的邻居权重等网络结构信息,深入挖掘关系语义特征,发现不同连接关系和邻居语义提取的差异性,生成节点的异质语义表示用于节点分类,识别节点类别标签.在3个公开的节点分类数据集上进行了实验,结果表明HNNCF能够充分利用异质网络多种语义信息,有效学习邻居节点权重等网络结构信息,提升节点分类效果.     

异质网络中基于关键词属性的Truss社区搜索

社区搜索旨在信息网络中寻找与用户指定的查询节点高度相关的稠密连通子图,是社会网络分析的重要研究内容。现有的社区搜索方法大多是针对同质网络,但现实中的信息网络通常是包含多种节点类型和多种关系类型的属性异质网络。提出了异质网络中基于元路径P和元结构S的P-距离和S-距离及(k,d,P)-truss和(k,d,S)-truss社区模型以度量子图的结构内聚性,同时提出了关键词属性得分函数用于度量不同子图的关键词属性相关性,最后提出了搜索具有最高关键词属性得分的(k,d,P)-truss和(k,d,S)-truss的社区搜索算法。搜索算法能够找到同时具有结构内聚性和关键词属性相关性的个性化社区,并且支持限制查询节点与社区内任意节点的最大距离d来控制社区搜索的范围。在真实数据集上与相关的社区搜索算法进行了实验对比,结果证明了所提算法的有效性和可行性。     

基于引力因子的加权网络重叠社区识别算法

通过挖掘大数据来识别复杂社会网络上的社区,有利于对经济、政治、人口等方面的重要问题进行定量研究,社区的识别算法已经成为当前研究的热点问题。重点研究了重叠社区识别问题,提出了基于引力因子的加权复杂网络的重叠社区识别算法GWCR。该算法首先选取万有引力因子大的节点为中心节点,将节点与中心节点之间的引力因子作为衡量标准,并将节点归入社区引力因子大于某一阈值的社区,最后通过识别重叠节点来识别重叠社区。在3个真实网络数据集上的实验结果表明,与传统的重叠社区识别算法相比,GWCR算法划分的社区的模块度较高。     

基于时间加权的重叠社区检测算法研究

随着网络结构的不断扩大和日益复杂, 重叠社区发现技术对挖掘复杂网络深层潜在结构具有重要意义. 本文提出一种基于时间加权的重叠社区检测算法. 该方法考虑了用户兴趣的时间因素, 构建带有时间加权链接的用户-用户图. 接着, 基于网络节点的影响力计算用户全局相似度, 在此基础上通过计算节点的中心度作为度量节点对社区结构影响力的重要性指标, 从而提出一种社区中心点的选取方法. 最后, 通过效用函数的迭代计算实现重叠社区检测. 利用人工网络和真实网络对提出的算法进行验证, 实验结果表明: 相对于传统的社区发现方法, 该算法在社区发现质量和计算效率方面都优于许多已有重叠社区发现算法.     

基于三角形的重叠社团发现算法

社区结构是复杂网络的重要属性之一, 有效挖掘出复杂网络中隐藏的社区结构具有重要的理论研究意义和广泛的应用前景。真实网络在一定程度上都表现为重叠的社区结构, 针对这一问题, 提出了一种基于三角形的重叠社区发现算法。通过判断两个节点与其共享邻居节点能否构成一个三角形来判断, 若能构成三角形, 则这两个节点属于同一社区。在计算机生成网络与真实网络上进行了实验, 都正确地识别出了社区结构以及重叠节点, 表明了此算法对于发现重叠社区结构的有效性和可行性。     

基于逻辑触发的异质网络体系能力分析

当前网络科学在对网络建模时只关注拓扑结构,而忽视了节点和连边自身的属性。针对该问题,提出通过异质网络中的异质元素(异质节点和异质连边)进行建模,将异质元素视为非线性系统,同时基于逻辑触发的思想构建异质网络的拓扑结构模型,模拟网络信息流程,并以此形成异质网络中存在的各种体系能力。实验结果表明,基于逻辑出发的异质网络模型,在进行网络分析时具有较好的可用性及可扩展性。     

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

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

基于子图结构的局部社区发现算法

局部社区发现算法通常选取种子节点进行社区发现,针对现有重叠社区发现算法中种子节点选取时有效性不足的问题,提出了一种基于子图结构的局部社区发现算法(Subgragh Structure Based Overlapping Community Detection,SUSBOCD).该算法提出了一种新的节点重要性度量指标,不仅考虑了节点的邻居数量,同时也考虑了邻居间的链接紧密程度.首先,选取未被访问且重要性最大的节点以及与其最为相似的邻居节点,将该两个节点及其公共邻居节点合并形成一个初始种子子图,该过程迭代运行直到所有节点均被访问;其次,根据种子子图的邻域信息进行相似度判断,若相似则进行合并,从而形成初始社区结构,持续扩展该过程直到所有种子子图均被访问;最后,对社区进行优化处理,若存在未分配社区的节点,则将其加入到最相似的初始社区,再合并重叠度较高的初始社区结构.在人工数据集和真实数据集上,对所提算法进行实验验证,实验结果表明,与其他重叠社区发现算法相比,SUSBOCD算法在ONMI,EQ和Omega这3个评价指标上均有所提升,即该算法能有效地提高重叠社区的划分质量.     

基于二部图表示的属性网络社区发现算法

属性网络社区发现是网络数据分析中的一项重要研究内容。为了提高社区发现的准确性，现有算法大多通过融合拓扑信息和属性信息对属性网络进行低维表示，然后基于低维特征进行社区发现。然而，这类算法通常基于深度模型进行表示学习，缺乏一定的可解释性。因此，文中提出了一种基于二部图表示的属性网络社区发现算法，以提高社区发现结果的准确性和可解释性。首先，分别基于属性网络的拓扑信息和属性信息计算网络中各个节点作为代表点的概率，通过两类信息融合选出一定比例的节点作为代表点；其次，基于拓扑结构和节点属性计算各个节点到代表点的距离，构建二部图；最后，基于二部图利用谱聚类算法进行社区发现，得到最终结果。在人造属性网络和真实属性网络上与已有的属性网络社区发现算法进行实验比较分析。实验结果表明，所提算法在标准化互信息、调整兰德指数等评价指标上均优于已有算法。