一种融合节点变化信息的动态社区发现方法

动态社区发现旨在检测动态复杂网络中蕴含的社区结构,对于揭示网络的功能及演化模式具有重要研究价值.由于相邻时刻网络的社区结构具有平滑性,前一时刻网络的社区划分信息可以用于监督当前时刻网络的社区划分过程,但已有方法均难以有效提取这些信息来提高动态社区发现性能.针对该问题,提出一种融合节点变化信息的动态社区发现方法(Semi-supervised Nonnegative Matrix Factorization combining Node Change Information,NCI-SeNMF).NCI-SeNMF首先采用k-core分析方法提取前一时刻社区网络的degeneracy-core,并选取degeneracy-core中的节点构造社区隶属先验信息,然后对相邻时刻网络的节点局部拓扑结构变化程度进行量化,并将其用于进一步修正社区隶属先验信息,最后通过半监督非负矩阵分解模型集成社区隶属先验信息进行动态社区发现.在多个人工合成动态网络和真实世界动态网络上进行大量对比实验,结果表明,NCI-SeNMF比现有动态社区发现方法在主要评价指标上至少提升了4.8%.

在线社会网络的动态社区发现及演化

在线社会网络研究中,动态隐含社区或群组结构的发现及演化探测是一个十分关键的核心问题,它对于在中观(Mesoscopic)视图观察在线社会网络隐结构特征、预测演化趋势、掌控网络势态、发现网络异常群体事件等具有重要意义.文中首先分析了动态社区发现和社区演化研究的关系,给出动态社区研究中关键挑战问题;然后根据问题背景的不同,从"同构社会网络的动态社区研究"和"异构社会网络的动态社区研究"两个方面进行国内外相关研究现状的阐述和分析,其中,在"同构社会网络的动态社区研究"中,根据评价方法的差异和关注问题的不同将当前相关研究分为基于时空独立评价、时空集成评价、统一评价和增量式算法4大类进行综述,同时对动态社区发现的重要应用——异常群体发现的研究进行介绍;最后对在线社会网络动态社区领域的难点和发展趋势进行分析和展望.

基于密度聚类的增量动态社区发现算法

现实世界中社交网络中的节点和边随时间动态增加或消失,导致网络中的社区结构也随之发生变化,因此,文中提出基于密度聚类的增量动态社区发现算法.首先,基于改进后的DBSCAN生成初始时刻社区.然后,提出边变化率指标,并结合余弦相似度指标确定相邻时刻邻居发生变化的节点及其邻居节点的社区归属调整.在进行社区归属度计算时,不仅考虑节点直接邻居的影响,还考虑间接邻居的影响.最后,通过迭代更新模块度增益进行社区合并,以减少噪声社区的干扰.在人工数据集和真实数据集上的实验表明,文中算法可以有效应对网络结构突变和增量计算累积误差带来的影响,具有较低的时间复杂度.

基于个体稳定度博弈的动态社区发现算法研究

在动态网络中发现社区结构是一个复杂而又有重要意义的课题。该文针对动态网络中的社区发现问题,提出一种基于个体稳定度的博弈论方法(PDG)。在该博弈方法中,网络中的每个节点都是一个独立个体。个体会根据网络中的其他个体的状态,使用最佳应对策略进行社区的选择。针对网络演化过程中的社区更新问题,该文提出了格局检测(Configuration checking)等优化策略,从而大大提高了演化网络的社区发现的效率。最后,在真实演化网络的实验中,与最新的静态和动态社区发现方法进行对比,验证了PDG方法的效率和效果。

在线社会网络的动态社区发现及其演化

分析了目前动态社区发现及其演化所存在的问题,提出了一种新的动态社区演化方法.该方法利用静态社区挖掘算法提取不同时间快照的每个社区,然后计算出相邻快照的社区之间的演化影响力,进一步分析连续快照中社区结构的发展演化过程.在新浪微博、网络测量Gnutella等大规模实验数据集上的验证,证明了该方法的有效性.此外,实验中还分析了社会网络中节点的出现和消失的频繁程度会影响社区稳定性以及社区结构的演化.

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

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

一种混合的动态社区发现算法

针对增量式动态社区发现算法存在的误差累积问题和计算复杂度受网络演化程度影响的问题,本文结合标签传播算法和模块度优化算法提出了一种混合的动态社区发现算法.该算法将网络的演变情况分为产生增量较多的剧烈演变和产生增量相对少的非剧烈演变2种情况.为了减少增量处理,对于剧烈演变,该方法将对应的网络快照看做一个完整网络,采用静态方法划分社区.对于非剧烈演变的情况,则采用增量的方式划分社区.在社区划分过程中,同时采用了基于模块度优化的Louvain算法和标签传播算法进行社区结构调整.在人工数据集和真实数据集上的实验验证了本算法的正确性和有效性.

基于拓扑势的增量式动态社区发现方法

