机器学习作为数据挖掘领域的一个热点研究方向,特别擅长处理结构化的矢量数据。然而,由于政策法规以及对用户隐私权的保护,有时我们并不能够获取完整的或者重要的节点属性信息,这使得机器学习算法的应用受到了极大的限制。作为数据挖掘领域的另外一个研究热点方向,网络分析方法能够将自然界的大多数复杂系统用网络的形式来表示,因此网络分析方法能够不受数据集的限制。目前,传统的网络分析方法大多数是基于邻接矩阵或者邻接表。随着网络规模的不断扩大,利用邻接矩阵来存储这些稀疏元素会严重浪费存储资源,有时甚至是不可能的;而邻接表的方式又不方便计算机的处理和计算。此外,网络分析方法大多采用一种大规模的批处理方式,很难为单独的请求提供实时响应。为此,网络嵌入学习逐渐发展起来并成为网络分析的一个焦点研究方向。网络嵌入算法的目的就是将网络的节点映射到一个低维特征空间中,同时保持网络的拓扑结构、节点信息等等。这样,每个节点都可以用一个矢量来表示。在对网络的全部或者部分节点进行分析时,只需利用基于矢量的数据挖掘方法来执行网络分析任务。网络嵌入算法使得网络分析的方式更加丰富和方便,许多热门的技术被引入到网络嵌入学习中,并产生了一系列优异的算法,例如Deep Walk、Node2vec、LINE等等。网络嵌入算法在多个应用方面的不俗表现,使得此类算法在网络分析中有着无穷的潜力。然而,网络嵌入算法的应用仍然面临着许多挑战,比如传统的社区发现算法在新的特征空间中变得不再适用,取而代之的是用k-means进行聚类。我们通过对真实数据集在新的特征空间中进行可视化分析发现,真实网络的社区结构在新的特征空间中呈现流形(Manifold)特点,并可能是任意形状的。结合社区发现的一些实际需求,我们需要一款能够识别任意形状簇,尽可能减少参数数量且能够预测簇个数的聚类算法。本文的主要工作以及创新点如下:1.分析了网络的一阶接近度、二阶接近度和Skip Gram模型,并从理论上证明了Skip Gram模型可以同时保持一阶接近度和二阶接近度。在此基础上我们提出了一种基于Proximity的网络嵌入算法(Preserving Proximities for Network Embedding),记作PPNE。在链路预测方面的实验结果表明PPNE算法有着较高的准确度,并且可以调节网络重建和网络预测的权重。2.分析了Minimax距离超空间的一些性质,并解释了它与最小生成树之间的关系。最后基于这些性质,提出了一种全局最优的Path-based聚类算法(Global Optimal Path-based Clustering Algorithm),这里记作GOP。GOP只需要输入一个参数k并且能通过决策图来交互决定。在综合数据集和真实数据集上的实验结果表明,GOP具有很强的鲁棒性且能够识别任意形状的簇。以上的这些优点使得该算法非常适合作为一个普适的聚类算法。3.结合了上述两个算法来进行社区发现,并与传统的基于网络存储方式的经典算法进行对比。实验的结果表明在大多数真实网络中,本文提出的算法都有着优异的表现,可以取代传统的社区发现方法。