基于局部模块度的社区层次结构发现方法

为了发现复杂网络中社区之间的层次关系,提出了一种基于局部模块度的社区层次结构发现方法。文章方法克服了多分辨率方法无法给出整个网络的层次划分以及无法直接定位造成社区层次变化的分辨率等方面不足,选取网络中的大度数节点基于R公式进行社区层次结构探测,根据局部模块度值变化过程中产生的极大值和极小值定义了社区层次区分度来判断是否到达层次边界。并对网络进行裁剪,从不同的大度数节点出发来发现网络中的全部层次结构。在经典数据集和人工生成网络上进行了实验,并与现有算法进行比较。实验结果证明章算法的有效性。     

基于结构相似度的多尺度局部社区发现算法

社会网络规模巨大且结构动态变化给传统社区发现算法带来了巨大挑战,局部社区算法通过种子节点进行扩展得到局部社区,较好解决了这些问题。结合节点结构相似度在传统社区定义的基础上提出了一种新的社区定义,在该定义基础上引入尺度因子并定义了结构模块度,基于该模块度提出了一种多尺度局部社区发现算法,并改进该算法使之应用到局部重叠社区发现。通过实验选择效果较好的节点结构相似度,在真实网络中和其他局部社区发现算法进行对比实验,结果表明该算法具有较好的性能。     

密度峰值聚类的自适应社区发现算法

为减少社区发现算法中参数的选择对社区划分的影响,同时使算法能够自适应地进行社区划分,本文提出一种基于核密度估计的密度峰值聚类的社区发现算法KDED.首先,定义一种基于信任度的距离度量,将社交网络中的用户关系量化为距离矩阵,使用矩阵元素的大小度量用户关系的紧密程度;然后对距离矩阵进行核密度估计,统计各个节点在网络中的影响大小,结合热扩散模型改进计算流程,使其自适应不同规模的数据集以提高计算精度;结合密度峰值聚类原理和社区属性确定社区中心节点后,可根据节点间的距离得到社区内部层次结构和社区外部的自然结构;最后将剩余节点按距离分配到相应的社区当中以完成社区划分.仿真结果表明:通过可视化软件可观察到,通过KDED算法得到的社区划分结果具有清晰的自然结构和内部层次结构;随着社区规模的提升以及划分难度增加,KDED算法具有出色的稳定性;在真实数据集以及LFR基准网络上均得到较为接近真实划分结果的社区划分,自适应性良好,验证算法的可行性与有效性.     

一种基于非对称三角形割的重叠社区发现算法

发现由相似功能的个体所形成的社区结构是复杂网络分析的重要任务之一. 提出一种基于非对称三角形割的重叠社区发现算法,首先根据社区内三角形连接情况对社区质量进行评价,并根据节点与社区的三角形连接定义了节点对社区的归属度和连接强度. 考虑到网络不同部分连接密度的差异,在将节点从社区中移除或加入社区的过程中,为每个节点分别设置了不同的移除阈值和扩展阈值,以提高社区发现质量. 将每个节点与其邻居节点组成初始社区,将归属度低于移除阈值的边缘节点从社区中移除,将连接强度高于扩展阈值的外围节点加入社区,社区节点移除和扩展阶段迭代进行直至社区结构趋于稳定,最后去掉重叠率过高的社区得到最终结果. 在7个带社区标签的网络上将所提算法与其他7个经典重叠社区检测算法进行比较,通过重叠标准互信息和F₁指标进行评价,结果表明所提算法可以较好地发现不同规模网络中的社区结构.     

一种基于完全子图与标签传播的重叠社区检测算法

提出了一种基于完全子图和标签传播的重叠社区检测ＣＬＰＯＡ算法。该算法首先搜寻完全子图,并为每个子图分配唯一标签,实现快速标签预处理;然后根据每个节点的邻接节点标签来更新该节点的标签,同时提出接触频数优化标签选择策略降低标签随机传播概率;最后,通过网络标签分布情况进行社区划分。选取两个小规模标准数据集和两个大规模网络数据集进行实验,结果表明ＣＬＰＯＡ算法能保持和ＣＯＰＲＡ算法相同社区划分质量,同时具有更好的算法稳定性和时间性能。     

多点种子预划分的二阶段社区发现算法

社区发现是在线社交网络研究领域中的重要内容,基于种子扩张的社区发现算法具有时间复杂度低、识别精度高以及不受社区形态限制等特点,近年来在网络局部社区发现任务中得到了广泛的应用.然而,该方法在种子选取时没有考虑种子之间的关联性,因此识别出的社区结构个数较多、结构松散.针对这一问题,提出一种基于多点种子预划分的二阶段社区发现...     

