基于拓扑势的局部化重叠社区识别

针对传统社区识别算法中需要根据先验知识设定参数、 社区划分结果具有随机性及复杂度过高的问题, 提出一种基于拓扑势的局部化重叠社区识别算法. 该算法通过引入拓扑势计算节点的影响力, 利用节点间的局部相似性度量指标, 采用标签传播策略进行重叠结构的社区识别. 在真实网络及人工合成网络上与多种经典算法进行对比实验验证了算法的高效性.     

基于局部紧耦合结构的模块性优化社区检测方法

利用局部紧耦合结构提升社区检测的模块性优化质量.首先,定义了4类边缘紧耦合结构,并提出了一种具有线性复杂度的边缘紧耦合结构挖掘算法.其次,分别选择k-clique,k-clan,k-plex结构作为核心紧耦合结构,并以长结构优先和短结构优先2种策略将边缘与核心紧耦合结构合并.然后,将合并后的局部紧耦合结构融入模块性优化过程,提出了一种NFN算法.该算法将每个局部紧耦合结构初始化为独立社区,不断凝聚模块性增量最大的2个社区,直至找到预定义数量的社区.6个真实数据集上针对外部指标和内部指标的实验结果均表明,相比于传统的FN算法,NFN算法能发现更高质量的社区.在参数设置方面,长结构优先策略优于短结构优先策略,且采用k-clique结构作为核心紧耦合结构优于采用其他结构.因此,长结构优先策略结合k-clique成为NFN算法的最佳参数组合.     

基于社区节点重要性的社会网络压缩方法

针对目前图压缩方法中存在的时间复杂度较高、依赖先验知识设定参数、需要调节的参数过多、压缩有损、忽视网络社区结构等问题, 提出基于社区节点重要性的社会网络压缩方法。该方法由基于贪婪策略的社区发现算法(GS)和社会网络压缩算法(SNC)两部分组成。GS算法采用拓扑势理论, 不但可以实现社区发现, 而且可挖掘出社区中的重要节点。SNC算法以网络社区为压缩对象, 在保持社区间的关联关系的前提下实现了无损压缩, 并可在必要时保留社区中的重要节点或基本结构。通过实验, 对方法的可行性和有效性进行了验证。     

学习全局边函数的半监督社区检测

随着在线网络数据量激增,单纯分析网络拓扑结构、节点属性、边属性无法有效认识和理解其内在结构和特性,因此提出基于边函数的半监督社区检测算法。首先将拓扑结构和属性信息统一为先验知识,设计边函数便于引入属性等各类先验知识;在此基础上,结合传统半监督学习框架,采用半正定规划学习全局最优的节点归属矩阵。在人工合成数据、赣南客家数据和基准数据上的实验和分析表明,与已有传统半监督社区检测算法相比,该算法能有效利用各种先验知识,检测社区性能较好,并能较好地抵抗数据退化问题。     

异质网络社区发现方法研究综述

社区结构是复杂网络研究中的重要领域,也是复杂网络的重要特征之一,发现网络中的社区结构在理解网络功能方面起着重要作用。通过对国内外异质网络社区发现文献进行深入研究,较为全面地对现有异质网络社区发现算法进行了归纳总结。首先,通过对国内外异质网络社区发现文献进行归纳,给出异质网络社区发现的基本概述,明确异质网络社区发现领域相关问题的基本定义。其次,介绍了异质网络社区发现算法及主要评价指标,利用不同网络结构以及算法对现有方法进行分类概述。最后,对异质网络社区发现算法的发展趋势进行了总结与展望,提出未来可以将研究重点集中在以下几个方面:1)探索基于异质网络的社区发现评价标准,以推动该领域的快速发展;2)设计更加通用的算法模型,解决由先验知识引起的未知社区数量问题;3)开展更多关于动态网络的研究。     

大规模社交网络重叠社区发现技术综述

随着社交网站的发展,大规模、结构复杂的社交网络应运而生,发现大规模社交网络的潜在结构是当前数据挖掘领域的研究难点.针对近几年出现的4种重叠式社区挖掘算法(SLPA,TopGC,SVINET,UEOC),详细分析各方法的设计原理,概括出各算法的特点和应用范畴.并将各算法应用于具备先验社区知识的多种大规模社交网络,通过多种性能评价指标进行定量对比分析.结果表明,SLPA和TopGC分别在性能和效率上取得最优,但所有算法无法同时在效率和性能上取得理想效果.     

