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

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

图神经网络社区发现研究综述

社区结构是复杂网络中普遍存在的拓扑特性之一,发现社区结构是复杂网络分析的基本任务.社区发现旨在将网络划分为多个子结构,对于理解网络、揭示网络的潜在功能有着重要作用.图神经网络是一种处理图结构数据的模型,具有从图中对数据进行特征提取和表示的优势,已经成为人工智能和大数据领域的重要研究方向.网络数据就是典型的图结构数据,使用图神经网络模型解决社区发现问题,是社区发现研究的一个新方向.首先对GNN模型进行深入探讨,分析GNN社区发现过程,并从重叠社区和非重叠社区这两个方面详细讨论现有GNN社区发现取得的进展以及未来可研究的方向.     

节点不对称转移概率的网络社区发现算法

社区发现是当前社会网络研究领域的一个热点和难点,现有的研究方法包括：（1）优化以网络拓扑结构为基础的社区质量指标;（2）评估节点间的相似性并进行聚类;（3）根据特定网络设计相应的社区模型等.这些方法存在如下问题：（1）通用性不高,难以同时在无向网络和有向网络上发挥出好的效果;（2）无法充分利用网络的结构信息,在真实数据集上表现不佳.针对上述问题,提出一种基于节点不对称转移概率的网络社区发现算法CDATP.该算法通过分析网络拓扑结构来设计节点转移概率,并使用random walk方法评估节点对网络社区的重要性.最后,以重要性较高的节点作为核心构造网络社区.与现有的基于random walk的方法不同,CDATP为网络中节点设计的转移概率具有不对称性,并只通过节点局部转移来评估节点对社区的重要程度.通过大量仿真实验表明,CDATP在人工模拟数据集和真实数据集上均比其他最新算法有更好的表现.     

基于限制性随机游走局部谱近似社区发现算法

针对大型网络中社区发现优化方法的效率问题,提出一种局部社区发现方法(LRW-LSA),从少量种子节点中识别本地社区的所有潜在社区成员.采用限制性随机游走进行采样处理,从种子节点出发得到一个相对较小的子图;利用种子的归一化指示向量对子图进行Lanczos迭代,得到相关节点与目标社区的隶属概率用以恢复出目标社区.在不同领域的真实数据集和合成数据集上进行实验,结果表明,LRW-LSA优于现有的社区发现方法.     

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

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

基于图注意力网络和简单循环单元的化合物-蛋白质交互预测

现有基于深度学习的化合物-蛋白质交互预测方法未考虑数据的内部协变量偏移及序列数据的长距离依赖.针对此问题,文中提出基于图注意力网络和简单循环单元的化合物-蛋白质交互预测方法.利用图注意力网络-门控循环单元学习化合物分子的图级表示,利用多层简单循环单元学习氨基酸子序列的特征向量表示,结合多层前馈网络预测化合物-蛋白质的交互作用.实验表明,文中方法在2个公开数据集上的各项评估指标都有所提升,由此验证方法的有效性.     

针对有向图的局部扩展的重叠社区发现算法

当前社区发现算法主要是针对无向图研究社区结构,但在实际复杂网络中,链接关系时常表现出非对称性或方向性,比如Twitter的用户关注关系,文献网络的引 用关系,网页之间的超链接关系等应用网络。因此,本文依据信息在复杂网络中的传播规律和流动方向性,提出了k-Path共社区邻近相似性概念及计算方法,用于衡量结点在同一社区的相似性程度,并给出了把有向图转换为带方向权值的无向图的方法。基于带权无向图提出了一种从局部扩展来探测社区的重叠社区发现算法(Local and wave-like extension algorithm of detecting overlapping community, LWS-OCD)。在真实数据集上的实验表明,共社区邻近相似性概念实现了有向到无向的合理转换,而且提高了社区结点的聚集效果,LWS-OCD算法能够有效地发现带权无向图中的重叠社区。     

一种基于层级信息优化的有向网络表示学习方法

网络表示方法旨在将每个节点映射到低维向量空间,并保留节点在网络中的结构关系。有向网络的环中节点相互可达,破坏了非对称传递性,影响了模型对网络整体结构信息的学习。为削弱有向网络的环在表示学习中的影响,增强模型对全局结构信息的感知,文中提出了一种针对有向网络表示学习的优化方法。该方法借助TrueSkill方法获取节点的层级信息,将该信息转化为边权重并引入表示学习过程。文中将此方法应用到已有的多种有向网络表示学习方法中,多个有向网络数据集上的链接预测和节点分类任务的实验结果表明,所提方法的性能相比原有方法得到了明显提升。     