基于点距离和密度峰值聚类的社区发现方法

在复杂网络中节点相似度度量以及密度峰值聚类算法的基础上,提出了一种基于点距离和密度峰值聚类的社区发现方法。首先,提出了基于节点相似度和节点间最短距离的节点距离度量。然后,应用密度峰值聚类方法探究网络中的社区结构,密度峰值聚类算法不仅能够检测出各个社区中心并进行相应的社区扩展,而且能够避免参数选择过程。最后,通过与经典算法在真实数据集和人工合成数据集上的比较实验,充分验证了本文方法的可行性和有效性。     

基于遗传算法的复杂网络社区结构探测

对于复杂网络社区结构的探测问题在多个应用领域引起了广泛关注。本文基于遗传算法提出了一种新的社区探测算法,该算法通过最大化网络模块度以探求最好的社区划分结果。本文采用字符串编码进行基因表示。在初始化种群时,通过将一部分节点的社区标识符传递给它的邻居节点保证了算法的收敛性,并且消除了不必要的迭代。对于交叉算子和变异算子也进行了优化,将单向交叉引入到交叉算子中,并在变异过程中保证了变异节点的连接有效性。将本算法与两种算法通过真实世界的复杂网络进行实验比较,实验结果表明,改进后的算法可以有效地应用于社区结构探测。     

一种融合社区结构信息的网络表示学习算法

为研究社区结构对网络表示学习的影响,提出了一种新颖的融合社区结构信息的网络表示学习算法（CINE）。通过借鉴模块度思想,将社区结构吸收到基于矩阵分解的模型中以保留网络内部的社区结构;设计一个整体的目标函数,在捕获社区结构信息的同时也融合了节点间的1阶2阶邻近性信息和节点的属性信息,最终得到包含原始网络中3类信息的节点表示;采用Cora、Citeseer和Wiki等3个公开网络数据集验证CINE在节点分类、链接预测和可视化任务中的表现。结果表明：在3个数据集的分类任务中,CINE的Micro-F1分数分别达到了0.900 2、0.840 2、0.761 9,优于所有对比算法;在Cora数据集的链路预测任务中,CINE的AUROC得分比Node2vec、DeepWalk和TADW等算法分别提高了1.165、1.144和1.059倍。说明CINE在保留网络的结构和属性信息的基础上,捕获了社区结构信息,使得所学节点表示可以更好地执行后续的网络分析任务。     

基于模体的模块度优化高阶社区检测算法

为提升现有高阶社区检测算法的性能，提出一种基于模体的模块度优化高阶社区检测算法。通过量化网络模体数量为节点间权重，将高阶基于模体的社区检测转化为低阶基于边的加权网络社区检测，并构造为加权模块度优化问题求解。为保证加权模块度优化性能以获得逼近全局最优的高阶社区划分，一方面优化策略采用典型的生物启发式算法；另一方面综合利用网络低阶和高阶拓扑结构信息，通过节点邻域社区修正操作和局部搜索操作，进一步提升社区划分质量并防止算法陷入局部最优。在人工合成和真实世界网络上的实验表明，利用模体高阶结构信息有助于提升复杂网络社区的检测性能，尤其是在社区结构较为模糊的情况下。该算法能够有效实现基于模体的高阶社区检测，与现有基于模体的典型方法相比在精确性和质量性上表现出一定优势，有助于加深对网络高阶结构及功能特性的理解。     

基于节点尺度特征的重叠社区检测算法

针对社会网络中重叠社区检测问题,在节点尺度特征下量化社区结构,用这些特性更易界定社区划分。利用合理假设来量化节点尺度的期望值,基于节点描述符集和谱算法建立算法模型,从而提出一种重叠社区检测算法。该方法允许节点同时属于多个社区,在社区重叠时同样可行。通过计算验证,算法对于整体边缘密度都有效。在2类网络中实验的结果表明,该算法在重叠社区检测中性能稳定、准确性高,能适用于目标特定的社区概念。     

基于节点聚类系数的网络社区结构发现

研究了节点聚类系数与网络社区结构之间的关系.直接使用节点聚类系数不易刻画社区子图的高聚集特性,定义了一些基于节点聚类系数的社区度量,据此识别网络中的社区.首先,给出了基于聚类系数增大的社区间边判定规则,简称CCE规则;然后,利用CCE规则引出相似度矩阵,即网络密度矩阵;最后,通过网络密度矩阵来构造Laplacian矩阵,并进一步推导出通过计算Laplacian矩阵的特征值以及特征向量来实现社区结构划分的算法.三个真实网络数据的实验结果表明,算法不仅获得了令人满意的划分结果,而且还提高了算法的时间效率.     

