关键词： 社团检测   标签传播   三节点模体   密度峰值  

摘要： 复杂网络是对现实世界中复杂系统进行建模得到的一种网络结构,在城市交通网络、社交网络、生物学网络等领域中广泛存在。随着数字化时代的到来,这些复杂网络已成为研究信息传播和揭示网络结构的重要工具。通过识别网络中的社团结构,能够探知网络的拓扑特征,从而帮助优化网络布局和资源分配,社团检测为深入理解复杂网络的功能结构及动态行为提供了有力工具,成为当下研究的热点。 标签传播算法是一种简单高效的社团检测算法,无需先验知识且适用于大规模网络,同时时间复杂度近似线性。但其在节点更新顺序的选择和标签选择上存在随机性,导致算法划分的结果不稳定且准确性较低。针对以上问题,本文提出了两种改进算法,主要研究内容如下: (1)为了解决原始标签传播算法的随机性强这一问题,本文提出了一种基于三节点模体挖掘的标签传播算法。通过挖掘三节点模体来获取网络的高阶拓扑结构,并为避免高阶连接模式下出现孤立节点的情况,与原始低阶拓扑结构合并来重建网络。本文基于三节点模体定义了节点和连边权重的计算方式,并计算出节点间的连接强度。为克服标签选择阶段的随机性,该算法设计了新的标签更新规则,该规则结合了连边权重、节点连接强度以及邻居节点中标签出现的频率,并引入平衡因子以加大标签传播力度的差异性。同时在节点更新顺序的选择上,算法根据计算出的节点权重进行升序排列,解决了多次运行结果不一致的问题,提高了算法的稳定性。 (2)为了进一步识别出具体的社团中心,针对已知社团数量的网络,本文提出了一种基于密度峰值和最短路径的标签传播算法。本文结合密度峰值聚类思想,计算出节点的局部密度和相对距离,并利用切比雪夫不等式来选择出合适数量的社团中心节点。同时根据节点间的重叠相似度来计算节点间距离,从而使原始网络转化为加权网络,剩余节点根据其到不同社团中心节点的最短路径长度来进行标签传播。若出现多个候选标签,则选取其邻居节点中出现次数最多的标签。确定社团中心节点后,剩余节点只需迭代一次即可完成标签更新,提高了算法的效率,并且划分结果的准确性也得到了保障。 本文将基于三节点模体挖掘的标签传播算法以及基于密度峰值和最短路径的标签传播算法在9个真实网络数据集和42个不同规模不同复杂度的人工合成网络数据集上进行大量实验,并与其他六种经典社团检测算法进行对比,实验结果显示,本文算法能够准确地识别出复杂网络中的社团结构,尤其在大规模网络上表现出色,证明了算法改进策略的可行性和有效性,验证了算法的高效性和稳定性。

关键词： 通信工程   电力通信网   复杂网络理论   社团检测   K-means   多层网络  

摘要： 电力通信网作为电网的第二张实体网络,其可靠性以及稳定性是至关重要的,为了解决当前电力通信网部分拓扑结构鲁棒性较低问题,文章提出将基于复杂网络理论的社团检测应用到电力通信网中,可以检测出电力通信网的社团结构,通过消除社团结构,可以增强网络的鲁棒性以及稳定性。文章结合电力通信网的网络特征,提出一种多层电力通信网社团检测算法,利用业务相似度矩阵和节点相似度矩阵的拉普拉斯矩阵的特征值间隔,以及改进的K-means聚类算法实现电力通信网的社团检测,并通过与加权AA、GN等社团检测算法进行对比,实验结果表明,该文算法在模块度、准确率等指标均优于对比算法。

关键词： 二分网络   社团检测   模块度   奇异值分解  

摘要： 针对二分网络社团检测算法存在精度不高和丢失原始网络信息等问题,设计了一种新的融合奇异值分解的谱聚类(SVD-MS)算法.该方法是将Barber的二分网络模块度最大化问题映射到奇异值向量分解上,并结合启发式算法快速求解向量划分问题.在3个真实世界的网络中对比SVD-MS算法与7种算法的模块度,结果表明,在保留原始网络信息的情况下,SVD-MS算法能更有效地划分二分网络的社团结构.

关键词： 软件模块化   大规模   二进制程序   复杂网络   社团检测  

摘要： 对大规模二进制程序进行模块化时,现有方法存在较大时间开销,基于软件系统的“模块”与复杂网络的“社团结构”具有一定的特征相似性,研究使用社团检测算法进行二进制程序模块化。目前存在大量的社团检测算法,为此提出一个社团检测算法选择框架,该框架包括3个选择标准以及4个评估标准。根据选择标准进行算法过滤,选出3种具有代表性的社团检测算法,并使用评估标准来评估算法的模块化效果。通过多组对比试验,从中选择了一种效果较好的社团检测算法Louvain用于大规模二进制程序的模块化。实验表明,Louvain在效果方面优于目前最优的模块化形式概念分析(Formal Concept Analysis,FCA)方法,且实验平均耗时仅仅为FCA平均耗时的0.7%,极大提高了大规模二进制程序模化的效率。

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

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

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

摘要： 图神经网络在学习节点表示中展现了其突出的能力,然而在社团检测方面,大多数图神经网络模型仍然使用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应用于“用户-应用”的移动漫游网络模型中,划分出了以携程旅行、高德地图、滴滴出行等为基础应用的社团结构,而这些社团划分结果可为设计个性化套餐业务提供策略参考信息。

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

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