动态加权网络中的演化社区发现算法研究

在动态网络中发现社区结构是一个非常复杂而有意义的过程,可以更好地观察和分析网络的演化情况。针对动态加权网络中的社区发现问题,提出了一种结合历史网络社区结构的算法,叫做动态加权网络中的演化社区发现算法（ECDA）。该算法分为两步：结合历史社区和网络结构信息,计算当前时间跳的输入矩阵;然后通过该输入矩阵计算得到结合历史时间跳信息的社区划分结果。该算法有以下优点：可以自动发现动态加权网络中每个时间跳的社区结构;对网络结构的变化和社区结构的变化具有较高的敏锐性。在人工数据集和真实数据集中进行了实验,实验结果证明该算法可以有效地发现动态加权网络中的社区结构,与其他算法相比具有较好的竞争力。     

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

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

一种基于增量式谱聚类的动态社区自适应发现算法

针对当前复杂网络动态社区发现的热点问题, 提出一种面向静态网络社区发现的链接相关线性谱聚类算法, 并在此基础上提出一种基于增量式谱聚类的动态社区自适应发现算法. 动态社区发现算法引入归一化图形拉普拉斯矩阵呈现复杂网络节点之间的关 系,采用拉普拉斯本征映射将节点投影到k维欧式空间.为解决离群节点影响谱聚类的效果和启发式确定复杂网络社区数量的问题, 利用提出的链接相关线性谱聚类算法发现初始时间片的社区结构, 使发现社区的过程能够以较低的时间开销自适应地挖掘复杂网络社区结构. 此后, 对于后续相邻的时间片, 提出的增量式谱聚类算法以前一时间片聚类获得的社区特征为基础, 通过调整链接相关线性谱聚类算法实现对后一时间片的增量聚类, 以达到自适应地发现复杂网络动态社区的目的. 在多个数据集的实验表明, 提出的链接相关线性谱聚类算法能够有效地检测出复杂网络中的社区结构以及基于 增量式谱聚类的动态社区自适应发现算法能够有效地挖掘网络中动态社区的演化过程.     

复杂网络社区发现研究进展

近年来,随着现代网络通信和社会媒体等技术的飞速发展,复杂网络成为多学科交叉研究的热点之一,社区发现是复杂网络中的一个重要问题,对其进行研究具有重要的理论意义和应用价值。该问题吸引了多个学科领域的众多学者的关注,并且已有许多社区发现算法被提出。已有的社区发现综述多是侧重某一方向或特定领域展开,基于此,文中在之前工作的基础上,对国内外社区发现工作进行了深入调研,较全面地阐述了复杂网络社区发现的研究现状。首先,针对不同网络结构,给出社区发现的问题定义和主要的评价指标。然后,介绍了不同网络结构中的经典社区发现算法,包括同质网络中的全局社区发现、局部社区发现算法,异质网络中的二分网络、三分网络和多分网络中的社区发现,结合节点内容和连接结构的社区发现算法,以及动态网络中的社区发现和社区演化工作。最后,简要介绍了社区发现的典型应用,包括影响最大化、链路预测和情感分析领域的应用。此外,探讨了当前社区发现研究面临的主要挑战,试图为社区发现研究领域勾画一个较为清晰和全面的轮廓,为初学者提供指引。     

一种新型的层次化动态社区并行计算方法

文中提出了一种可并行分解的层次化动态社区发现算法D-SNCD(Dynamic Social Network CommunityDiscovery).D-SNCD算法充分利用复杂动态社会网络变化的局部性,对算法生成的层次化社区树HOT(Hierar-chical cOmmunity Tree)的分枝进行选择性更新.与传统的对动态社会网络直接采用快照方式进行社区发现相比,D-SNCD算法在效率上取得了明显的提高.由于D-SNCD是对已有的静态社区并行计算方法P-SNCD(ParallelSocial Network Community Discovery)的进一步扩展,因而D-SNCD保持着P-SNCD算法的高扩展性和高分辨率等优点.另外,D-SNCD算法对用户参数输入要求简单.严格的数学证明和充分的实验数据保证了整个算法的正确性和有效性.     

群智感知网络中基于社会关系的社区发现算法

