一种基于增量式谱聚类的动态社区自适应发现算法

针对当前复杂网络动态社区发现的热点问题, 提出一种面向静态网络社区发现的链接相关线性谱聚类算法, 并在此基础上提出一种基于增量式谱聚类的动态社区自适应发现算法. 动态社区发现算法引入归一化图形拉普拉斯矩阵呈现复杂网络节点之间的关 系,采用拉普拉斯本征映射将节点投影到k维欧式空间.为解决离群节点影响谱聚类的效果和启发式确定复杂网络社区数量的问题, 利用提出的链接相关线性谱聚类算法发现初始时间片的社区结构, 使发现社区的过程能够以较低的时间开销自适应地挖掘复杂网络社区结构. 此后, 对于后续相邻的时间片, 提出的增量式谱聚类算法以前一时间片聚类获得的社区特征为基础, 通过调整链接相关线性谱聚类算法实现对后一时间片的增量聚类, 以达到自适应地发现复杂网络动态社区的目的. 在多个数据集的实验表明, 提出的链接相关线性谱聚类算法能够有效地检测出复杂网络中的社区结构以及基于 增量式谱聚类的动态社区自适应发现算法能够有效地挖掘网络中动态社区的演化过程.     

基于目标协同规划的网络入侵特征聚类仿真

在网络入侵检测优化的研究中,对网络入侵特征进行准确检测,由于在复杂的网络环境中会存在大量噪声,传统的方法只是单一的入侵特征聚类方法,难以在包含大量噪声的复杂网络环境中进行入侵特征聚类.提出一种基于目标协同规划思想的网络入侵特征聚类方法.利用标准化处理过程和归一化处理过程对对网络入侵数据进行预处理,能够将原始的网络入侵特征属性映射到标准属性空间.提取入侵特征构成数据集合,并进行降维处理,为入侵特征的聚类提供了准确数据基础,将可能性模糊聚类算法和聚类中心分离的模糊聚类算法进行入侵特征聚类目标的协同规划,能够得到准确的聚类中心.实验结果表明,改进算法能够提高网络入侵聚类的准确率.     

基于链接和萤火虫算法聚类博文发现热点话题

针对已有的基于链接分析的热点发现方法存在准确度较低、易受作弊链接影响、易产生主题漂移现象等问题,利用复杂网络簇结构具有高度主题相关的特点,提出一种融合应用链接分析和萤火虫算法聚类博文的热点话题发现算法。以博文页面为节点,与博文内容相同或相关的链接作为边,根据博文及博主的相关属性,综合评定页面权重,建立博客话题模型;运用萤火虫算法对博文进行聚类获得聚类中心,按页面权重将聚类中心从大到小排序,形成热点话题热度排行。实验结果表明,该方法能够发现精度更高、数量更多的博客热点话题。     

一种基于网络社团结构和模块化函数的聚类算法

结合复杂网络社团结构的相关研究,提出一种基于网络社团结构和模块化函数的聚类算法CSMFBCA(Community Structure and Modularization Function Based Clustering Algorithms)。算法通过数据点之间的关系进行融合,形成一定的数据簇,然后定义一个统筹全局的模块化函数,再通过最大化模块函数值,得到最优的聚类结果。实验结果表明,该算法不仅能很好地解决凹形数据聚类以及聚类个数识别的问题,而且能处理权重无向网络的社团发现问题,比现有的典型算法有明显的优势。     

基于混沌PSO的大数据智能加权K均值聚类算法

针对传统聚类算法无法处理大数据中多视图高维数据问题,提出一种基于混沌粒子群优化算法的智能加权K均值聚类算法。在聚类模型中引入聚类之间的耦合程度以扩大聚类的相似性。为了消除初始聚类中心的敏感性,利用混沌粒子群优化算法通过全局搜索得到最优初始聚类中心、视图权重和特征权重。引入一种精确摄动策略提高混沌粒子群优化算法的寻优性能。通过在Apache Spark和Single Node两个平台上的实验验证了该方法在视图多、维数高的复杂数据集条件下具有较好的聚类性能。     

基于低秩和局部约束矩阵估计的链接预测方法

