基于关联系数的社区划分算法

不同于一般社区划分衡量标准——模块度Q值,从社区结构本质出发,提出一种用关联系数评判社区划分好坏的方法,即求社区内部连接与外部连接的关联系数。该方法不但能克服模块度Q值只适用于无向无权网络的缺陷,而且更符合社区结构的定义。     

基于引力因子的加权网络重叠社区识别算法

通过挖掘大数据来识别复杂社会网络上的社区,有利于对经济、政治、人口等方面的重要问题进行定量研究,社区的识别算法已经成为当前研究的热点问题。重点研究了重叠社区识别问题,提出了基于引力因子的加权复杂网络的重叠社区识别算法GWCR。该算法首先选取万有引力因子大的节点为中心节点,将节点与中心节点之间的引力因子作为衡量标准,并将节点归入社区引力因子大于某一阈值的社区,最后通过识别重叠节点来识别重叠社区。在3个真实网络数据集上的实验结果表明,与传统的重叠社区识别算法相比,GWCR算法划分的社区的模块度较高。     

网络形式背景下的社区划分方法研究

网络社区划分是从社会网络中进行概念认知、模式学习的基础,也是网络背景下机器学习研究的热点问题.为了充分发挥形式概念和网络特征值的双重优势,基于网络形式背景研究网络社区划分问题.首先,将网络结构与节点属性信息相结合给出了网络节点中心度和中心势,使得网络形式背景的网络社区划分综合考虑了网络结构和节点内涵两方面的特征;其次,提出了网络形式背景的网络社区概念,该概念不仅给出了传统形式背景的形式概念,还包含了概念的网络特征值,可以描述该概念在网络中的平均重要度和平均重要度势差;然后,考虑到社会网络划分中多角色与网络有向性的特点,又将有向网络分为单角色网络和双角色网络,运用网络结构与节点属性信息相结合的方法提出了两种网络社区划分算法,并分析了算法的时间复杂度;最后,通过实例说明了上述网络社区划分算法的有效性.所得结论为网络数据挖掘和网络概念认知的进一步研究提供了参考.     

基于信息扩散概率的二分网络社区划分算法

二分网络是复杂网络的表现形式之一,二分网络单侧节点的社区划分对研究复杂网络具有重要的实际意义.基于信息在网络中的扩散概率和模块度思想,本文提出了一个针对二分网络的社区划分聚类算法(IPS算法).该算法通过模拟信息在网络中扩散的过程,利用各个节点的信息量在网络中扩散后,每个节点收到其他节点的信息量作为社区之间合并的依据,并引入二分网络模块度作为社区划分优劣判断的依据.最后算法在典型网络上测试结果表明,该算法不仅能够精确的识别二分网络社区个数,而且可以获得高质量的社区划分结果.     

一种新的在线社交网络社区发现算法

针对传统的社交网络社区发现算法时间复杂度较高的问题,提出了一种新的在线社交网络社区发现MICDA算法.运用凝聚思想并引入模块度增量的概念,按照杜区划分的标准自底向上的构建一个社交网络大社区,采用微博用户数据集和karate数据集上进行社区划分,并与传统的社区发现算法GN和FN进行对比分析.仿真结果表明,提出的社区发现算法MICDA要优于传统的GN(Girvan,Newman)和FN(Fast,Newman)算法,时间复杂度大大降低,且适用于大型社交网络的社区发现.     

基于孤立节点分离策略的改进鲁汶算法

鲁汶算法（LM）是基于模块度优化的复杂网络社区发现算法,有关模块度的现有研究中没有计算节点离开原属社区后模块度增益的方法。针对这一不足,基于模块度的定义和节点合并后模块度增益的计算方法,推导出了节点离开原属社区后模块度增益的计算方法,完善了该领域的理论研究。针对鲁汶算法对存储空间需求高的缺点,提出了基于孤立节点分离策略的改进鲁汶算法,该算法在每次迭代中将输入网络的孤立节点提前分离出去,只令其中的连通节点实际参与迭代过程,并在存储社区发现结果时将孤立节点和非孤立节点分开存储。基于真实网络的相关实验结果表明,采用孤立节点分离策略的改进方法,使算法对存储空间的需求减少了40%以上,并进一步缩短了算法的运行时间。因此,改进后的算法在处理真实网络时更具优势。     

模块度增量与局部模块度引导下的社区发现算法