为保证动态社区发现效率,提高动态社区划分结果的准确性,提出一种基于拓扑势的增量式动态社区发现方法。增量式方法以前一个时间片网络的社区划分结果为基础,动态调整网络变化部分的社区归属,其余部分的社区结构仍保持不变。传统增量式方法只考虑增量节点,实际上,增量节点的邻居节点也会受到影响而出现社区归属的变化。该方法考虑增量节点,依据拓扑势场理论,进一步计算增量节点影响范围内的邻居节点,重新判定这些节点的社区归属。在真实和人工网络上的实验结果表明,该算法扩大了传统增量更新的范围,在保证计算效率的基础上,有效提高了社区划分结果的准确性。

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

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

一种基于介数和时效性的动态社区发现算法

为了发现动态变化的社区结构,在分析了动态社区划分算法的研究现状基础上,提出一种基于时效性和介数的动态社区发现算法,对历史信息的时效性进行了计算,建立了综合有权网络,基于局部边介数进行社区划分,发现了稳定社区结构。实验表明了算法的有效性。

一种基于局部模块度的增量式动态社区发现算法

为更好地适应大规模社会网络数据的应用要求,提出一种基于局部模块度的增量式动态社区发现算法。把对起始时间的社会网络执行静态社区发现获得的社区结构和局部模块度作为增量分析的基础,把局部模块度作为优化的条件,使用四种原子操作,逐步演化社区结构。使用社区结构的局部信息,提高了算法的运行效率。避免了设定参数的条件,提高了算法的适应性。实验结果表明,该算法具有一定的实际应用价值。

动态属性网络的语义社区发现及演化分析方法

动态属性网络的语义社区发现及演化分析具有重要研究价值,其包含动态社区发现、社区语义解释及社区演化分析三个任务,但现有方法均难以同时实现.针对该问题,提出一种基于联合非负矩阵分解的方法DANNMF(NMF for Dynamic Attributed Networks).DAN-NMF可以统一集成网络拓扑结构信息、节点属性信息及社区演化平滑约束信息,并利用最大最小化优化框架推导相关因子矩阵的迭代更新规则,从而可以直接获得动态社区发现、社区语义解释及社区演化分析结果.在人工合成和真实的动态属性网络进行大量相关实验,结果表明DAN-NMF比最优的基准方法在准确性指标上至少提高了7.3%.此外,在真实动态属性网络上的相关数据分析结果也表明DAN-NMF能够有效地发现动态社区的演化模式,并提供丰富的社区语义解释.

改进离散蜉蝣算法的多目标动态网络社区发现

动态网络社区发现能检测出随时间不断变化的社区结构,其研究具有重要意义。为了有效地解决动态网络社区发现问题,将蜉蝣算法引入社区发现,提出了一种多目标离散蜉蝣算法的动态网络社区发现方法(MODMA)。首先,在初始化阶段结合基于种群的标签传播算法和标签扩散算法对蜉蝣种群进行初始化,有利于提高初始解的互补性和多样性;其次,将蜉蝣个体更新策略进行离散化,进一步充分搜索全局空间;然后,提出改进的交叉操作并结合两种变异策略,加快种群的进化速度;最后,对最优解进行基于边界点的局部搜索,避免算法陷入局部最优,提高寻优搜索能力和收敛能力。在算法求解过程中,使用非支配排序和拥挤度距离排序机制保留优质解。大量基于合成网络和真实网络的实验结果表明,MODMA算法与对比算法相比具有更高的求解精度。

新冠疫情科研合作网络的动态演化及其影响因素探析

基于WALKTRAP随机游走算法对科研合作网络进行社区划分,时间上通过建立时间指数随机图模型探究合作网络演化和动态演变影响机制,空间上通过建立空间误差模型探究国家科研合作的影响因素,研究结果显示:科研合作产出的重要社区主要围绕新冠疫情死亡因素、急性呼吸窘迫综合征、通风以及新冠疫情的治疗效果等展开研究;结构上,该社区呈不断发散的、稳进式增长的良性结构,但缺乏创新性和消融性;网络形态上,该社区从高稀疏的多维群集向高聚集的单一群集演变并伴随“小世界”网络特征;国家的科研合作关系具有空间溢出效应,科研产出水平、邻近国家的合作数量、隶属于同一机构作者及其学术成就对国家的科研合作关系均有显著正向影响。

基于专利主题演化的颠覆性技术识别研究——以类脑智能领域为例

【目的/意义】颠覆性技术具有隐蔽性和突变性,而技术主题在演化过程中会释放颠覆性趋势产生的早期信号,本文提出一种基于专利主题演化的颠覆性技术识别方法。【方法/过程】首先,基于S曲线法判断技术生命周期;其次,综合运用文本挖掘和社会网络分析方法识别技术主题的演化事件;最后,定义新主题出现、原主题趋热和多主题融合三类突变情况,用于识别具有颠覆性潜力的技术主题。【结果/结论】通过类脑智能领域专利实证,发现六个新出现主题、四个趋热型主题和六个融合型主题,通过专家判读,证明了所提方法的有效性,同时筛选出五项主题作为最终预测结果。【创新/局限】本文基于动态社区发现算法对技术主题的演化特征进行分析,进而基于主题突变性筛选颠覆性技术,但数据来源较为单一,将在未来研究中加以扩充。