在大数据时代,互联网社会网络和其他复杂网络中的链接预测问题研究成为热门领域。链接预测相关的方法已被广泛地应用于社会网络关系挖掘、个性化推荐和生物制药等领域。在链接预测问题中,通常使用相似性矩阵来表示网络中任意节点之间存在链接的可能性,因此相似性矩阵的计算是链接预测中至关重要的一步。近年来的研究中,大多数方法是基于已知网络中数据的分析,通过网络潜在结构设计机器学习算法构造相似性矩阵。在全局低秩的网络结构假设下,结合网络中节点特征的局部约束,提出了一种基于数据的链接预测优化算法,并针对复杂网络数据链接预测问题设计了可扩展的分治方法,便于分布式环境中对大规模数据进行求解。通过在多个真实数据集上的实验和结果分析,基于低秩结构和局部约束矩阵估计的链接预测分治方法能够取得较好的效果,并对复杂的网络结构数据具有较强的可扩展性。     

弱链接文档搜索引擎研究

聚类技术能将大规模数据按照数据的相似性划分成用户可迅速理解的簇．从而使用户更快地了解大量文档中所包含的内容。因此．聚类技术成为搜索引擎中不可或缺的部分和研究热点。Web上的AJAX应用和PowerPoint文件等弱链接文档由于缺乏足够的超链接信息,导致搜索该类文档时．排序结果不佳。针对该问题．给出一个弱链接文档的搜索引擎框架,并重点描述一个基于网页搜索结果的弱链接文档排序算法．基于聚类的弱链接文档排序算法利用聚类算法从高质量的网页搜索结果中提取与查询相关的主题．并根据主题的相关网页的排名确定该主题的重要性．根据识别的带权重的主题计算弱链接文档的排序值。实验结果表明该算法能够为弱链接文档产生较好的排序结果．     

一种双重特征选择的不平衡复杂网络链接分类模型

基于有监督学习思想的链接分类是复杂网络分析领域的主要研究问题,该思想的核心在于把网络分成训练网络和目标网络,通过分类模型学习训练集合并对目标集合进行预测。然而在复杂网络链接分类这一场景中,正类别样本和负类别样本的分布是不平衡的,特征之间会存在冗余信息,这一现象往往制约着分类性能的有效提升。针对该问题,提出了一种双重特征选择的分类模型,该方法借助Relief赋予特征权重并使用K-means聚类算法对不平衡样本进行采样,解决数据不平衡问题,然后引入极小冗余-极大相关（mRMR）衡量特征与特征之间和特征与类别之间的相关性,同时最大限度地减少冗余。在多个真实复杂网络数据集上的实验结果表明,相较于目前主流的链接分类模型,本文的方法能够明显的提升分类的性能。     

基于低秩和稀疏矩阵分解的多源融合链接预测算法

近年来,链接预测成为社会网络和其他复杂网络链接挖掘中的热门研究领域.在链接预测问题中,经常会存在用来提高预测效果的附加数据信息源,这些数据可以用于预测网络中的链接是否存在.在所有的数据源中,最主要的数据源在链接预测中起到最重要的作用.因此,设计具备健壮性的算法用于充分利用所有数据源的信息来进行链接预测十分重要,算法还需要平衡主数据源和附加数据源的关系,使得链接预测能够获得更好的效果.同时,传统基于拓扑结构计算的无监督算法大多数通过计算网络中节点间的评分值来解决预测链接存在可能性的问题,这些方法能够获得有效的结果.在链接预测方法中,最关键的一步是构建准确的输入矩阵数据.由于许多真实世界数据集存在噪声,这导致降低了大多数链接预测模型的效果.提出了一种新的链接预测方法,通过多个数据源的融合,兼顾地利用了主数据源的信息和其他附加数据源的信息.接着,主数据源和其他附加数据源被用于构建一个低噪声且更准确的矩阵,而新的矩阵被用于作为传统无监督拓扑链接预测算法的输入.根据在多个真实世界数据上的测试结果,在多源数据集上进行对比实验,提出的基于低秩和稀疏矩阵分解的多源融合链接预测算法相对于基准算法能够获得更好的效果.     

基于半监督学习的链接预测算法的研究*

