关键词： 多层网络   社团检测   交通流   供需关系  

摘要： 海量的城市交通流数据已经可以被广泛获取,发现不同类型交通流空间交互结构间的关系以及交通流与交通网络间的联系对于优化城市交通设计、缓解城市交通拥堵具有重要价值。为此,采用北京市六环以内区域2016年5月9日与5月15日的公交刷卡、出租车轨迹、公交线路数据,借助单层与多层社团检测方法,探索:①不同交通流空间分布模式间的联系;②公交服务与公交乘客之间的供需关系。研究发现:①从公交刷卡与出租车轨迹数据中发现的社团结构具有明显差异,表明2种不同交通流反映城市空间交互的不同作用;②北京市公交线路社团结构与公交出行社团结构相似性较高,但也存在局部的差异,可以反映公共交通供需不平衡模式。研究结论可为城市交通设计优化提供一定的参考。

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

摘要： 以重叠社团检测算法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应用于“用户-应用”的移动漫游网络模型中,划分出了以携程旅行、高德地图、滴滴出行等为基础应用的社团结构,而这些社团划分结果可为设计个性化套餐业务提供策略参考信息。

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

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

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

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

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

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

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

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

关键词： 复杂网络   聚类同步   牵制控制   社团检测   介数中心性   Ricci曲率   图扩散  

摘要： 在复杂网络研究中,网络的同步性状态和社团检测是两个十分重要的问题。同步性研究关注网络结构和功能之间的关系。社团检测是指将网络中的节点划分为不同的社团,以便更好地理解网络结构和功能。对于现存的网络同步性研究,存在只是在非奇异网络上研究,研究的网络同步状态过于简单等问题。针对于社团检测研究,现存的算法存在依赖于统计学特征、在大型网络上检测效果不佳、算法鲁棒性低等问题。在部分领域中,同步性实际上可以结合社团检测算法进行研究,两者的理论可以有机的结合在一起,但是相关的工作很少。针对以上这些问题,本文主要做了以下工作: 在第三章中,基于自适应牵制控制策略研究了具有多链路和时变延迟的奇异复杂网络的聚类同步问题。针对奇异网络研究了网络的聚类同步问题,奇异网络的动力学方程相比非奇异网络会更为复杂,相关的同步性问题也更难处理,并且奇异网络上的结论可以相应的转化到非奇异网络上,这使得本章的结论更具有价值。在研究中,奇异网络被构建为两层模型,这可以更准确地揭示领导者-跟随者层之间的层级结构。本章运用牵制控制手段达成网络的同步,可以有效的节省控制开销,针对于非线性多链路时变时滞网络的研究则使得本章的研究结果更具有普适性和实际应用价值。 在第四章中,结合复杂网络的同步性研究和社团检测算法,提出了一种基于社团检测和介数中心性的复杂网络牵制控制手段。在控制过程中,首先使用GN算法识别网络中潜在的社团结构,然后从每个社团中挑选介数中心性高的节点作为牵制控制的被控节点,并研究基于介数中心性重整化网络拓扑结构以加快网络系统响应的方法。实验证明从社团中筛选被控节点相比于随机选择可以有效的提高控制响应的速度,基于牵制控制的控制协议可以本质上地减少能量消耗和控制器的开销。而基于介数中心性优化网络的权值连接结构,可以使得网络系统具有更快的响应速度,更快的达成聚类同步。 在第五章中,研究了基于Ricci曲率的社团检测算法。通过计算节点之间的离散Ricci曲率,经Ricci流过程不断迭代收敛识别出网络中的社团结构。在Ricci曲率的基础上,本章还提出通过引入图扩散过程来改变Ricci曲率中节点的度量,可以令算法在大型网络上具有更高的准确率,在网络缺失节点时具有更高的鲁棒性。

关键词： 复杂网络   社团检测   重叠社团   马尔可夫链  

摘要： 现实世界中大量的系统都可以被视作复杂网络,社团检测作为复杂网络中的热点问题之一,在过去的几十年里引起了广泛关注并得到了大量研究,在各行各业里得到了广泛应用。虽然许多方法在这个问题上表现良好,但现实世界中的网络种类繁多,如果网络具有一些很复杂的特征,例如非常稀疏、社团结构不明显或社团结构重叠性太强,这些方法就会变得无能为力。 为了解决这些问题,本文研究了一种基于马尔可夫链的社团检测模型(Community Detection Model based on Markov Chain,CDMMC)。具体工作如下: (1)为了解决非重叠社团检测领域普遍存在的社团检测算法应用于稀疏网络以及社团结构不明显的网络上效果不佳的问题,本文将CDMMC应用到了非重叠社团检测领域提出了图重构(Graph Reconstruction Method,GRM)算法。在GRM算法中,通过四种基于马尔可夫链的特征提取方法来提取网络蕴含的结构化特征,从而得到一个概率特征矩阵,通过该矩阵利用GRM算法对新图进行进一步的重构,并用重构后的图代替原来的网络进行社团划分,最终提取这个新的网络的连通分量即可得到社团的划分,实现非重叠社团检测。最后可以利用Leiden算法对GRM算法进行局部优化,使整体社团检测算法的效果更加突出。在240个不同参数的人工网络数据集和6个不同的真实网络数据集上关于图重构(GRM)算法和带有Leiden优化的图重构(GRML)算法与其他8种经典的非重叠社团检测算法的对比实验证明了算法的有效性、准确性和优越性。实验表明,当网络较为稀疏时或社团结构不明显时,本算法与其他8种经典算法相比优势非常明显。 (2)为了解决重叠社团检测领域普遍存在的社团检测算法应用于强重叠网络上效果不佳的问题,将CDMMC应用到了重叠社团检测领域提出了图吸收(Graph Absorbing Method,GAM)算法。GAM算法在得到概率特征矩阵后,首先会初始化一个以节点重要性排序的序列,然后把该序列作为吸收的种子节点利用概率特征来吸收其他节点,直到社团达到指定数量或者无法继续。对于每个没有被吸收的孤立节点,最终算法会将其归入与该节点最匹配的社团中。在人工和真实网络数据集上的实验表明,GAM在重叠社团检测领域优于其他的对比算法,特别是在社团结构重叠性更加强烈的数据集上。