西安交通大学学报 2007年41卷分类索引篇名(期号/页码)

管理科学排污权期权价值评估模型研究(1/106)现代信用风险模型的统一性分析(1/110)自然科学总论与数学基于先验知识与模块性的网络社区结构探测算法(6/750)Zak变换和平移不变子空间中的抽样定理(10/1248)复金兹伯格朗道方程螺旋波外矢量场响应的数值模拟(10/1242)一个新Pohozaev恒等式及其在四阶拟线性椭圆方程中的应用(10/1245)中子输运问题源项反演的反幂法(4/493)随机1集压缩型算子方程的几个定理(2/241)一种具有跟踪替代特征的小世界算法(11/1360)壳体中性曲面变形后的度量张量和曲率张量(12/1483)力学均匀覆层梯度半空间中的Love面波…     

基于动量粒子群优化的社会网络分析

针对社会网络分析中的社区发现问题,在原有的粒子群优化算法的基础上,提出了一种基于动量粒子群优化算法,并且将此算法应用于社会网络分析中的社区发现研究中,提出了一种自适应社区发现方法.利用Newman提出的模块度作为适应度函数,在优化过程中自动获取社区数目,在Karate网络上的实验结果表明,所提出的算法能够有效地进行社区...     

高度重叠社区的社区合并优化算法

当原图转换成边图后,在边图上进行社区发现可以天然地得到重叠社区,然而得到的社区往往相互大面积重叠,甚至相互包含,导致社区模块性质量较低.针对这一问题,在得到边图下重叠社区发现算法结果的基础上,我们将进一步以优化重叠社区模块化质量函数为标准进行社区合并,以获得高质量的重叠社区.本文首先提出一种描述社区间重叠程度的重叠系数,并基于此进一步提出一种构建带权社区图的启发式方法,能够快速有效地完成社区合并的过程.在人工生成网络与真实世界网络上的实验,进一步验证了该算法能够在不削弱边图方法速度优势的前提下,提高高度重叠社区的模块性.     

基于GN算法的重叠社区识别方法

针对社会网络中的重叠社区识别问题,提出用从属度描述节点对不同社区的紧密程度,并把模块度扩展到重叠社区的识别.基于Girvan和Newman提出的非重叠社区识别(GN)算法设计了重叠社区的串行识别算法.基于MapReduce模型设计了并行识别算法,以提高识别效率.对模块度与重叠度进行了分析,结果表明:所提出的算法在计算机科学文献网络中能有效识别重叠社区,且运行效率优于已有重叠社区识别算法.     

基于相似度投票的社区划分改进算法

为快速、 准确地对日益复杂的大规模社会网络进行社区划分, 提出一种基于相似度投票的改进算法替代Louvain算法的底层划分, 解决了Louvain算法在底层划分收敛速度较慢, 并出现大量重复计算的缺点, 使社区划分更迅速. 由真实社会网络数据实验结果可见, 与Louvain算法相比, 改进算法在保持模块度基本不变的情况下, 效率显著提高, 划分的社区数更少、 社区结构更紧凑.     

基于向量划分的复杂网络社区结构发现

社区结构是复杂网络最重要的结构特性之一,通过优化模块度来进行社区结构发现是目前使用最为广泛的一类方法.通过将网络看做有向图,模块度矩阵可表示为顶点的有向边向量表示的交叉协方差矩阵,但是该矩阵不是正定的.现有方法通过对该矩阵的进行谱分解,提取大于零的特征根对应的成分,将社区发现问题描述为向量划分问题.本文通过修正交叉协方差矩阵的对角线,使之满足正定性条件,将其表示为顶点向量的内积矩阵.因此,无须对模块度矩阵进行谱分解,甚至无须显式计算顶点的表示向量,就可以将基于模块度的社区发现问题重构为一个向量划分问题.进一步,从向量划分的角度解释了有限分辨率现象的根源,设计了以最大化向量夹角为指导的贪婪算法,该方法比直接优化模块度的方法有更高的异质社区分辨能力.在合成网络和真实网络上分别进行了实验验证,实验结果证实了所提方法的可行性和有效性.     

基于共邻节点相似度的加权网络社区发现方法