社区结构是复杂网络的重要特性之一,基于层次聚类的社区发现算法很好地利用了模块度来挖掘网络中的社区结构,但其局限性也导致算法对社区结构复杂的网络划分不够准确、无法发现小于一定规模的社区。在层次聚类的基础上,提出引入局部模块度来弥补模块度在划分社区时的不足,避免可能出现的划分不合理情况。通过真实数据集和人工网络进行了验证,实验结果证明,该算法具有可行性与有效性。     

复杂网络重叠社区结构发现的演化算法研究

复杂网络重叠社区结构的划分已成为复杂网络研究的一个热点,目前已提出了很多关于社区结构发现的算法。提出了一种基于个体从众的演化算法ICEA,基本思想是由节点邻居组成的个体依概率进行从众和变异操作,用较短时间找到最优(或拟最优)模块度的社区划分,社区结构确定后利用邻居投票机制NV发现网络的重叠节点,完成重叠社区的划分。在真实网络的实验结果表明,此算法的使用时间和划分结果都优于典型算法。     

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

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

基于模块度增量的二分网络社区挖掘算法

针对二分网络的社区挖掘问题,提出了一种基于模块度增量的二分网络社区挖掘算法。该算法假设每个顶点独自构成一个社区,并具有自己的标号。其中,一部分顶点将自己的标号复制并传递到另一部分中的某个顶点上,使之与其位于同一个社区;另一部分的顶点实施同样的操作。如此反复迭代,直至收敛。标号传播时,选择模块度增量最大的边进行传送,使整体模块度不断提高。在真实数据集上进行的测试表明,所提算法能对二分网络进行高质量的社区划分。     

A novel multiobjective particle swarm optimization algorithm for signed network community detection

Signed graphs or networks are effective models for analyzing complex social systems. Community detection from signed networks has received enormous attention from diverse fields. In this paper, the signed network community detection problem is addressed from the viewpoint of evolutionary computation. A multiobjective optimization model based on link density is newly proposed for the community detection problem. A novel multiobjective particle swarm optimization algorithm is put forward to solve the proposed optimization model. Each single run of the proposed algorithm can produce a set of evenly distributed Pareto solutions each of which represents a network community structure. To check the performance of the proposed algorithm, extensive experiments on synthetic and real-world signed networks are carried out. Comparisons against several state-of-the-art approaches for signed network community detection are carried out. The experiments demonstrate that the proposed optimization model and the algorithm are promising for community detection from signed networks.     

动态社区发现方法研究综述

随着社交媒体多样性的增加,实时分析社交网络的需求不断增大,动态社区发现的研究受到了广泛的关注。已有的社区发现综述多是侧重静态社区发现,以及相关方法的探讨,无法进行网络演化分析,此外社区的实体数据往往具有交叉更替性和时序性,因此对动态社区发现的研究现状进行分析和综述。首先,基于复杂网络的研究背景,提出了通用的动态社区发现研究框架;接着,形式化表示动态社区发现的相关定义,并从网络层面和节点层面对动态社区演化进行详细分析;然后,根据架构和技术的不同,对动态社区发现方法进行归纳分类,并结合常用数据集和评价指标对经典静态社区发现算法进行定性和定量分析;最后,介绍了社区发现的典型应用场景,探讨了当前动态社区发现研究面临的主要挑战,针对性地提出了相关解决方案,为动态社区发现研究领域勾画出较为清晰和全面的研究方向。     

基于社团强度系数的社团结构发现算法

社团结构是复杂网络普遍存在的拓扑特性之一.为了将复杂网络中的社团结构有效地划分出来,在对强社团定义的基础上,引入社团强度系数的概念,提出了一种基于社团强度系数的社团结构发现算法.该算法具有较低的时间复杂度,通过不断寻找网络最大度数的节点及其邻居节点,计算其社团强度系数来衡量社团如何划分.主要针对Zachary网络和Dolphin网络等进行了仿真实验,结果表明该算法具有较高的社团划分准确度、较好的敏感性和良好的可扩展性,充分验证了其可行性和有效性.     

复杂网络重叠社团检测算法研究综述

社团结构是复杂网络的一项基本特性,对复杂网络中社团结构特别是重叠社团结构的检测,是复杂网络理论研究的一项重要且充满挑战的课题.对当前常用的重叠社团检测算法进行了分析和归纳,阐述每类算法特点,并介绍用于评价算法性能的一些基准图,对复杂网络重叠社团检测领域未来的研究方向提出了一些思考和建议.     

