基于对比学习的多关系属性图聚类方法

现实世界包含复杂的图数据，其节点之间通常包含多种关系，这种图被称为多关系属性图。图聚类是挖掘图数据相似信息的技术之一，然而现有的图聚类的方法大多只适用于单关系图。即使有的方法考虑到了多关系图，也往往是将图表示学习与聚类看作两个单独的过程。受Deep Graph Infomax(DGI)算法的启发，文中设计了一种基于对比学习的多关系属性图的聚类方法(CCLMAG),用于解决上述问题：1)通过引入社区级互信息机制，弥补了DGI算法无法融合簇信息的缺点；2)引入嵌入融合模块来聚合不同关系上的节点嵌入；3)引入聚类优化模块将图表示学习与聚类两个过程联系起来，使得学习到的节点表示更适合聚类任务。在3个公开数据集和1个构建的期货数据集上的大量实验表明，所提方法优于目前最先进的基线方法，且具有实际应用价值。     

基于矩阵分解的属性网络嵌入和社区发现算法

属性网络不但包含节点之间复杂的拓扑结构,还包含拥有丰富属性信息的节点,其可以比传统网络更有效地建模现代信息系统,属性网络的社区划分对于分析复杂系统的层次结构、控制信息在网络中的传播和预测网络用户的群体行为等方面具有重要的研究价值.为了更好地利用拓扑结构信息和属性信息进行社区发现,提出了一种基于矩阵分解的属性网络嵌入和社区发现算法(CDEMF).首先提出基于矩阵分解的属性网络嵌入方法,基于网络局部链接信息计算相邻节点的相似性,将其与属性接近度联合建模,通过矩阵分解的分布式算法得到每个节点对应的低维嵌入向量,即把网络节点映射为低维向量表示的数据点集合.接着提出基于曲率和模块度的社区划分方法,自动确定数据点集合中蕴含的社区数量,并通过对数据点集合聚类完成属性网络社区划分.在真实网络数据集上,将CDEMF方法与其他8种知名算法进行比较,实验结果表明CDEMF具有良好的性能.     

基于双监督网络嵌入的社区发现算法

针对基于网络嵌入的社区检测算法中节点嵌入和聚类过程独立进行时容易陷入局部极值的问题,文中提出基于双监督网络嵌入的社区发现算法.首先利用图自编码器,得到可保持网络的一阶相似性的节点嵌入.优化模块度,发现拓扑连接紧密的社区.采用自监督聚类优化,发现嵌入空间上相似的社区.引入互监督机制,使发现的社区在模块度优化和自监督聚类这...     

层次标签引导的属性网络嵌入

网络嵌入是在保持网络性质不变的前提下,将节点转换为低维向量,以便下游任务的求解.现有网络嵌入方法的研究大多关注于网络结构、节点属性信息或单层次标签信息等方面.然而,许多真实世界的网络节点通常具有丰富的层次标签信息,这些层次标签信息对获取高效的网络嵌入具有重要价值.由于不同层次的标签之间的信息很难相互关联或继承,如何合理利用层次标签信息进行网络嵌入,获得更高效的向量表示是亟待研究的问题.针对上述问题,提出了一种新的基于层次标签的属性网络嵌入框架(HLANE),该框架利用层次注意力机制将层次标签信息融入网络嵌入中.HLANE框架首先通过现有的网络嵌入方法获取结构和/或属性信息初始化节点的嵌入向量.然后通过层次注意力机制层建立多层次标签的父节点和子节点之间的联系,并依此指导网络节点初始化嵌入向量在不同层次的学习,最终生成网络节点的多层次嵌入向量表示.在真实数据集上的实验表明,与对比算法相比,HLANE框架具有更好的网络节点嵌入表示.     

无监督空谱近邻超图嵌入高光谱图像特征提取