针对链接挖掘中网络的结构难以预测这个难点问题,提出了一个关于链接预测的新型半监督学习方法——基于快速共轭梯度方法和链接相似性传递增殖原理的链接预测算法,利用节点相似性等辅助信息去预测未知结构。该算法利用张量的形式去表示多维的复杂的多关系数据,利用克罗内克积与克罗内克和去计算张量之间的相似性,利用向量特技方法降低了算法的时间和空间复杂度。在社会网络和生物信息网络等环境下,通过实验验证了算法的有效性和健壮性。     

具有社区结构的无标度网络生成算法

近年来,生成图模型在复杂网络研究中的作用越来越重要。图的生成过程对于研究疾病的蔓延和信息的传播具有重大意义,同时图模型的生成也有助于更深入地研究复杂网络的特性。为了能够生成既符合真实网络特征又具有结构多样性的复杂网络,提出了一种具有社区结构的可调节聚集系数和模块性的无标度网络生成算法——TCMSN(Scale Free Network with Tunable Clustering Coefficient and Modularity)。通过调节混合参数可以调节生成网络的模块性,通过调节社区内连边的概率和混合参数可以对网络聚集系数进行调节。TCMSN采用了合理的连边策略,在不破坏网络结构多样性的情况下,能尽可能维持网络的无标度特性。人工构造数据和真实网络数据的对比实验结果表明,TCMSN算法能够生成可调节聚集系数和模块性的无标度网络模型,且能够生成最接近真实网络社区结构特征的网络模型。     

复杂网络大数据中重叠社区检测算法

大数据时代互联网用户数量呈爆炸性增长,社交网络、电商交易网络等复杂网络规模快速发展,准确有效地检测复杂网络大数据中重叠社区结构对用户兴趣点推荐和热点传播具有重要意义。提出一种新的面向复杂网络大数据的重叠社区检测算法DOC（Detecting Overlapping Communities over complex network big data）,时间复杂度为O（nlog²（n））,算法基于模块度聚类和图计算思想应用新的节点和边的更新方法,利用平衡二叉树对模块度增量建立索引,基于模块度最优的思想设计一种新的重叠社区检测算法。相对于传统重叠节点检测算法,对每个节点分析的频率大大降低,可以在较低的算法运行时间下获得较高的识别准确率。复杂网络大数据集上的算法测试结果表明：DOC算法能够有效地检测出网络重叠社区,社区识别准确率较高,在大规模LFR基准数据集上其重叠社区检测标准化互信息指标NMI最高能达到0.97,重叠节点检测指标F-score的平均值在0.91以上,且复杂网络大数据下的运行时间明显优于传统算法。     

模块度增量与局部模块度引导下的社区发现算法

社区结构是复杂网络的重要特性之一,基于层次聚类的社区发现算法很好地利用了模块度来挖掘网络中的社区结构,但其局限性也导致算法对社区结构复杂的网络划分不够准确、无法发现小于一定规模的社区。在层次聚类的基础上,提出引入局部模块度来弥补模块度在划分社区时的不足,避免可能出现的划分不合理情况。通过真实数据集和人工网络进行了验证,实验结果证明,该算法具有可行性与有效性。     

基于信息熵的复杂网络社团划分建模和验证

社团结构是复杂网络最普遍和最重要的拓扑属性之一,社团结构的划分方法对分析复杂网络相关统计特性具有十分重要的理论意义.为了提高社团划分精度,提出了一种新的基于信息熵(information entropy)模块度的社团划分算法(简称IE算法).在有着确定社团结构的数据集和不确定社团结构的数据集上,通过选取Q值、社团划分个数、社团最大连通分量大小和强弱社团个数比例4个重要参数,将IE算法与两种最主要的基于模块度的划分算法GN(Girvan-Newman)和FastGN(Fast Girvan-Newman)进行对比,实验结果证明了IE算法在社团划分性能上优于GN和FastGN;将IE和其他7种最主要的经典社团算法进行时间复杂度分析,并在随机网络和真实网络上进行实验,结果表明该算法时间复杂度在GN与FastGN之间,时间复杂度小于GN而精确度优于GN,证明了在大多数数据集上IE算法的社团划分准确度优于传统基于点边比率的社团划分算法的准确度.     