基于社区的关键节点挖掘算法

在对大型网络进行关键节点挖掘方面,传统方法效率低下。针对这一缺陷,提出了一种基于社区的关键节点挖掘算法,首先对社区发现算法进行改进,然后提出基于节点频度中心度的挖掘算法。实验结果表明,新算法对社区进行关键节点挖掘时,不仅挖掘的影响度得到保证,而且效率显著提高。     

基于节点向量表达的复杂网络社团划分算法

社团结构划分对复杂网络研究在理论和实践上都非常重要.借鉴分布式词向量理论,提出一种基于节点向量表达的复杂网络社团划分方法（CDNEV）.为了构建网络节点的分布式向量,提出启发式随机游走模型.利用节点启发式随机游走得到的节点序列作为上下文,采用SkipGram模型学习节点的分布式向量.选择局部度中心节点作为K-Means算法的聚类中心点,然后用K-Means算法进行聚类,最终得到社团结构.在真实和模拟两种网络上做了丰富的实验,与主流的全局社团划分算法和局部社团划分算法作了比较.在真实网络上CDNEV算法的F1指标比其他算法平均提高19%;在模拟网络上,F1指标则可以提高15%.实验结果表明,相对其他算法,CDNEV算法的精度和效率都较高.     

基于信息瓶颈的社区发现

该文提出一种映射方法,把单部网络变换成二部图网络.针对得到的二部图网络,在信息论的框架下,提出了一种基于信息瓶颈的社区发现方法.该方法通过寻找网络的最优压缩表示来发现网络的社区结构,最优压缩表示尽可能多地保留原始网络的拓扑特征.在真实数据集和计算机产生的数据集上的实验表明,该方法能够有效地发现网络的社区结构.另外,对于有向网络的社区发现,现有方法忽略有向网络中边的方向而作为无向网络来处理,损失了有向的网络的方向信息,文中提出的社区发现方法能够很好地解决这一问题,并能从有向网络中挖掘出一些现有方法无法发现的知识,这一特点使得该文的方法比现有方法更适用于解决像WWW这样的有向网络.同时,真实世界的许多网络本身就是二部图网络,相对于现有的社区发现方法,文中的方法可以直接应用于这类网络.     

基于模糊神经网络的火灾探测系统研究

为降低火灾报警误报、漏报频率,根据火灾探测特点,提出了基于模糊神经网络的火灾探测系统设计方案,介绍了基于模糊神经网络的火灾探测系统组成、模糊神经网络的设计与应用等。该系统可对传感器探测到的信息进行智能化处理,明显提高了火灾探测的灵活性和准确性。仿真结果证明了该方法的可行性。     

网络社区动态角色挖掘算法研究*

传统的社区挖掘以社区为单位,忽略了社区内部成员的性质和地位。为了提高社区挖掘的精度,为个性化推荐提供一个优化的基础平台,基于优先情节和增长定律,提出了一种新颖的动态角色挖掘算法。首先根据节点的度数分布逆向推导社会网络的形成演化机制,构造网络时间轴;然后根据时间轴逐步向网络中添加新节点,同时进行社区挖掘和角色划分。在人工网络和真实世界网络上进行了多次测试,并与G-N算法进行了比较,取得了较好的结果。实验证明,应用动态角色挖掘算法得到的社区都是强连通社区,具有较高的准确性和实用价值。     

基于标签传播的语义重叠社区发现算法

语义社会网络(Semantic social network, SSN)是一种由信息节点及链接关系构成的新型复杂网络, 为此以节点邻接关系为挖掘对象的传统社会网络社区发现算法无法有效处理语义社会网络重叠社区发现问题. 由此提出标签传播的语义重叠社区发现算法, 该算法以标签传播算法(Latent Dirichlet allocation, LDA)模型为语义信息模型, 利用Gibbs取样法建立节点语义信息到语义空间的量化映射; 提出可度量节点间相似性的主成分 (Semantic coherent neighborhood propinquity, SCNP)模型和语义影响力(Semantic impact, SI)模型; 以SCNP作为标签传播的权重, 以SI 作为截断值的参数, 提出一种改进的Semantic-LPA (Semantic label propagation algorithm)算法; 提出可度量语义社区发现结果的语义模块度模型, 并通过实验分析, 验证了算法及语义模块度模型的有效性及可行性.