基于连边相似度的重叠社区发现算法研究

针对GN算法在发现重叠社区时存在的不足,以及为了降低算法时间复杂度,提出一种基于网络图中连边相似度划分连边集的重叠社区发现算法EGN。算法依据网络图的连边集进行划分,每一条边被划分到某个特定的社区,而一个节点可以关联多条连边,因此节点可以被划分到不同的社区,从而发现重叠社区。EGN算法首先需要构造网络节点之间连边关系的边图;然后根据边图中节点的关系计算网络图中连边的相似度,在节点之间相似度的基础上提出了连边之间相似度的计算方法;再按照相似度由小到大对边图删除边,构建出边图的树状图。树状图的每一层对应网络的一个划分,采用划分密度函数来衡量划分的质量,以此寻找最优的划分。最后将算法应用到Zachary空手道俱乐部网络中,并与GN算法进行对比,实验结果表明EGN算法能够很好地发现重叠社区。     

基于连边密度传播的二分网络社区发现算法

依据节点在社区中的连边情况,定义社区内节点的连边密度,构造社区的平均密度评价指标。经过实例验证,社区的平均密度评价指标能够克服模块度在完全图上的分辨率限制。同时,通过节点的连边密度和最优化社区的平均密度,提出连边密度传播算法。在真实数据和人工数据上进行测试,利用该算法划分社区后求得的模块度和社区平均密度都比利用BRIM算法、边集聚系数算法和资源分布算法求得的值高。这表明相比以上三种算法,连边密度传播算法更能够有效地发现二分网络的社区结构。     

基于边重要度的矩阵分解链路预测算法

基于矩阵分解的链路预测方法的领域适应性较好.然而在已有基于矩阵分解的链路预测方法中,0-1矩阵的网络数据表示对网络中未知连边的假设较强,同时对网络中已知连边的重要度无区分性.为此,文中放松0-1矩阵的网络数据表示假设,对未知节点对连边不做任何假设,并提出边重要度度量方法,对网络中已知连边进行重要度度量,最终建立基于网络权重矩阵分解的链路预测模型.在8个公开网络数据集上对比基于度量的链路预测方法和已有矩阵分解方法,文中方法链路预测结果更好.     

基于时序模体注意力图卷积的动态网络链路预测算法

时序网络中的动态链路预测旨在基于历史连边信息预测未来会产生的连边,是网络分析的重要组成部分,具有极大的理论研究价值和广阔的应用场景.针对现有的动态链路预测算法大多基于一阶连边关系预测未来连边,忽略了对高阶的拓扑信息和时序通联信息的挖掘和利用问题,提出一种基于时序模体注意力图卷积的动态链路预测算法.首先,提出一种时序模体邻接矩阵构建算法,利用时序模体抽取节点间的高阶拓扑和时序关系信息;然后利用隐式调节过程对网络演化过程进行建模,并使用时序模体邻接矩阵作为传输矩阵的图卷积神经网络学习节点的低维向量表示并进行迭代更新;最后以节点间表示向量作为输入,通过计算连边发生的条件密度函数值作为依据完成动态链路预测.在多个真实时序网络数据集上的实验结果表明,所提算法可有效挖掘节点间的高阶拓扑和时序信息,提高动态链路预测效果.     

融合连边符号语义信息的网络表示学习算法

为融合连边符号语义信息提升网络表示学习质量,针对现有算法处理复杂连边符号语义信息能力较弱问题,提出一种融合连边符号语义信息的网络表示学习算法,将包含正负关系的连边符号语义信息引入网络表示学习过程。首先,该算法设计基于三层感知机的关系预测模型刻画节点间不同类型的上下文链接关系;然后,引入随机游走策略实现上下文链接采样以适应大规模网络场景训练需求。在三个数据集中实验表明,该算法能够有效建模节点间不同类型的上下文链接关系,挖掘其中包含的复杂语义信息,相比目前最优的SIDE方法,所提算法的性能分别提高了0.31%、1.3%和1.85%。     

基于边密度聚类的重叠社区发现算法

基于边聚类的社区发现算法以边为聚类对象,自然发现重叠社区,但也存在生成的社区集边界归属模糊、社区结构过度重叠等问题.基于此种情况,文中提出基于边密度聚类的重叠社区发现算法.首先,以边为研究对象,通过密度聚类检测连接紧密的核心边社区.然后,根据边界边归属策略将边界边划分到离它最近的核心边社区.针对孤立边,提出基于边的度与边的社区归属的孤立边处理策略,进一步处理未划分的孤立边,避免社区结构过度重叠的问题.最后,将边社区还原为节点社区,实现重叠社区的发现.在人工数据集和真实数据集上的实验表明,文中算法可以快速准确地检测复杂网络中的重叠社区.     

基于边图的线性流重叠社区发现算法

重叠网络的社区发现是复杂网络研究中的重要问题。为了提高网络中重叠社区发现的时间效率，提出一种基于边图的线性流重叠社区发现算法LBSA。算法首先对于边图网络中的边进行随机的依次处理，完成节点的初步社区划分，再将其中重叠小社区合并到相似度最大的其他大社区中得到最终的社区。通过以上步骤，算法能够以接近线性的时间复杂度得到网络的重叠结构。从最终的实验结果来看，与其他算法相比，该算法能够在更短的时间有质量地发现网络中的重叠社区。     

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

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

基于异质图注意力网络的重叠社区发现方法

