关键词： 重叠社团   结构中心   互信息  

摘要： 图神经网络在学习节点表示中展现了其突出的能力,然而在社团检测方面,大多数图神经网络模型仍然使用K-means来定位社团中心,为了克服K-means不适用于高维空间下聚类的缺点,提出了联合图的全局和局部互信息的重叠社团检测算法(overlapping community detection algorithm using global and local mutual information of graph,overDGI),这是一种用于处理重叠社团检测问题的图神经网络。首先,采用最大化图互信息和社团互信息使得隶属于同一社团的节点间的向量表示距离更近、更接近社团中心;然后,设计了一个目标分布来帮助模型更好地解决重叠社团检测任务。综合实验表明,overDGI在重叠社团划分上的表现对比现有的几种基准算法都有很强的竞争力。

关键词： 三角形构成   社团检测   标签选择   综合影响力  

摘要： 以重叠社团检测算法COPRA作为基础,给出了一个结合节点重要性与节点影响力的重叠社团检测算法COPRANNI.首先,使用一种在三角形构成基础上的节点重要性,以此确定节点更新顺序.其次,使用Node2vec模型遍历网络生成节点序列,在此基础上利用Skip-gram模型获得节点的低维向量,然后通过余弦相似度量标准获取相似值.将该相似性和重要性融合确定的节点影响力引入到隶属系数中,进行标签传播,待稳定收敛后,最终发现重叠社团.通过在多个数据集上进行实验,结果表明:该论文提出的算法在重叠社团EQ质量指标上有较好表现.

关键词： COVID-19   人口流动   网络分析   社团检测   百度迁徙大数据  

摘要： 新冠疫情(COVID-19)对人口流动与城市网络产生了巨大影响,该文基于百度人口迁徙数据,利用多维度特征评价方法分析疫情暴发前后中国城市网络的空间关联特征变化,有助于重大卫生事件突发期间人口出行和迁徙模式认知以及疫情后的社会恢复。结果表明:①城市网络中重要性相对较高的城市面对疫情等突发状况冲击时的韧性比低位城市小,加权优势度最大起伏可达0.380,且城市位次恢复需要更多时间;②城市间形成以长江三角洲、珠江三角洲、成渝、京津冀4个城市群为核心顶点的“筝型”城市网络结构,核心城市群中的大规模疫情暴发会明显抑制整个网络的人口流动规模和密度,并且其部分城市职能会暂时被周边核心城市分担;③城市集群结构韧性大,在长时间序列上保持稳定,间断性疫情暴发不会明显改变城市群结构,城市群内部的优势城市会发生明显变化;④疫情暴发会降低全国人口的出行意愿,但在疫情暴发前后,各城市与其主要人口流动城市间仍能保持健康的联系。

关键词： 社团挖掘   社团划分   社团检测   复杂网络   移动漫游网络   节点相似性   节点可达性  

摘要： 为度量多关系节点相似性、挖掘具有多关系节点的社团结构,提出基于节点多关系的社团挖掘算法LSL-GN。首先基于节点相似性和节点可达性刻画具有多关系的节点相似性度量指标LHN-ISL;然后利用该指标重构目标网络的低密度模型,并结合GN(Girvan-Newman)算法完成社团划分。将LSL-GN算法与多个经典社团挖掘算法在模块度(Q)、标准化互信息(NMI)和调整兰德指数(ARI)上进行对比,结果显示LSL-GN算法在3个指标上均优于经典算法,说明它的社团划分质量相对较好。将LSL-GN应用于“用户-应用”的移动漫游网络模型中,划分出了以携程旅行、高德地图、滴滴出行等为基础应用的社团结构,而这些社团划分结果可为设计个性化套餐业务提供策略参考信息。

关键词： 复杂网络   社区检测   核心度   重叠社团  

摘要： 针对含有重叠节点的社团提出了新的检测算法—NCD算法。提出了节点核心度的概念,按照节点核心度的计算方法选取簇的初始中心点;提出差异性函数对重叠部分的节点进行识别;在中心点扩展原则的指导下,通过判断网络中节点之间可否构成三角模型对重叠社团进行检测。使用了NMI和模块度作为社团检测的指标,将NCD算法应用在3个真实网络数据集上进行实验,结果表明,NCD算法可以高效地检测到社团中的重叠节点,同时表明了该算法与其他算法对比具有明显的优越性。

关键词： 复杂网络   进化算法   目标优化   多目标进化算法   社团检测   鲁棒性优化  

摘要： 复杂网络作为现今科学研究中的一个热点学科,在过去20年里得到了巨大的发展.现实中大量的复杂的交互系统,比如互联网、交通运输网、神经网络等都可以抽象为复杂网络,以进行系统的分析和研究.进化算法作为优化工具应用于复杂网络的不同领域的各个任务中,如网络社团结构的检测任务、网络动力学中的鲁棒性优化任务、网络传播中关键节点的搜寻任务等.本文首先对复杂网络和进化算法相关的基础知识进行了全面的概述,重点讨论了复杂网络中目标优化的研究进展,针对不同任务对优化目标及其具体应用展开了详细介绍,同时,对算法的性能评价指标进行了概述.此外,本文通过一系列实验展示了单/多目标优化算法在复杂网络优化问题上的性能表现,以及部分目标之间的相关性关系.最后对复杂网络中优化问题未来的研究动向进行了展望,为今后研究人员开展进化计算和复杂网络相结合的相关研究提供一些思路.

