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

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

复杂网络中社区发现方法的研究

研究复杂网络中社区发现方法对分析复杂网络的拓扑结构和层次结构、理解社区的形成过程、预测复杂网络的变化趋势、挖掘复杂网络蕴含的规律特征具有十分重要的意义。同时,复杂网络社区发现方法在众多实际领域还有广泛的应用前景。综述了复杂网络社区发现方法的研究现状,将社区发现方法分为无重叠社区发现、重叠社区发现、演化发展社区发现三个方面,并分析比较了算法时间复杂度和准确度。试图为社区发现方法的研究工作提供有益的帮助和参考。     

一种基于元胞自动机的无向图剖分优化算法

运用元胞自动机理论,针对无向图剖分优化问题进行了分析和建模,提出了一种元胞自动机模型以及基于该模型的无向图剖分优化算法。在该元胞自动机模型中,元胞对应于无向图中的结点,元胞的邻居对应于邻接结点,元胞空间对应于无向图中的结点集,元胞的状态对应于所在的结点子集。实验及分析表明该算法不仅能找到无向图的近似最优剖分,而且有效地降低了空间复杂度和时间复杂度。     

基于节点局部相似性的两阶段密度峰值重叠社区发现方法

为了有效地发现复杂网络中的重叠社区结构,引入了密度峰值聚类算法,但将此算法应用于社区发现还存在如何度量节点间距离、如何产生重叠划分结果等问题。为此提出了一种基于节点局部相似性的两阶段密度峰值重叠社区发现方法(Node Local Similarity Based Two-stage Density Peaks Algorithm for Overlapping Community Detection, LSDPC)。该方法结合大度节点有利指标和连接贡献度定义了一种新的节点局部相似性指标,首先通过节点局部相似性度量节点距离;然后通过节点的局部密度和最小距离计算节点中心值,利用切比雪夫不等式筛选出社区中心节点;最后经过初次划分与重叠划分两阶段得到最终的重叠社区划分结果。在真实网络数据集与合成网络数据集上的实验结果表明,所提算法可以有效发现重叠社区结构,且结果优于其他对比算法。     

一种基于信息扩散的复杂网络重叠社区发现算法

社区结构可以为网络的其他分析挖掘提供中观尺度的分析视角,在大规模复杂网络的各项研究中是一项非常重要而基础的工作。社区的重叠是真实世界网络中常见的一种现象,重叠社区结构可以更准确地描述网络中真实的结构信息,因此,复杂网络重叠社区发现具有更加突出的现实意义。在综合对比分析了当前主要的重叠社区发现算法的基础上,结合信息论的相关知识,给出了一种基于信息论的社区定义,并进一步借鉴信息传播理论,从单个节点对关于某种主题的信息的掌握程度的角度出发提出了一种复杂网络重叠社区结构发现算法。基于实际数据集的相关实验表明,与传统的社区定义和社区发现算法相比,本算法发现的重叠社区从内容角度来看具有更加明确的实际意义,并且具有较低的时间复杂度。     

有向网络重叠社区的快速划分算法

随着社会的发展,数据量越来越大,网络规模也在迅速增长。作为一种研究网络结构的有效方法,社区划分对于深刻认识超大规模网络有重要的意义。在分析研究有向网络的非重叠社区划分算法和无向网络的重叠社区划分算法的基础上,提出了一种有向网络重叠社区划分的快速算法。算法根据节点的有向权值和归属度进行社区划分,并分析了有向权值和归属度对划分结果的影响,在此基础上得到了一组最优的有向权值和归属度参数。使用2个实际网络和1个人工构建网络对算法的性能进行了测试并与已有算法进行了对比。实验结果表明,所提出的算法能够有效地划分出有向网络中的重叠社区。     

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

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

一种局部的重叠社区发现方法

研究重叠社区发现技术,可以将重叠社区转化为非重叠的社区发现。通过分裂结点后,使用已有的非重叠社区发现算法来进行社区划分,然后将分裂后的结点还原为源结点即可发现重叠社区。而结点是否分裂由分裂系数来衡量。使用局部的方法来计算结点的分裂系数,并分裂具有较大分裂系数的结点。实验表明此方法可以有效地发现重叠社区,并从时间复杂度上优于基于全局的方法。     

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

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

复杂网络社区挖掘的距离相似度算法

有效挖掘出复杂网络中隐藏的社区结构具有重要的理论研究意义和广泛的应用前景,目前已有多种关于社区挖掘算法和社区性质的研究,但还未见深入讨论结点间距离与全局社区结构内在关系的工作.因此,深入研究了它们之间的内在联系,发现较近(远)的结点通常以较大的概率属于相同(不同)社区,相同(不同)社区中的结点距离通常较小(较大).基于...     

结构-属性平衡图节点相似度测量算法

摘  要：节点相似度是图聚类算法的重要基础,在基于结构-属性图聚类现有方法中,由于传统图模型的限制,需要多次矩阵相乘来调整属性边的权值,算法执行效率低。为解决这一问题,提出了结构-属性平衡图的概念,并采用随机游走模型策略统一度量结构-属性平衡图GB中顶点间的相似度。与现有方法相比,该方法不但能测量直接相连的顶点之间的相似度,还可测量不直接相连而存在不同长度的路径的顶点之间的相似度,且没有增加原相似度矩阵的规模,节省了大量存储空间,提高了算法执行效率。     