为解决异质网络重叠社区发现问题,提出一种基于异质图注意力网络的重叠社区发现模型。通过异质图注意力网络的双层注意力机制,从节点级与语义级充分挖掘节点、元路径在信息表示中的重要程度,并进行分层聚合获得节点特征向量,将伯努利-泊松模型与图卷积网络整合,在生成社区隶属关系矩阵的基础上优化社区重叠度进行重叠社区划分。模型改变异质图注意力网络的激活函数,改善梯度消失问题,将异质图注意力网络与伯努利-泊松模型结合实现异质网络的重叠社区发现。使用真实数据集进行实验,实验结果表明,模型可以利用异质网络节点信息多样性进行重叠社区发现,相对传统社区发现方法具备较好的稳定性和准确性。     

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

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

一种加权稠密子图社区发现算法

目前,针对复杂网络的社区发现算法大多仅根据网络的拓扑结构来确定社区,然而现实复杂网络中的边可能带有表示连接紧密程度或者可信度意义的权重,这些先验信息对社区发现的准确性至关重要.针对该问题,提出了基于加权稠密子图的重叠聚类算法（overlap community detection on weighted networks,简称OCDW）.首先,综合考虑网络拓扑结构及真实网络中边权重的影响,给出了一种网络中边的权重定义方法;进而给出种子节点选取方式和权重更新策略;最终得到聚类结果.OCDW算法在无权网络和加权网络都适用.通过与一些经典的社区发现算法在9个真实网络数据集上进行分析比较,结果表明算法OCDW在F度量、准确度、分离度、标准互信息、调整兰德系数、模块性及运行时间等方面均表现出较好的性能.     

基于信息熵的复杂网络社团划分建模和验证

社团结构是复杂网络最普遍和最重要的拓扑属性之一,社团结构的划分方法对分析复杂网络相关统计特性具有十分重要的理论意义.为了提高社团划分精度,提出了一种新的基于信息熵(information entropy)模块度的社团划分算法(简称IE算法).在有着确定社团结构的数据集和不确定社团结构的数据集上,通过选取Q值、社团划分个数、社团最大连通分量大小和强弱社团个数比例4个重要参数,将IE算法与两种最主要的基于模块度的划分算法GN(Girvan-Newman)和FastGN(Fast Girvan-Newman)进行对比,实验结果证明了IE算法在社团划分性能上优于GN和FastGN;将IE和其他7种最主要的经典社团算法进行时间复杂度分析,并在随机网络和真实网络上进行实验,结果表明该算法时间复杂度在GN与FastGN之间,时间复杂度小于GN而精确度优于GN,证明了在大多数数据集上IE算法的社团划分准确度优于传统基于点边比率的社团划分算法的准确度.     

基于LeaderRank和节点相似性的多标签传播重叠社团挖掘算法

针对基于多标签传播重叠社团挖掘算法COPRA因随机更新策略带来的不稳定性以及需要预先输入参数的局限性等问题,提出一种基于LeaderRank和节点相似性的多标签传播重叠社团挖掘算法.该算法首先利用LeaderRank算法对网络中的节点进行重要性排序从而确定节点的更新顺序,减少标签不必要的更新.在标签传播过程中,根据节点相似性重新设计标签的更新策略,提高算法的稳定性.将算法应用于人工网络和真实网络中进行实验,实验结果表明该算法在挖掘重叠社团上具有较高的准确性和稳定性.     

基于矩阵分解的DeepWalk链路预测算法

现有的链路预测方法的数据来源主要是基于邻居、路径和随机游走的方法,使用的是节点相似性假设或者最大似然估计,尚缺少基于神经网络的链路预测研究。基于神经网络的一些研究表明,基于神经网络的DeepWalk网络表示学习算法可以更加有效地挖掘到网络中的结构特征,已有研究证明DeepWalk等同于分解目标矩阵。因此,提出了一种基于矩阵分解的DeepWalk链路预测算法（LPMF）。该算法首先基于矩阵分解的DeepWalk算法分解得到网络的表示向量;然后通过余弦相似度计算每对节点之间的相似度,构建目标网络的相似度矩阵;最后利用相似度矩阵,在三个真实的引文网络中进行链路预测实验。实验结果表明,提出的链路预测算法性能优于现存的20余种链路预测算法。这充分表明了LPMF能够有效地挖掘网络中节点之间的结构关联性,而且在实际网络的链路预测中能够发挥出较为优异的性能。     

基于随机游走的带有属性网络的链接预测

链接预测的问题是复杂网络分析中的一个重要研究领域,已经在社会学、生物信息学、信息科学以及计算机科学等领域得到了广泛的应用。提出了一个顶点具有属性的网络链接预测的随机游走算法。在此算法中,根据顶点和属性的链接相似度定义了每一条边上的传播概率。并将顶点的属性相似度作为顶点间的相似度的初值,然后根据传输概率在网络中以随机游走的方式进行传播和更新,最终得到顶点间的相似度作为链接预测的结果得分。实验结果显示,提出的算法在顶点带属性的网络中取得了比其他算法更精确的预测结果。     

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.

     

基于随机聚类采样算法的复杂网络社团探测

根据网络节点的局部拓扑信息构建稀疏相似网络。基于稀疏相似网络, 提出了一种改进后的随机聚类采样算法对网络社团进行探测。在人工和真实网络上, 将算法与未改进的随机聚类采样算法以及几种典型的社团探测算法进行了准确率和时间复杂度的比较。实验结果表明, 该方法在时间复杂度上具有明显的优势, 并且具有较好的准确率。     

一种联合拓扑与属性的社区模糊划分算法

现有的社区发现算法通常基于结构特性进行社区划分,对节点属性特征欠缺考虑。为此,提出一种基于模糊等价关系的社区发现算法。用完全相异距离指数的概念将拓扑结构与属性特征相结合,以此作为隶属关系建立模糊等价关系矩阵,选择合适的聚类f阂值对网络进行社区划分。实验结果证明,与传统的GN算法相比,该算法发现社区的准确率较高,在相同社区内的节点连接紧密且具有同质性。