复杂网络社团的谱分检测方法

为有效地检测复杂网络中的社团结构,优化模块密度函数,展示模块密度函数怎样被优化框定到谱分聚类问题,提出一种谱分算法,进一步对该算法进行时间复杂度分析。在一个经典的真实世界网络中检验该算法,并与基于模块密度的直接核方法及基于模块函数的谱分方法做比较。特别地,当网络中社团结构变得模糊时,实验结果显示,该谱分算法在发现复杂网络社团上是有效的。     

非负矩阵分解的复杂网络社团检测方法

为有效地检测复杂网络中的社团结构,优化了评估与发现社团的模块密度函数(即D值).通过模块密度的优化进程,证明了模块函数的最大化与非负矩阵分解目标函数(SNMF)的等价性.基于这种等价性,设计了一种新的基于模块密度函SNMF算法,并且讨论了该算法的复杂性.在一个经典的计算机产生的随机网络中检验了该算法,特别地,当社团结构变模糊时,实验结果表明该算法在发现复杂网络社团上是有效的.     

二谱分聚类的复杂网络社团检测方法

近年来,复杂网络中的社团发现越来越受到研究人员的关注并且许多方法被提了出来。为有效地检测复杂网络中的社团结构,优化了评估与发现社团的模块密度函数(即D值)。通过模块密度的优化进程,证明了模块密度函数能写成模块密度矩阵迹的最大化表达形式。利用模块密度矩阵的谱分分解,提出了一种新的二谱分的聚类检测复杂网络社团方法。在LFR标准人工模型网络中验证了二谱分方法的有效性。实验结果显示这种新的方法在发现复杂网络社团上有较高的准确性。     

基于模块度函数的加权蛋白质复合物识别算法

针对加权模块度函数聚类算法在蛋白质相互作用网络中进行复合物识别的准确率不高、召回率较低以及时间性能不佳等问题进行了研究,提出一种基于模块度函数的加权蛋白质复合物识别算法IWPC-MF（Algorithm for Identifying Weighted Protein Complexes based on Modularity Function）。融合点聚集系数改进边聚集系数,将改进后的边点聚集系数与基因共表达的皮尔逊相关系数结合来构建加权蛋白质网络;基于节点权重选取种子节点,遍历种子的邻居节点,设计节点间的相似度度量和蛋白质附着度来获取初始聚类模块;设计基于紧密度的蛋白质复合物模块度函数来合并初始模块,并最终完成复合物的识别,克服传统的模块度函数无法识别出重叠和规模较小的复合物的缺陷。将IWPC-MF算法应用在DIP数据上进行复合物的识别,实验结果表明IWPC-MF算法的准确率和召回率较高,能够较准确地识别蛋白质复合物。     

基于加权网络和局部适应度的蛋白质复合物识别算法

蛋白质复合物识别对分析蛋白质网络的结构特征和模块功能具有重要意义。通常在蛋白质网络中挖掘稠密子图或模块来识别其中的蛋白质复合物,限制了其应用范围和识别的准确性。针对该问题,提出了一种基于加权网络和局部适应度的蛋白质复合物识别算法,该算法综合稠密子图的密度指标和模块性定义了新的局部适应度函数,并基于边聚集系数构建加权的蛋白质网络,根据权值选择边,在加权蛋白质网络中将种子边不断聚类扩展,从而获取具有最大综合适应度的子图作为蛋白质复合物。在酵母蛋白质等多个实际网络中试验表明,该算法能够有效提升蛋白质复合物识别的准确性。     

基于谱分析的无线传感器网络模块度分簇算法

基于谱分析与模块度,提出一种无线传感器网络分簇算法(CHSM).首先利用非平凡特征向量获得传感器网络的原始簇结构;然后借助模块度的增量来评估、合并原始簇,从而形成一个与真实网络相匹配的簇结构;同时设计了一种能量异配度函数,并利用各节点的能量异配度及其剩余能量在各个簇内选取簇头节点.仿真结果表明,CHSM算法找到的簇结构具有更高的模块度,其选取的簇头节点具有更高的能量异配度,进而表明了所提出的算法能有效延长网络的寿命.