基于边重整化方法的新社团检测算法

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

结合网络拓扑与节点内容的统一化半监督社团检测方法

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

融合节点重要性与影响力的重叠社团检测算法

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

基于谱聚类的二分网络社团检测算法

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

图重构下大规模网络的社团检测算法

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

基于社团检测算法的二进制程序模块化方法

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

电力通信网的多层网络社团检测

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

复杂网络重叠社团检测算法研究综述

社团结构是复杂网络的一项基本特性,对复杂网络中社团结构特别是重叠社团结构的检测,是复杂网络理论研究的一项重要且充满挑战的课题。对当前常用的重叠社团检测算法进行了分析和归纳,阐述每类算法特点,并介绍用于评价算法性能的一些基准图,对复杂网络重叠社团检测领域未来的研究方向提出了一些思考和建议。

基于联合矩阵分解的节点多属性网络社团检测

发现复杂网络中的社团结构在社会网络、生物组织网络和在线网络等复杂网络中具备十分重要的意义.针对社交媒体网络的社团检测通常需要利用两种信息源:网络拓扑结构特征和节点属性特征,丰富的节点内容属性信息为社团检测的增加了灵活性和挑战.传统方法是要么仅针对这两者信息之一进行单独挖掘,或者将两者信息得到的社团结果进行线性叠加判决,不能有效进行信息源的融合.本文将节点的多维属性特征作为社团划分的一种有效协同学习项进行研究,将两者信息源进行融合分析,提出了一种基于联合矩阵分解的节点多属性网络社团检测算法CDJMF,提高了社团检测的有效性和鲁棒性.实验表明,本文所提的方法能够有效利用节点的属性信息指导社团检测,具备更高的社团划分质量.

基于非负矩阵分解的半监督动态社团检测

如何有效融合不同时刻的网络结构信息,是影响复杂网络中动态社团检测算法检测性能的关键和难点。基于此,提出了一种基于非负矩阵分解的半监督动态社团检测方法 SDCD-NMF,该方法首先有效提取了历史时刻所包含的稳定结构单元,然后将其作为正则化监督项,指导当前时刻的网络社团检测。在真实网络数据集上的实验表明,所提方法与已有方法相比具备更高的社团划分质量,更有利于探索网络的演变与发展规律。

基于交互行为和连接分析的社交网络社团检测

社交网络的迅猛发展极大地方便了人们的日常生活、工作和学习,但也带来了大量复杂的交互行为和连接模式。如何有效地综合分析网络中的交互信息和网络节点之间存在的连接信息,进而完成高效的社团检测,是在当前网络多维属性的复杂背景下进行网络分析所面临的关键难题。基于此,从有效融合两类不同的异质信息研究出发,提出了一种基于交互行为和连接分析的社交网络社团检测(CDUILS)方法。该方法基于两类信息能够从不同的角度反映网络同一个社团归属的假设,采用联合非负矩阵分解架构,以迭代更新的方式,同时利用两类信息进行社团结果的获取。在真实网络数据集上的实验表明,与已有方法相比,所提方法能够有效融合两类信息进行社团检测,取得了更好的社团划分质量。

采用离散粒子群算法的复杂网络重叠社团检测

针对复杂网络重叠社团检测的问题,建立了衡量重叠社团划分优劣的评判函数,并基于该函数提出了一种采用混沌量子粒子群优化的复杂网络重叠社团检测算法。该算法采用量子编码,利用Logistic映射初始化粒子种群,并以粒子群速度改变方式更新转角的大小,以概率为1收敛。实验结果表明,所提算法具有较高的检测正确率,能更好地反映实际社团划分情况。

采用影响力节点集扩展的局部社团检测

针对规模化网络中局部社团检测存在的对初始节点位置敏感、拓扑信息难以有效利用问题,提出了一种采用影响力节点集扩展的社团检测(IN-LCD)方法。首先定义了节点的局部影响力指标,通过该指标计算并构造了源节点附近的影响力节点子集,然后从影响力节点子集开始,以迭代更新的方式,进行连续的社团扩张,最后通过节点和社团相似性指标计算,完成整个局部社团的获取。IN-LCD方法从有效利用节点局部信息出发,通过最具影响力节点集合进行社团扩展,有效克服了局部社团检测对初始节点位置敏感的问题。在真实和人工网络数据集上的实验表明,IN-LCD方法与已有的最佳局部社团检测方法相比,识别性能提升了5.3%,更能有效应用于局部信息出发的社团检测场景。

基于自然最近邻居的社团检测算法

