一种基于图压缩的重叠社区发现算法

为提高单机处理复杂网络规模的能力,提出一种新的重叠社区发现算法.首先,通过基于图压缩的社区结构表示模型(压缩社区图),对网络进行无损压缩;然后,在压缩社区图上基于种子迭代的思想,通过不断优化社区适应度函数将种子扩展成社区;最后,将相似度高的社区进行合并,得到最终的重叠社区结果.由于压缩后的凝聚图大大降低了待处理的网络规模,并能在一定程度上减少重复计算,该方法可以大大提高计算效率和单机处理的网络规模.     

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

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

大规模网络广义社区发现随机变分推理算法

流行度-生成度随机块(popularity-productivity stochastic block,PPSB)模型能发现网络广义社区,但该模型易过拟合,且不能有效处理大规模网络,故提出一个3层贝叶斯网络广义社区发现(generalized PPSB,GPPSB)模型,并给出实现大规模链接网络和内容网络广义社区发现的随机变分推理(stochastic variational inference,SVI)算法GPPSB-SVI和GPPSB-C-SVI。不同规模人工网络和实际网络上的实验结果表明:GPPSB-SVI准确性优于已有流行大规模网络社区发现算法,效率高于基于PPSB模型的广义社区发现算法;GPPSB-C-SVI准确性优于GPPSB-SVI算法;GPPSB模型引入节点隶属度和类间链接概率矩阵的先验分布,可更好地对网络建模,其参数估计算法GPPSB-SVI、GPPSB-C-SVI可更有效地实现大规模网络广义社区发现。     

基于MCMC的贝叶斯长记忆随机波动模型研究

针对贝叶斯长记忆随机波动模型的单步Gibbs抽样算法效率低下的问题,通过对模型在状态空间框架下的近似表示,将向前滤波向后抽样算法引入对波动变量的估计过程中,同时在贝叶斯框架下分析了模型参数的满条件后验分布,设计出Gibbs联合抽样算法.更进一步,在对模型进行参数估计的基础上,提出波动变量的向前多步预报分布的估计方法.模...     

基于三角模体的社团发现算法

为了提高社团发现算法的效率,提出了一种基于三角模体和期望极大的社团结构发现(Community structure discovery based on triangular motifs and expectation-maximization,CSDTME)模型的社团发现算法。CSDTME模型采用三角模体对网络进行表示,考虑了节点的混合隶属度及社团间的链接关系,用期望极大算法计算模型涉及的参数,采用全三角模体和两边三角模体作为计算对象,通过减少计算对象来提高算法的效率,根据参数结果可得到节点的社团隶属度及社团间的链接关系。实验结果表明:在保证社团发现能力的同时,该算法能够提高社团发现的效率。     

基于边聚类系数的谱聚类社区划分方法研究

针对图谱划分方法在划分社区结构不是很明显的网络时,不能得到好的划分效果,该文提出了基于边聚类系数的谱聚类社区划分方法.由于社区内部节点之间的连接比各个社区间节点的连接稠密,边聚类系数的大小反映了节点的聚集程度,因而通过网络中的边所构三角形的数量定义了聚类系数矩阵,矩阵中的元素即处于网络中的边实际构成三角形的数量.在增益函数最大化的过程中,使用了矩阵的特征值和特征向量,以此来进行社区划分.通过在真实网络数据中进行实验,结果表明该算法可行.     

蛋白质界面网络中模体和模块的探测

基于复杂网络研究蛋白质界面网络中的模体和模块,发现蛋白质界面网络与蛋白质肽链网络的拓扑性质有差异.蛋白质界面网络中的模体类型和数量受截断距离R影响较大,R值不同,网络中的模体类型和数量都有较大差别.蛋白质界面网络中存在模块结构,分析R为0.5,0.7,1.2,2.4nm时网络中存在的3-派系-模块,发现当R为0.7nm时的蛋白质界面网络模块划分比较符合实际.最后,分析蛋白质界面网络中的模块与其拓扑性质的关系,发现界面网络中的节点数与3-派系-模块数呈线性关系.     

一种基于派系过滤的社区进化发现研究

在对派系过滤方法及其相关原理进行研究基础上,分析了该方法在社区进化发现中存在的参数依赖问题,提出了一种基于派系过滤的社区进化发现方法:通过生成社区树,综合多组参数的社区发现结果,可获取网络中不同耦合度的社区的层次结构,从而发现网络中社区的进化过程.本文将该方法应用在单词关联网络中,实验结果表明,该方法能够发现各社区在进化过程中的规模、成员以及耦合度方面的变化,在一定程度上,克服了传统派系过滤方法对参数的依赖性.     

生物序列模体发现的最优化模型

提出了生物序列模体发现的最优化模型,该模型适用于搜索资源(如计算时间)有限的情况,传统的模体发现方法可能在资源耗尽后仍不能得出任何结果.基于最优搜索理论给出了一种在有限的时间资源下的最优模体发现策略和算法实现,并得到了一些实验结果.     

一种高效的生物网络概率模体发现算法

针对概率模体发现算法中非树形子图的挖掘和在得分函数最大化的过程中得分函数值计算的2个难点.首先提出基于划分的非树形子图的搜索算法,其次将子图同构应用于最小错配的求解以缩小智能优化算法对得分函数求解的解空间,最后将基于模拟退火算法和遗传算法的混合算法应用于得分函数的求解过程.在大肠杆菌基因调控网络中的实验结果表明,与其他算法相比,混合智能算法可以大大减少非树形子图的搜索时间,并以相对较快的收敛速度收敛到一个较优的解,因此所提出的方法有效地提高了概率模体发现的效率.     