针对高光谱图像数据标注困难,以及传统图嵌入方法无法表征高维数据之间的多元复杂关系的问题,提出面向高光谱特征提取的无监督空谱近邻超图嵌入算法.充分利用高光谱的空间信息与光谱信息揭示像元之间的相关性,构造有效的无监督空谱近邻关系,引入超图学习表征高维数据之间的复杂多元关系,提高特征提取性能.将所提算法与同类算法在Indian Pines和Salinas数据集上进行实验,其结果表明,所提算法能够获得较高的分类精度.     

网络嵌入随机块模型的社区发现和链路预测

社区发现与链路预测任务是网络数据研究中的热点问题, 兼顾网络传递性与区块结构有助于捕捉个体之间的有效关联、探测数据中蕴含的内在规律, 帮助研究者挖掘更多数据价值进而做出决策. 当前的算法与模型多侧重于网络传递性或区块结构单一层面的分析, 且依赖一定的假设条件. 本文提出网络嵌入随机块模型(NE-SBM)用于社区发现与链路预测. 搭建贝叶斯框架完成模型参数的正则化, 利用Metropolis Hasting-Gibbs算法获得节点嵌入表示的隐位置与社区隶属关系, 基于多维尺度变换算法解决隐位置可识别性问题. 本方法可解决传统启发式算法中过分依赖判断准则或评价函数的问题, 对各类型的数据都具有更好的适应性. 人工数据及真实数据的实验结果进一步验证了该方法在社区发现与链路预测中有更优的表现.     

基于图注意力网络表示学习的协同过滤推荐算法

针对传统的基于模型的协同过滤推荐算法未能有效利用用户与项目的属性信息以及用户之间与项目之间的关系结构信息, 本文提出一种基于图注意力网络表示学习的协同过滤推荐算法. 该算法使用知识图谱表示节点的属性特征信息和节点间的关系结构信息, 并在用户和项目的同质网络上进行节点的图注意力网络表示学习, 得到用户和项目的网络嵌入特征表示, 最后构建融合网络嵌入信息的神经矩阵分解模型获得推荐结果. 本文在Movielens数据集上与相关算法进行对比实验, 实验证明该算法能优化模型的推荐性能, 提高推荐的召回率HR@K和归一化折损累计增益NDCG@K.     

一种结合聚集图嵌入的社会化推荐算法

社交网络信息已被广泛的应用到传统的推荐上,一定程度上减轻了数据稀疏和冷启动问题.随着表示学习的兴起,出现了利用表示学习进行推荐的算法研究.然而社交网络过大,表示学习可扩展性差,难以在有限内存中进行计算.聚集图通过空间压缩,保留了关键的结构关系,去除次要或噪音的结构数据,便于表示学习能够有效学习图结构,从而更好地找到相似用户进行推荐.首先,利用图聚集算法同时考虑分组间及分组内的结构得到最终的聚集图;其次,在聚集图上计算随机游走的转移概率,然后选择每个具有偏差概率的后继节点并生成节点序列;最后将节点序列输入到skip-gram学习用户的潜在表示,获得节点的表示向量整合其信息到贝叶斯个性化排序模型(BPR)来解决项目排名问题.实验结果表明,该方法相比于社会化贝叶斯个性化排序(SBPR)、协同用户网络嵌入(CUNE)等基线方法在推荐任务中保持时间效率的同时有效提升了准确率、召回率和平均精度均值.     

复杂网络大数据中重叠社区检测算法

大数据时代互联网用户数量呈爆炸性增长,社交网络、电商交易网络等复杂网络规模快速发展,准确有效地检测复杂网络大数据中重叠社区结构对用户兴趣点推荐和热点传播具有重要意义。提出一种新的面向复杂网络大数据的重叠社区检测算法DOC（Detecting Overlapping Communities over complex network big data）,时间复杂度为O（nlog²（n））,算法基于模块度聚类和图计算思想应用新的节点和边的更新方法,利用平衡二叉树对模块度增量建立索引,基于模块度最优的思想设计一种新的重叠社区检测算法。相对于传统重叠节点检测算法,对每个节点分析的频率大大降低,可以在较低的算法运行时间下获得较高的识别准确率。复杂网络大数据集上的算法测试结果表明：DOC算法能够有效地检测出网络重叠社区,社区识别准确率较高,在大规模LFR基准数据集上其重叠社区检测标准化互信息指标NMI最高能达到0.97,重叠节点检测指标F-score的平均值在0.91以上,且复杂网络大数据下的运行时间明显优于传统算法。     