为实现加权网络的准确划分,发现真实的社区结构,提出一种基于模块度和共邻节点相似性的层次聚类社区划分方法IEM.首先,定义两节点间基于共邻节点的相似度.之后,基于该度量快速聚合当前节点和与其关联紧密度最强的邻居节点以形成初始社区,并进行社区扩展.最后,以最大化网络模块度为目标进行社区合并以优化划分结果.算法通过形成初始社区、扩展社区、合并社区三步,实现了加权网络合理有效的社区划分.以加权模块度作为社区划分质量的评价标准,在多个数据集上的实验结果表明,IEM算法优于加权CN、加权AA、加权RA.同时,与CRMA算法相比,IEM算法对加权网络社区划分的有效性和正确性更高.     

基于极值优化模块密度的复杂网络社区检测

分析了基于优化模块度检测复杂网络社区结构的算法存在解的限制问题,即不能检测出小于一定内在尺度的社区,并提出了基于极值优化模块密度来检测复杂网络社区结构的启发式算法,通过调整局部极值来优化全局的变量,使算法具有更好的持续搜索和跳出局优解的能力.通过人工网络和现实网络实验分析表明,本文算法用于检测大型网络社区时,具有较高的正确率和效率,即使当网络结构变得很模糊时,算法也能很好地工作.     

基于重要结点的社区发现算法

复杂网络中内部的社区结构是复杂网络结构特征和属性特征的具体体现。首先依据模块度最大化理论计算网络的模块度矩阵的最大k特征向量矩阵;然后提出聚类中心方法,并用于求出k个社团的重要结点作为k聚类中心,利用欧几里得距离计算每一个结点到k个聚类中心的距离,将结点分配到距离聚类中心最近的社区中;最后对网络应用k-means方法进行迭代计算,得到k个社区的划分。分别在Karate Club Network和American College Football数据集上对算法进行了实验验证,实验结果表明该算法可以有效发现潜在社区,其纯度与模块度比已有的社区发现算法都有一定的提高,并且迭代次数较少,效率较高。     

一种向量划分的网络社团发现方法

为有效地检测复杂网络中的社团结构,对评估与发现社团的模块密度函数(即D值)进行了优化.通过模块密度函数的优化进程,展示了模块密度函数被优化到向量划分方法中的社团向量幅度最大化,并且提出了一种新的向量划分方法.在一个经典的真实世界网络中检验了该算法.实验结果暗示这种新的算法在发现复杂网络社团上是有效的.     

一种对分划分的复杂网络社团检测方法

在许多领域,例如社会科学,技术科学及生物科学,复杂网络中的社团发现是一项重要任务。这些社团结构暗含着系统功能方面的信息并用来帮助人们理解网络的功能及增长机制。谱分优化了由李等人最近提出的一种用来评估和发现社团的模块密度函数。提出了一种对分算法,该算法使用模块密度矩阵的主特征向量迭代来检测网络社团结构。在一个经典的计算机产生的随机网络中检验了算法。当社团结构变地模糊时,实验结果显示这种新的算法在发现复杂网络社团上是有效的。     

基于注意力网络特征的社区发现算法

现实世界中许多网络都是根据社区结构紧密组织起来的, 发现社区对于了解复杂网络的结构及其关系有很大的帮助, 文中提出了一种基于注意力网络特征的社区发现(community discovery algorithm based on attention network features, CANF)算法, 利用标记节点频率和反示例节点频率度量初始网络标记特征, 并且引入注意力机制, 对示例节点的每个邻居节点更好地分配权重, 将初始权重与分配权重相结合, 使初始度量的网络特征获取更多与目标有关的细节信息。文中通过分配的注意力网络特征进行复杂网络预处理以及社区博弈归并, 于真实网络中进行验证, 实验结果表明, CANF算法在准确度、模块度以及运行时间方面优于其他社区发现算法。     

基于相似性模块度最大约束标记传播的网络社团发现算法

提出一种基于相似性模块度最大约束标记传播的快速网络社团发现算法(MLPA)。该方法采用结构相似度计算, 通过最大约束标记传播模型更新节点标记, 使社团的划分结果更加符合社团内部结构相对紧密、 社团之间结构相对稀疏的特点, 提高社团划分的精确度。结合标记传播5次循环迭代可以完成95%或者更多节点标记过程的实验结果, 判定标记更新过程趋于稳定, 从而在稳定时停止更新, 降低了运行时间。MLPA避免了传统的邻接矩阵计算方法, 适合大规模网络的社团发现。