一种基于节点相关度的无线传感器网络分簇算法

提出了一种基于节点相关度的无线传感器网络分簇算法。该算法根据接收信号强度、节点剩余能量和网络连通度选取簇头节点,根据节点相关度确定簇内成员。分析与仿真结果表明,与经典的LEACH算法相比,该算法选出的簇头分布更均匀,并提高了簇内负载平衡程度,延长了网络生存时间。     

基于迭代K-shell和改进信息熵的节点重要性排序算法

复杂网络中对节点重要性排序算法的研究具有重要的现实意义。传统的K-shell算法排序结果分辨率不高,根据节点信息熵的排序算法时间复杂度又过高。针对这一问题,提出基于迭代K-shell和改进信息熵的节点重要性排序算法。首先,通过分析K-shell分解过程中的迭代信息得到节点在网络中的全局信息;其次,提出改进的节点信息熵来得到节点的局部信息;最后,综合节点的全局和局部信息对节点重要性进行排序。通过将该算法在4个真实数据集上与其他6个算法进行实验,该算法与现有方法相比排序结果的分辨率更高、节点信息传播能力更强且时间复杂较低,更适用于大规模网络。     

基于多中心性加权的Ad hoc网络连通支配集算法

给出一种基于网络中心性加权的连通支配集生成算法,以改善Ad hoc网络最小连通支配集算法的负载均衡性。根据特征矢量中心性、度中心性和紧密中心性在描述网络节点重要性方面的功能差异,以加权方式对各中心性进行融合,借此选取网络关键节点作为支配集节点,进而以其一跳范围内连通性较好的节点为支配邻居,构建全网连通支配集,并添加合适的连接节点来维护网络连通性。针对随机构建的网络拓扑图,仿真结果显示,所给算法可有效均衡网络负载,延长网络生命周期。     

基于密度峰值的重叠社区发现算法

根据基于快速搜索和发现密度峰值的聚类方法的思想,提出了基于密度峰值的重叠社区发现算法。首先定义新的距离矩阵算法,克服了邻接矩阵元素为整数的缺陷。然后用概率形式刻画每个节点属于不同类别的可能性,从而实现了重叠社区的划分。基于真实网络的实验结果验证了本文算法的可行性和有效性。     

结合概率矩阵的改进谱聚类社区发现算法

针对目前谱聚类算法的相似图包含较多错误社区信息的问题,引入了概率矩阵的概念,提出了一种改进的谱聚类社区发现算法。该算法首先利用马尔可夫过程计算节点间的转移概率,并基于转移概率构建复杂网络的概率矩阵;然后以均值概率矩阵重新构造相似图;最后通过优化归一化切割函数实现社区划分。采用人工网络和现实网络与其他典型算法进行对比实验,实验结果表明,该算法能够更加精准地划分社区,具有更加良好的聚类性能。     

校园移动社交网络中基于种子的数据分发算法

为了研究如何利用节点间间歇性连接传输数据,提出了校园移动社交网络中基于种子的数据分发算法,其主要思想是为每一个社区选择一个种子节点,并利用种子节点来进行数据分发.仿真实验表明,与著名的Epidemic、PS和SGBR算法相比,该算法可明显地降低网络开销,同时接近Epidemic算法达到的最大传递率.     

基于传播影响力的重叠社区划分算法

在研究经典标签传播算法的基础上,提出了一种基于传播影响力的重叠社区划分算法COPRA-PI,可用于挖掘加权网络中的社区结构。该算法在COPRA算法的基础上从节点影响力、边影响力、历史标签影响力3个方面综合考虑传播影响力;同时针对COPRA算法中每个节点在每次迭代过程中均具有相同的最大标签数,且该最大标签数目需手动设置等不足,该算法中设计了一个自适应的最大标签数。实验结果表明,COPRA-PI算法在经典的数据集上对比现有经典算法更能挖掘出高质量的社区结构且收敛速度较快。     

基于环路紧密度的复杂网络社区挖掘方法

提出了一种基于环路紧密度的复杂网络社区挖掘算法(LTA):首先提出一种快速发现网络环路和计算其紧密值的算法,然后根据环路紧密值将网络聚类,再次揭示网络环路与社区结构的联系。并使用人工合成网络和真实网络数据集对LTA进行了验证,实验结果证明了LTA对复杂网络社区挖掘问题的有效性和高效性。