盗窃犯罪空间分布与地理因素的关联

为分析犯罪空间分布成因,将地理加权回归模型用于犯罪空间分布与地理因素关联研究。该模型可以处理空间关系变化过程,求解空间非稳定性问题。以社区盗窃案件发案率为例,建立了盗窃刑事犯罪率与社区人口密度、路网密度、社区距派出所距离等因素之间的局部分析模型,给出了参数估计及显著性检验空间分布图。结果表明,犯罪空间分布与人口、环境等因素的关系随空间位置而改变;地理加权回归模型可以提高参数估计的准确性。     

论无标度网的增长和择优

增长和择优机制是无标度网络中两种重要的演化机制,已发现比较重要的择优机制有度择优和秩次择优,比较重要的增长方式有星形图增长和完全图增长.该文首先分析了秩次择优机制对网络度指数的影响,指出可以利用秩次择优来构造度指数在较大范围内变化的模型. 接下来分析了星形图增长和完全图增长的优缺点,并提出了更符合实际情况的模体增长方式,然后结合秩次择优机制和模体增长方式提出了一个新模型——模体增长秩次择优模型,该模型除了具有较宽的度指数范围外,还在度指数大于2.5时具有独立于网络规模的群集系数.     

融合社区连接信息的网络嵌入方法

网络嵌入旨在学习节点的低维稠密向量,同时保留原始网络的结构和属性信息。现有的网络表示方法大多未考虑网络中的社区信息和社区间的信息,难以有效地学习网络的低维表示。为有效保留网络中的社区信息和社区间信息,提出了一种融合社区连接信息的网络嵌入方法(network embedding based on community connection information,ECCI)。该方法基于不同社区的亲密程度,捕捉网络中社区间的关系;采用自定义游走的方式得到融合局部结构、社区信息以及社区间信息的游走序列;通过Skip-Gram模型得到与之对应的网络嵌入结果。在3个公开数据集的实验结果表明,ECCI相比基准方法在链接预测上的AUC值和F1-Score都有一定程度的提升。     

基于重叠社区发现的社会网络推荐算法研究

协同过滤算法已成为用来为用户提供个性化服务以处理海量信息最常用的方法之一.本文提出一种基于重叠社区发现的社会网络推荐算法,该算法同时考虑了群组用户的兴趣以及他们复杂的内部关系,通过将重叠社区发现算法和基于模型的社会推荐算法进行创新融合,以实现重叠社区的发现、建立,和基于社区的智能推荐.基于开放数据集,本文设计了一系列相关实验以验证算法的有效性和准确性.实验结果表明本文提出的算法可以实现高效且准确的社会网络推荐.     

多方法集成预测短柄草核心启动子模体

为了解决真核生物启动子调控元件注释难题,以短柄草为研究对象,进行全基因组范围内的核心启动子模体预测.基于系统进化足迹技术,集成多种模体发现算法寻找启动子模体,并结合模体聚类算法筛选出真实模体.结果发现,在前10个最优的核心启动子模体中,有6个与已知的拟南芥模体一致,表明该方法的有效性.     

直接三角形和矩形NAM的灰度图像表示算法

分析了三角形非对称递布局模型(NAM)、矩形NAM和线性四元树表示算法,借助于三角形和矩形布局问题的思想,提出了一种直接三角形和矩形NAM (TRNAM)的灰度图像表示算法.通过描述三角形和矩形子模式的存储结构,给出了该算法数据量的理论分析.实验结果表明:与直接三角形NAM表示、直接矩形NAM表示和线性四元树表示算法相比,直接三角形和矩形NAM表示算法能够更有效地减少子模式数(节点数)和数据存储空间,是灰度图像模式的一种更优的表示方法,这种表示方法在降低存储空间、加快传输速度、提高模式匹配效率等方面具有理论参考意义和实际应用价值.     

区域创新合作网络演化特征与动力研究——以长三角为例

基于2005—2019年长三角地区产学联合申请专利数据构建合作网络，运用空间网络分析法、模体分析法和指数随机图模型研究网络的演化特征及动力机制。研究发现：在空间格局上，由“三足鼎立”向“核心-边缘”演变；在局部模体上，闭合模体是网络中的重要模体，网络存在集团化现象；在网络动力机制上，内生结构效应和节点属性效应是网络关系形成的重要动力，演化过程中存在显著的“马太效应”与“同质效应”。从战略协同、高地共建与机制重构等方面提出优化区域创新合作网络结构和促进长三角创新一体化发展的政策建议。     

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

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

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

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

扩展产生式规则的网络故障诊断专家系统

根据自然语言理解和网络故障诊断专家系统的特性,提出了一种扩展产生式规则的知识表示方法.扩展产生式规则将规则的前提、结论和建议分别用概念图表示,是一种混合知识表示方法.在扩展产生式规则知识表示方法的基础上,设计出了网络故障诊断专家系统的模型.该系统具有自然语言接口,可将网络中有关故障问题的汉语语句转换成概念图;经过专家系统推理后,可将推理结果和推理过程转换成汉语输出.为了增强专家系统知识获取的灵活性,在系统中还增加了Apriori关联规则挖掘算法,通过对陷阱协议数据单元挖掘,实现在线知识获取.利用该系统模型已开发出网络故障诊断专家系统原型.