群智感知应用主要通过社区划分进行任务分配,然而现有群智感知应用中社区发现算法缺乏对社会关系的量化以及划分社区的特征因子单一。针对这些问题,提出了一种基于多维社会关系特征的社区发现算法,通过计算移动节点间的最优生成树、节点合并因子、社区调整因子,对移动节点的社会关系进行具体量化,将节点合理划分成不同的社区。实验结果表明,与现有方法相比,该算法在不同的数据集中具有更好的动态适应性、有效性和预测准确性,其准确性平均达到97.3%,高于对比算法15.2%。     

基于谱聚类的社交网络动态社区发现算法

动态社区发现研究是社交网络分析（SNA）的重要研究领域。随着节点加入或离开社交网络，节点间的关系也随之建立或消失，进而影响着社区结构的变化。针对社交网络静态社区发现算法缺少必要的社区节点历史信息而导致的网络结构分析、聚类信息不足和计算开销过大的问题，基于社区网络演化事件的划分并根据主要社区事件的分析，提出一种基于谱聚类的动态社区发现算法（SC-DCDA）。首先，根据实验观察使用谱映射的方法将高维数据降维，并采用改进的模糊C-均值聚类（FCM）算法确定动态社交网络中的节点与待发现社区的关联度；其次，根据演化相似度矩阵分析社区结构。通过使用真实网络数据集以及模块度得分、轮廓系数等社区发现算法衡量指标，评估所提算法的效果。实验结果表明，SC-DCDA的计算开销相较于传统谱聚类降低了8.37%，在所有数据集上的平均模块度得分是0.49，其他衡量指标的定性分析结果也较好，验证了所提算法在信息交互、聚类效果和精确度上表现较好。     

基于联合矩阵分解的动态异质网络社区发现方法

动态网络的社区发现是目前复杂网络分析领域的重要研究内容,然而现有动态网络社区发现方法主要针对同质网络,当网络包含多种异质信息时,现有方法不再适用。针对这个问题,本文提出了一个基于联合矩阵分解的动态异质网络社区发现方法,首先计算动态异质网路中各个快照图的拓扑相似度矩阵和多关系相似度矩阵,其次利用时序联合非负矩阵分解方法,约束各个时刻快照图的社区划分,最后在真实网络数据集上的实验结果表明,该算法可以有效检测出动态异质网络中潜在的社区结构。     

基于协同过滤的Web服务动态社区发现算

针对现有社区发现算法挖掘结果精确度不高以及Web服务资源智能推荐质量较低的问题,在传统协同过滤算法的基础上,提出了基于节点相似性的动态社区发现算法。首先以连接节点最多的中心节点为起始网络社区,以社区贡献度为衡量指标不断形成多个全局贡献度饱和的社区;再使用重叠度计算将相似度高的社区进行合并,最后通过计算目标用户与社区中其他用户之间的动态相似度,将计算结果降序排列后构成邻近用户集,获得社区化推荐对象。实验结果表明,提出的社区发现算法对用户社会网络的社区分类与实际社区分类结果吻合,提高了社区挖掘的精确度,有助于实现高质量的社区化推荐。     

一种面向动态科研网络的社区检测算法

科研网络是一类动态变化的异构信息网络,科研网络上的社区检测能挖掘出学术主体的所属社区并发现蕴含于科研社区中的洞察.既有的社区检测算法忽略了科研网络的动态特征和科研主体间的特殊关系,未将科研社区内部的紧密程度和社区间的关系纳入社区检测算法中予以优化,对此提出了一种基于动态科研网络表示学习的社区检测算法DANE-CD.首先...     

社区挖掘技术研究

复杂网络分析已成为近年来的一个热点研究领域。如何快速有效地对复杂网络进行社区划分,并在社区划分的基础上找出网络中的重要节点有很强的现实意义。本文分析比较了近年来复杂网络分析中社区结构挖掘算法和社区节点等级排序算法的原理和特征,最后对复杂网络分析的发展进行了总结和展望。     

基于网络嵌入与局部合力的复杂网络社区划分算法