潜在最小二乘回归子空间分割方法*

子空间分割已逐渐成为高维数据聚类的有效工具,但数据缺失或噪声干扰将直接影响子空间分割方法中仿射矩阵的构造,进而影响聚类效果.为解决这一问题,文中提出潜在最小二乘回归子空间分割方法,分别从行和列两个方向重构数据矩阵,并交替优化两个重构系数矩阵,充分考虑两个方向的表示信息.在6个基因表达数据集上的实验表明文中方法优于现有子空间分割方法.     

基于多目标优化的网络社区发现方法

社区发现是复杂网络挖掘中的重要任务之一,在恐怖组织识别、蛋白质功能预测、舆情分析等方面具有重要的理论和应用价值.但是,现有的社区质量评判指标具有数据依赖性与耦合关联性,而且基于单一评判指标优化的网络社区发现算法有很大的局限性.针对这些问题,将网络社区发现问题形式化为多目标优化问题,提出了一种基于多目标粒子群优化的网络社区发现算法MOCD-PSO,它选取模块度Q、最小最大割MinMaxCut 与轮廓(silhouette)这3 个指标进行综合寻优.实验结果表明,MOCD-PSO 算法具有较好的收敛性,能够发现分布均匀且分散度较高的Pareto 最优网络社区结构集,并且无论与单目标优化方法(GN 与GA-Net)相比较,还是与多目标优化算法(MOGANet与SCAH-MOHSA)相比较,MOCD-PSO 算法都能在无先验信息的条件下挖掘出更高质量的网络社区.     

基于Kullback-Leibler距离的二分网络社区发现方法

现实世界存在大量二分网络,研究二分社区结构有助于从新角度认识和理解复杂网络。由于二分网络特殊的二分结构,使得基于单模网络的现有社区发现算法无法适用。本文提出一种基于Kullback-Leibler距离的二分网络社区发现算法,该算法将异质节点间的连接关系转化为其在用户节点集上的连接概率分布,并建立基于概率分布的KL相似度衡量节点连接模式的差异性,从而克服二分结构对节点相似性评估的不利影响,实现对二分网络异质节点的社区发现。在人工网络和真实网络上的实验和分析表明：该算法能够有效挖掘二分网络社区结构,改善二分网络社区发现的准确性和效率。     

一种新的社区/动态社区优化方法

社区结构作为复杂网络的重要 拓扑特性之一,成为当前的研究热点。本文提出了一种基于边排序和模块度优化的社区发现方法。该方法首先对初始的静态网络进行稀疏化,然后在稀疏化后的网络上依据边的重要程度对边进行排序,给出了一种模块度最大化、快速边合并的社区发现方法(Fast rank base d community detection, F RCD)。在初始网络社区划分结果的基础上,将该方法推广到动态、实时社区划分上,给出了一种快速、鲁棒的动态社区划分方法(Incremental dynamic community detection, IDCD)。理论分析 表明FRCD相对于边具有线性时间复杂度。在实际 和人工网络上的实验结果均表明,本文提出的方法无论在静态网络社区划分还是在动态网络社区追踪上都优于已有方法。     

图重构下大规模网络的社团检测算法

对大型复杂网络进行高质量的社团检测通常依赖图的拓扑结构来划分节点集,然而现实世界的网络通常带有嘈杂且与集群无关的链接,这些链接可能会导致模型将来自不同集群的节点划分在一起。为此,提出了基于图重构的社团检测算法（graph reconstruction based community detection,GRCD）,该方法能够处理大规模复杂网络的社团检测。首先,删除社团之间的相互连接的边来重新构建原始图的社团结构;然后,将网络视为一个社交系统,旨在以更直观的方式揭示社团;提出了一种高效的社团检测策略,即基于话语权的社团组织生成策略;最后,在不同规模数据集上进行实验。实验结果表明,GRCD算法不仅能够处理大规模网络,而且在保持较高稳定性的同时,其社团划分的质量对比现有的几种基准算法都有很强的竞争力。     

基于加权投影的二分网络的链路预测