Distance‐based control of formations with hybrid communication topology

In this paper, we focus on the control of multiagent formations with hybrid communication topology through a distance‐based approach. By saying hybrid topology, we mean that the communication topology contains both undirected and directed links, or the underlying graph of the formation contains both undirected and directed edges. A new type of graph, ie, hybrid graph, is introduced. We discuss the persistence of hybrid graphs and present the persistence verification strategy for hybrid graphs. It is proved that all the minimally persistent hybrid graphs can be obtained from persistent directed graphs by the operation of edge transformation. As the main result, it is shown that multiagent formations modeled by acyclic persistent hybrid graphs can be stabilized locally under distance‐based controllers.     

WSM: a novel algorithm for subgraph matching in large weighted graphs

Given an undirected/directed large weighted data graph and a similar smaller weighted pattern graph, the problem of weighted subgraph matching is to find a mapping of the nodes in the pattern graph to a subset of nodes in the data graph such that the sum of edge weight differences is minimum. Biological interaction networks such as protein-protein interaction networks and molecular pathways are often modeled as weighted graphs in order to account for the high false positive rate occurring intrinsically during the detection process of the interactions. Nonetheless, complex biological problems such as disease gene prioritization and conserved phylogenetic tree construction largely depend on the similarity calculation among the networks. Although several existing methods provide efficient methods for graph and subgraph similarity measurement, they produce nonintuitive results due to the underlying unweighted graph model assumption. Moreover, very few algorithms exist for weighted graph matching that are applicable with the restriction that the data and pattern graph sizes are equal. In this paper, we introduce a novel algorithm for weighted subgraph matching which can effectively be applied to directed/undirected weighted subgraph matching. Experimental results demonstrate the superiority and relative scalability of the algorithm over available state of the art methods.     

基于Ncut准则的图分割的新算法

针对有权图分割时不能很好解决子图内部耦合度不高的问题,使用可以同时优化子图内部顶点耦合度和子图之间顶点耦合度的Ncut准则,提出了一种新的基于迭代改善策略的RNK分割算法。算法通过不断交换可以改善Ncut值的顶点对优化现有分割。与传统分割算法相比,可以同时保证子图内最大耦合度和子图间最小的耦合度。并提出一种散列技术,提高查找最优交换顶点对的效率。当图为稠密矩阵时,改善效果尤为明显。通过对随机图分割的实验结果表明,该算法较传统的KL算法可以得到更理想的分割结果。     

权长相合的带权无向图画图算法

针对带权无向图的输出需用边长反映权值大小的问题,提出了一种基于遗传算法的带权无向图画图算法,通过对顶点坐标的编码进行交叉和变异来得到理想的节点坐标,变异算子结合了非一致性变异和单点邻域变异,并在适应度函数中运用顶点平均距离、边交叉数、多度顶点相关边夹角均匀度、边的权值长度比一致程度四个美学标准。实验结果表明,该算法画出的图形连线无交叉,分支清晰,权值—长度相合,能得到清晰、美观且能直观反映权值的可视化输出结果,可应用于带权无向图的可视化输出系统的设计。     

基于节点拓扑结构和属性的重叠社区检测算法

近些年来,网络中的重叠社区检测应用越来越广泛,这极大引起了人们的兴趣。通常重叠社区检测只考虑节点的拓扑结构信息,忽略了节点的属性信息,这可能会遗漏数据间的重要结构。本文提出了一种基于节点拓扑结构和属性相似度的局部社区检测算法。首先,计算出节点与社区之间属性相似度。其次,为挖掘内部紧耦合的社区,计算出能够表示耦合性的模块度增量。最后,通过融合多个已检测到局部社区,计算出隶属矩阵从而获取全局重叠社区结构。在三个有真实社区的数据集上的实验结果从内部指标模块度和与真实社区的比较验证了基于节点拓扑结构和属性相似度的重叠社区检测算法比目前基于节点结构的社区检测算法在效率和有效性上有所提升。     

面向对象的动态图编辑器的设计与实现

提出了一种面向对象的动态图编辑器,该动态图编辑器区别一般图编辑器的方面在于：可以根据用户的需要在任何时候动态地执行用户程序定义的方法;产生可序列化的图;编辑部分和显示部分既能合并使用也能分开使用;允许用户定义任意形状的结点和弧;具有处理无向图和有向图的双重功能。用户可以分别利用交互式编辑环境和图布局机制输入小型图和中、大型图。动态图编辑器体系结构建立在软件工程设计模式和面向对象设计思想的基础上,用ＪＡ－ＶＡ２实现。     

基于图匹配的分层布局算法

针对节点数目较大并且度数比较平均的无向图,根据分层扩展的思想,提出一种基于图匹配的分层布局算法（Graph Matching Hierarchy,GMH）。基于图匹配思想对大图进行递归化简,然后应用FR算法对最粗化图进行布局,最后利用质心布局算法对图进行扩展。实验结果表明,GMH算法能够提高可视化效率,改善布局效果,且分层布局的结果更易于理解。      

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

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