社区划分可以揭示复杂网络中的内在结构和行为动态特点,是当前的研究热点。文中提出了一种基于网络嵌入和局部合力的社区划分算法。该算法将网络的拓扑空间转化成欧氏空间,把网络节点转换成向量表示的数据点,首先基于重力模型和网络拓扑结构,提出局部合力和局部合力余弦中心性指标(Local Resultant Force Cosine Centrality,LFC),通过节点的LFC和节点间的距离来确定各个初始小社区的中心节点,然后将网络中其他的非中心节点划入与其最近的中心节点所在的初始小社区内,最后通过优化模块度的方法来合并初始小社区并找到最优的网络社区结构。在6个现实世界网络和可调参数人工网络上与6种知名社区划分方法进行比较,比较结果表明了新算法良好的社区划分的性能。     

社团挖掘和话题监控的互动模型研究

社团挖掘是Web信息挖掘领域的重要应用,而话题监控是文本信息研究领域的重要应用,目前这两种技术是各自独立的。为更好地应用于互联网形成的复杂社会网络,将这两种技术结合起来研究,发现了社团和话题之间的关系,创建了社团挖掘和话题监控的静态和动态互动模型,设计了社团挖掘、话题识别以及社团跟踪算法。     

可探测社区稳定结构的局部社区发现算法

社交网络的动态变化使社区发现的精确度面临更高挑战。目前提出的大部分算法都是以寻求模块度最优解来发现社区,但往往会忽略所发现的社区结构是否稳定。根据力学平衡原理即当一个物体所受内部力和外部力平衡的条件下可达稳定状态,因此基于点的稳定性机制,判断节点来自社区内部连边数量与来自外部社区连边数量的最大值是否保持平衡,提出一种可探测稳定结构的局部社区发现算法。网络的稳定性大小与社区的结构有很大的关系,因此将网络的稳定性作为一种新的评价社区结构优良的标准。通过在真实网络和人工集成网络上进行实验对比发现提出的算法的社区结构稳定度比其他算法高,同时能发现精确度高的社区。     

层次聚类社区发现算法的研究

概述了社区发现算法的研究现状; 介绍了因分析对象的不同而产生的四类社区发现方法：矩阵谱分析方法、层次聚类方法、基于边图思想的方法和基于极大团思想的方法。对其中性能最优的层次聚类方法进行了详细的综述, 并对其典型算法进行了分析比较。最后, 提出了社区发现算法可能的研究方向, 为今后的研究提供参考。     

Community Detection in Dynamic Social Networks Based on Multiobjective Immune Algorithm

Community structure is one of the most important properties in social networks,and community detection has received an enormous amount of attention in recent years.In dynamic networks,the communities may evolve over time so that pose more challenging tasks than in static ones.Community detection in dynamic networks is a problem which can naturally be formulated with two contradictory objectives and consequently be solved by multiobjective optimization algorithms.In this paper,a novel multiobjective immune algorithm is proposed to solve the community detection problem in dynamic networks.It employs the framework of nondominated neighbor immune algorithm to simultaneously optimize the modularity and normalized mutual information,which quantitatively measure the quality of the community partitions and temporal cost,respectively.The problem-specific knowledge is incorporated in genetic operators and local search to improve the effectiveness and efficiency of our method.Experimental studies based on four synthetic datasets and two real-world social networks demonstrate that our algorithm can not only find community structure and capture community evolution more accurately but also be more steadily than the state-of-the-art algorithms.     

一种有效的社会网络社区发现模型和算法

社会网络的社区发现存在划分效果较好的算法时间复杂度过高、现有快速划分算法划分质量不佳、缺乏表达和充分利用个体和链接属性信息的模型和机制等问题.针对这些问题,提出了一种边稳定系数模型和一种能表达个体间关系紧密度的完全信息图模型,在此基础上设计和实现了一种有效的社区发现算法.提出的完全信息图模型具有较高通用性,适用于需要融合个体和链接属性的社区发现算法.通过系列实验表明,所提出的以边稳定系数模型和完全信息图为基础的算法,对社会网络中的社区发现问题是有效的.算法不仅具有较快的速度,也能适用于带权与不带权的网络,得到的社区划分结果也具有较高的划分质量.