针对传统社团检测算法无法判断网络中特殊节点和SCAN算法对于参数依赖性太大的缺点,提出了一种基于自然最近邻居概念的社团检测算法CD3N。算法利用自然最近邻居无参的特性,首先以结构相似度为基准,计算出网络节点的自然最近邻居,并依此构造小值最近邻域图;然后取邻域图中邻居数最多的节点为核心节点,根据可达关系,构造关于核心节点的社团;重复选取核心节点并构造社团的过程,直到没有可归入社团的节点。将算法应用到空手道俱乐部网络和海豚网络中,并与SCAN算法进行对比。实验结果表明,CD3N算法有效解决了参数敏感性问题,能够很好地进行社团检测。

基于单步添加团的重叠社团检测算法

基于局部扩充的重叠社团检测算法由单个节点或团出发,不断添加新的节点而获得最终的社团划分,但现有算法均为每次添加一个节点,没有充分考虑所添加节点的局部信息,从而影响了社团检测结果的准确性.为此,文中提出了一种基于单步添加团的重叠社团检测算法,该算法从一个团开始,通过不断添加此团邻居内适应度增值最大的团,使算法在局部扩充时不仅考虑了所添加节点与已有社团的连接紧密性,而且考虑了所添加节点内部的连接情况.在真实网络和计算机生成网络上的实验结果表明,与现有基于局部扩充的重叠社团检测算法相比,文中算法可以更准确地检测出复杂网络中的重叠社团.

基于网络社团检测的电信客户细分

现有的电信客户细分方法无法发现基于个体间交互关系形成的客户群体。为此,提出基于网络社团检测的电信客户细分模型。考虑网络加权方法对社团检测效果的影响,采用电信企业的通话明细记录构建不同的加权电话呼叫网络,并采用随机漫步模型算法建立基于通话关系的客户细分模型。在细分模型的基础上,结合客户基本信息分析社团的特征,使用网络节点度中心性识别社团中的中心客户。经电信运营商客户通话数据的分析表明,以通话总时长进行加权的网络得到的社团检测效果最佳,可以用于检测客户的关系圈,发现具有领导地位的中心客户,为电信企业客户挽留、精准营销等提供有效的决策支持。

基于稀疏子空间聚类的多层网络社团检测

现有的子空间聚类方法大多只适用于单层网络,或者仅对多层网络中每层的聚类结果简单地进行平均,未考虑每层网络中包含信息量不同的特点,致使聚类性能受限。针对该问题,提出一种面向多层网络的稀疏子空间聚类方法。将距离正则项和非负约束条件集成到稀疏子空间聚类框架中,从而在聚类时能够同时利用数据的全局信息和局部信息进行图学习。此外,通过引入稀疏约束使学习到的图具有更清晰的聚类结构,并设计迭代算法进行优化求解。在多个真实数据集上的实验结果表明,该方法能够挖掘网络不同层的互补信息,得到准确的一致性联合稀疏表示,有效提高社团聚类性能。

基于标签扩散的时序平滑社团检测算法

针对动态网络相邻网络快照社团检测结果差异较大、准确性不足的问题,文章在基于角色的标签扩散算法(role-based label propagation algorithm,RLPA)基础上,结合前一时刻社团结构信息以提高时序平滑性,根据时序结构差异性调整前序信息对当前社团结构的贡献权重,提出了一种基于角色的演化标签扩散算法(role-based evolutionary label propagation algorithm,RELPA)。在两类真实数据集上进行了对比实验,结果表明,该文算法能够准确有效地检测出动态网络中的社团结构。

一种面向动态网络的社团检测与演化分析方法

针对制约动态网络演化分析方法发展的社团演变模式挖掘问题,设计了基于指向性变异策略和变邻域搜索算法的静态社团检测算法与基于匹配度和社团生存周期的社团演化分析算法,并采用在时刻上运行静态社团检测算法、在时序上运行社团演化分析算法的策略,提出了一种面向动态网络的社团检测与演化分析方法。并用Zachary空手道俱乐部网络和Power网络验证了该方法的可行性和有效性。

基于双编码的重叠社团检测多目标优化方法

近年来,多目标进化方法已被广泛应用于重叠社团检测问题并取得了较好的社团划分性能.如何设计合适的个体编码以及进化策略是提高基于多目标进化重叠社团检测算法性能的重要因素.为此,本文设计了一种双编码表示方法对非重叠社团结构和重叠点分别进行编码,能够有效解码得到重叠社团结构.在双编码表示的基础上,本文提出了一种基于双编码的重叠社团检测多目标优化方法(DRMOEA).在DRMOEA中,为了获得好的初始个体并提高算法检测性能,本文提出了一种基于社团边界点的初始化策略.除此之外,针对双编码中的重叠点编码部分,本文提出了基于精英个体边界点的交叉策略,该策略利用社团边界信息引导种群向好的方向进化,从而有效提高了算法的检测性能.最后,在9个真实世界网络上的实验结果表明DRMOEA算法优于其他5个代表性重叠社团检测算法.