关键词： 社团检测   节点内容   先验信息   随机块   非负矩阵分解  

摘要： 在复杂网络分析中,社团检测发挥着越来越重要的作用,而在实际应用中如何提高社团检测的性能仍是一个共同研究目标.由于网络节点中内容信息有助于社团识别,一些方法侧重于将网络拓扑和节点内容相结合,并且获得了不错效果.此外,也有些方法借用节点之间的拓扑相似度,以提升实现社团检测性能.鉴于此,我们提出了一个统一化方法,结合节点内容的半监督社团检测,简称SCDNC.在该方法中,我们不仅将链接增强应用于社团检测,而且实现了拓扑和内容有机融合.首先,我们运用随机模型来描述节点社团隶属度.其次,我们构建出一个刻画节点内容社团隶属度的随机块模型,节点社团隶属度作为节点内容的权重向量,以实现拓扑和内容结合.再次,我们利用网络中节点之间的拓扑相似度构建先验信息,即,使网络中节点与其最相似的邻居节点具有相同的隶属度分布.最后,使用非负矩阵分解的方法学习新模型的统一化参数.在带有真实标签的人工网络和真实网络上,我们对新方法与一些当前流行的社团检测方法进行了性能比较.实验结果显示,通过融合节点内容和先验信息强化的链接,新方法检测社团的性能取得了显著提升.

关键词： 社团检测   边重整化   随机游走   相似性   模块度  

摘要： 现实网络构造过程中,存在连接数据不完整甚至自相矛盾等问题,且现有的社团检测算法易出现丢失部分连接信息等现象,为此,提出一种基于边重整化方法的新社团检测算法。根据“节点间相似性越小则属于同一社团的概率也越小”原理,引入节点间随机游走的稳态概率来衡量节点之间的相似性,不断移除相似性最小的现存连边,并补充相似性最大的丢失连边,以保持网络总连接边数不变。最后通过实例验证了新社团检测算法的有效性。

关键词： 大规模   复杂网络   图重构   社团检测  

摘要： 对大型复杂网络进行高质量的社团检测通常依赖图的拓扑结构来划分节点集,然而现实世界的网络通常带有嘈杂且与集群无关的连接,这些链接可能会导致模型将来自不同集群的节点划分在一起。为此,提出了基于图重构的社团检测算法(graph reconstruction based community detection,GRCD),该方法能够处理大规模复杂网络的社团检测。首先,删除社团之间的相互连接的边来重新构建原始图的社团结构;然后,将网络视为一个社交系统,旨在以更直观的方式揭示社团;提出了一种高效的社团检测策略,即基于话语权的社团组织生成策略;最后,在不同规模数据集上进行实验。实验结果表明,GRCD算法不仅能够处理大规模网络,而且在保持较高稳定性的同时,其社团划分的质量对比现有的几种基准算法都有很强的竞争力。

关键词： 复杂网络   社团检测   自主计算   社团脆弱性   结构属性  

摘要： 社团是指复杂网络中连接紧密或者具有相似属性的节点集合,通常,社团之间连边稀疏,社团内部边连接紧密。社团是网络系统的重要结构属性,社团检测有助于挖掘网络中的关键信息及分析网络结构特征。因此,社团检测方法的研究具有重要的现实意义。同时,网络中社团的安全性也变得尤为重要,对社团的脆弱性进行评估能够及时发现网络中的脆弱环节,并有助于制定有效措施避免网络遭受大规模破坏。所以对社团的脆弱性分析的研究也是必不可少的。基于上述问题,本文提出了基于自主计算的社团检测方法和一种新的社团脆弱性分析方法,并以真实世界网络作为研究对象,通过大量的仿真实验验证了方法的有效性。本文主要工作内容及创新成果如下:(1)基于自主计算的社团检测方法研究本文提出了一种新的基于自主计算的社团检测方法(AOCCD)。该方法基于自主计算(Autonomy-oriented computing,以下简称为AOC)系统,主要包括两个阶段:检测和合并。在检测阶段,系统中的自治体各自挖掘其附属节点的局部社团,通过局部相似度指标和局部模块度增益指标来决定哪个节点可以加入局部社团。在合并阶段,所有自治体已完成其社团检测任务,将具有相同社团标签的节点进行合并,可完成对社团的初步划分。最后,使用本文提出的合并策略将一些“小社团”进行合并。实验表明,AOCCD算法对网络社团的划分更准确,得到的社团质量更高,并优于部分传统算法。(2)考虑社团内部与外部特征的社团脆弱性分析研究综合考虑社团的内部特征和外部特征,本文提出了一种新的社团脆弱性分析方法。社团内部特征有割点的平均度,连接密度和边与边之间的权重;外部特征有社团之间的连边数和连边权重。本文通过上述五个特征定义了社团脆弱性指标,将社团脆弱性量化,社团的脆弱性值越高,该社团就越脆弱。通过在真实世界网络中进行实验验证了本文提出的社团脆弱性评估方法的可行性。本文提出的方法可以对社团脆弱性进行准确评估,及时发现网络中的脆弱环节,避免网络网络遭受大规模破坏。