基于KNN与矩阵变换的图节点嵌入归纳式学习算法

图节点的低维嵌入在各种预测任务中是非常有用的,如蛋白质功能预测、内容推荐等。然而,多数方法不能自然推广到不可见节点。图采样聚合算法(Graph Sample and Aggregate,Graphsage)虽然可以提高不可见节点生成嵌入的速度,但容易引入噪声数据,且生成的节点嵌入的表示能力不高。为此,文中提出了一种基于KNN与矩阵变换的图节点嵌入归纳式学习算法。首先,通过KNN选取K个邻节点;然后,根据聚合函数生成聚合信息;最后,利用矩阵变换与全连接层对聚合信息和节点信息进行计算,得到新的节点嵌入。为了有效权衡计算时间与性能,文中提出一种新的聚合函数,对邻节点特征运用最大池化作为聚合信息输出,以更多地保留邻节点信息,降低计算代价。在reddit和PPI两个数据集上的实验表明,所提算法在micro-f1和macro-f1两个评价指标上分别获得了4.995%与10.515%的提升。因此,该算法可以大幅减少噪声数据,提高节点嵌入的表示能力,快速有效地为不可见节点及不可见图生成节点嵌入。     

Network representation learning based on community-aware and adaptive random walk for overlapping community detection

The Network representation learning methods based on random walk aim to learn a low-dimensional embedding vector for each node in a network by randomly traversing the network to capture the features of nodes and edges, which is beneficial to many downstream machine learning tasks such as community detection. Most of the existing random-walk-based network representation learning algorithms emphasize the neighborhood of nodes but ignore the communities they may form and apply the same random walk strategy to all nodes without distinguishing the characteristics of different nodes. In addition, it is time-consuming to determine the most suitable random walk parameters for a given network. In this paper, we propose a novel overlapping community detection algorithm based on network representation learning which integrates community information into embedding vectors to improve the cohesion degree of similar nodes in the embedding space. First, a node-centrality-based walk strategy is designed to determine the parameters of random walk automatically to avoid the time-consuming manual selection. Second, two community-aware random walk strategies for high and low degree nodes are developed to capture the characteristics of the community centers and boundaries. The experimental results on the synthesized and real-world datasets demonstrate the effectiveness and efficiency of our algorithm on overlapping community detection compared with the state-of-the-art algorithms

     

True-link clustering through signaling process and subcommunity merge in overlapping community detection

To overcome the difficulty in detecting reliable overlapping communities in complex networks, “true-link” and “pseudo-link” are firstly proposed on the basis of the original network graph. Then, the “true-link” graph is obtained through the preprocessing of the original network graph. And then the line graph is partitioned by means of signaling process and single-linkage hierarchical clustering. Meanwhile, the subcommunities are merged based on the proposed similarity between communities, which eradicates the inherently redundant overlapping communities to a certain extent. Compared with other overlapping community detection algorithms, this proposed algorithm is of strong robustness and high accuracy. All the results of the experiments boil down to the conclusion that this True-link Clustering Community Detection is an overlapping community detection algorithm prevailing over others.

     

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.     

局部扩展的遗传优化重叠社区发现方法

重叠社区结构是复杂网络的一种重要的特征,提出了一种局部扩展的遗传优化重叠社区发现（LEGAOCD）。借鉴局部扩展的重叠社区发现方法的思想,将少数的核心节点构成模体;同时,利用了三角形模体来判断社区的稳定性度量问题,从而量化社区结构稳定性;然后通过改进的遗传优化算法策略分配它们应归属的社区;最后通过两个评价目标函数得到高质量的重叠社区结构。该算法在数据集上与经典的CPM算法、COPRA算法作比较,实验结果表明,LEGAOCD算法在检测重叠社区结构和重叠节点方面具有较优的性能。     

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

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

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

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