二分网络上的链路预测是复杂网络中的重要研究内容。充分利用拓扑结构,提出一种基于双向投影的二分网络上的链路预测算法。它能同时投影二分网络上的两类节点,分别生成基于顶部节点的投影图和基于底部节点的投影图。通过基于资源分配的加权方法得到同类节点之间的资源权重比,利用相似度度量两类节点之间未链接边资源分配值进行比较,预测出链路边。在实验分析中通过利用AUC来分析算法的准确性和精度,得出该算法具有一定的优势。     

基于蚁群优化的二分网络社区挖掘

近年来,网络社区挖掘得到了极大的关注,尤其是针对二分网络的社区挖掘。二分网络社区挖掘对于研究复杂网络有非常重要的理论意义和实用价值。提出了一个基于蚁群优化的二分网络社区挖掘算法。该算法首先将二分网络社区挖掘问题转化成一个优化问题,建立一个可供蚂蚁搜索的图模型。同时,根据顶点的拓扑结构定义启发式信息。每只蚂蚁根据每条路径上的信息素和启发式信息选择路径,构造出一个社区的划分,再用二分模块度去衡量社区划分的优劣。实验结果表明,该算法不但可以较准确地识别二分网络的社区数。而且可以获得高质量的社区划分。     

基于连边距离矩阵的重叠社区发现

现有重叠社团发现算法大多直接从相邻连边的相似性出发,不能有效利用网络的多层连边信息。基于此,本文提出了一种基于连边距离矩阵的重叠社区发现算法LDM。首先结合连边-节点-连边随机游走模型,以实现多级连边信息的有效利用,其次借助模糊聚类方法,处理连边距离矩阵以获取连边社区,最后根据扩展模块度调整和优化重叠社区结构。在人工网络和真实网络上的实验结果表明,所提算法能够有效提高重叠社区发现算法的准确度。     

Dual modularity optimization for detecting overlapping communities in bipartite networks

Many algorithms have been designed to discover community structure in networks. These algorithms are mostly dedicated to detecting disjoint communities. Very few of them are intended to discover overlapping communities, particularly the bipartite networks have hardly been explored for the detection of such communities. In this paper, we describe a new approach which consists in forming overlapping mixed communities in a bipartite network based on dual optimization of modularity. To this end, we propose two algorithms. The first one is an evolutionary algorithm dedicated for global optimization of the Newman’s modularity on the line graph. This algorithm has been tested on well-known real benchmark networks and compared with several other existing methods of community detection in networks. The second one is an algorithm that locally optimizes the graph Mancoridis modularity, and we have adapted to a bipartite graph. Specifically, this second algorithm is applied to the decomposition of vertices, resulting from the evolutionary process, and also characterizes the overlapping communities taking into account their semantic aspect. Our approach requires a priori no knowledge on the number of communities searched in the network. We show its interest on two datasets, namely, a group of synthetic networks and real-world network whose structure is also difficult to understand.     

一种基于随机块模型的快速广义社区发现算法

随机块模型可以生成各种不同结构(称作广义社区,包括传统社区、二分结构、层次结构等)的网络,也可以根据概率对等原则发现网络中的广义社区.但简单的随机块模型在网络生成过程建模和模型学习方面存在许多问题,导致不能很好地发现实际网络的结构,其扩展模型GSB(general stochastic block)基于链接社区思想发现广义社区,但时间复杂度限制其在中大型规模网络中的应用.为了在无任何先验的情形下探索不同规模网络的潜在结构,基于GSB 模型设计一种快速算法FGSB,更快地发现网络的广义社区.FGSB 在迭代过程中动态学习网络结构参数,将GSB 模型的参数重新组织,减少不必要的参数,降低算法的存储空间;对收敛节点和边的参数进行裁剪,减少每次迭代的相关计算,节省算法的运行时间.FGSB 与GSB 模型求解算法有相同的结构发现能力,但FGSB 耗费的存储空间和运行时间比GSB 模型求解算法要低.在不同规模的人工网络和实际网络上验证得出:在近似相同的准确率下,FGSB 比GSB 模型求解算法快,且可发现大型网络的广义社区.     

基于半局部结构的异常连边识别算法

随着网络科学领域研究的进展,所涉及的真实网络类型愈加广泛.复杂系统中存在的冗余错误关系,或出于异常目的 刻意发生的行为,如网页错误点击、电信网刺探呼叫等,都对基于网络结构的分析工作造成了重大影响.复杂网络异常连边识别作为图异常检测重要分支,旨在识别网络结构中由于人为制造或数据收集错误所产生的异常连边.现有方法主要从结构...