一种基于粗糙集和密度峰值的重叠社区发现方法

随着互联网和社会的发展,各个领域每天都会产生大量相互关联、彼此依赖的数据,这些数据根据不同的主题形成了各种复杂网络。挖掘社区结构是复杂网络领域中的一项重要研究内容,因为其在推荐系统、行为预测和信息传播等方面具有极其重要的意义。社区结构中的重叠社区结构在生活中普遍存在,更具有实际研究意义。为有效发现复杂网络中的重叠社区,文中引入了粗糙集理论对社区进行分析,识别出重叠节点,进而提出了一种基于粗糙集和密度峰值的重叠社区发现方法OCDRD(Overlapping Community Detection Algorithm Based on Rough Sets and Density Peaks)。该方法在传统网络节点局部相似性度量的基础上,结合灰色关联分析方法求出网络节点间的全局相似性,进而将其转化为节点间距离。将密度峰值聚类算法的思想应用于该算法中,以根据网络结构自动选取社区中心节点。依据网络中节点的距离比例关系,定义了社区的上近似、下近似以及边界域。最后,不断调整距离比率阈值并进行划分迭代,在每次迭代中针对社区的边界域进行计算,从而获得最佳重叠社区划分结构。在LFR基准人工网络数据集和真实网络数据集上,基于标准互信息(Normalized Mutual Information,NMI)和具有重叠性模块度EQ这两个评价指标,将OCDRD方法与近几年效果较好的其他社区发现算法进行测试比较。实验结果显示,OCDRD方法在社区划分结构方面整体优于其他社区发现算法,表明了该算法的可行性和有效性。     

结合拓扑势与信任度调整的重叠社区发现算法

现实世界中的复杂系统可建模为复杂网络,探究复杂网络中的社区发现算法对于分析复杂网络的拓扑结构和层次结构具有重要作用。早期研究通常将网络中的节点局限在一个社区中,但随着研究的深入发现社区结构呈现重叠特性。针对现有重叠社区发现算法存在划分社区结构不稳定、忽略节点交互和属性等问题,提出一种基于网络拓扑势与信任度调整的重叠社区发现算法。融合节点的属性和结构特征计算节点的拓扑势,依据节点的拓扑势选取核心节点。从核心节点出发构建初始社区群,计算各个社区间的调整信任度,实现社区的合并与再调整,从而识别重叠社区。在多个人工模拟网络和真实网络数据集上的实验结果表明,与基于贪婪派系扩张、种子扩张等的重叠社区发现算法相比,该算法将扩展模块度最高提升至0.719,能有效识别社区结构及重叠节点,提升重叠社区检测性能。     

基于图划分抽样算法的图表示学习

在基于神经网络的图表示算法中,当节点属性维度过高、图的规模过大时,从内存到显存的数据传输会成为训练性能的瓶颈。针对这类问题,该方法将图划分算法应用于图表示学习中,降低了内存访问的I/O开销。该方法根据图节点的度数,将图划分成若干个块,使用显存缓存池存储若干个特征矩阵块。每一轮训练,使用缓存池中的特征矩阵块,以此来减少内存到显存的数据拷贝。针对这一思想,该方法使用基于图划分的抽样算法,设计显存的缓存池来降低内存的访问,运用多级负采样算法,降低训练中负样本采样的时间复杂度。在多个数据集上,与现有方法对比发现,该方法的下游机器学习准确率与原算法基本一致,训练效率可以提高2~ 7倍。实验结果表明,基于图划分的图表示学习能高效训练模型,同时保证节点表示向量的测试效果。今后的课题可以使用严谨的理论证明,阐明图划分模型与原模型的理论误差。