面向超图数据的最大独立集算法

超图是普通图的泛化表示,在许多应用领域都很常见,包括互联网、生物信息学和社交网络等.独立集问题是图分析领域的一个基础性研究问题,传统的独立集算法大多都是针对普通图数据,如何在超图数据上实现高效的最大独立集挖掘是一个亟待解决的问题.针对这一问题,提出一种超图独立集的定义.首先分析超图独立集搜索的两个特性,然后提出一种基于贪心策略的基础算法.接着提出一种超图近似最大独立集搜索的剪枝框架即精确剪枝与近似剪枝相结合,以精确剪枝策略缩小图的规模,以近似剪枝策略加快搜索速度.此外,还提出4种高效的剪枝策略,并对每种剪枝策略进行理论证明.最后,通过在10个真实超图数据集上进行实验,结果表明剪枝算法可以高效地搜索到更接近于真实结果的超图最大独立集.

边带权最大独立集问题及其近似算法

区别于传统对带权最大独立集问题的研完,本文从新的角度首先提出了边带权最大独立集问题,给出了完整的定义,证明了它的NP-Complete难解性。并且通过对问题结构的研完,给出了一个近似度为1/「(Δ′+1)/3」的近似算法,Δ′为图中点的最大度数。

闭模糊拟阵导出独立集的等价描述

利用闭模糊拟阵可由基本序列和导出拟阵序列唯一确定的方法,提出并证明一个子集族、一个数列和由该子集族到该数列的一个满射,在满足规范性、继承性、强单调减和增长性的条件下唯一确定一个闭模糊拟阵,反之亦然.该等价描述建立了普通集族与模糊独立集族的联系.

量子近似优化算法在最大独立集中的应用

最大独立集问题是著名的NP问题,并且在许多场景中都有应用。传统的精确算法解决最大独立集问题需要指数级的时间复杂度。为更高效地解决最大独立集问题,提出了一种基于量子近似优化算法的量子线路解决方案。该方案由最大独立集的数学模型,推导出最大独立集问题的哈密顿量表达式;设计了基于量子近似优化算法的量子线路,采用COBYLA经典优化算法对参数量子门中的参数进行优化,并使用IBM提供的量子开发框架Qiskit进行仿真实验。仿真结果表明,使用量子近似优化算法可以在多项式时间内以高概率获得最大独立集问题的解,实现了指数加速。量子近似优化算法对解决最大独立集问题有一定的可行性和有效性。

网络分解及最大独立集算法研究(Ⅰ)

本文首先分析了一般网络的结构特征,开发出对任意网络进行变换及分解、且不丢失可行解的新方法。继而发现了网络中具有优化迭代功能的特殊子网络;对其进行了较深入的研究,提出并论证了求最大独立集的充要条件;研制出在网络中系统搜索该特殊子网络的新算法。最后,对算法的有效性及可靠性,进行了较全面的分析论证。研究表明,该算法可在时间复杂性O(|V|5)界内收敛。

极大独立集与极小覆盖集的逻辑及递归算法

本文主要研究了图的极大独立集与极小覆盖集之间的关系,并给出了将图的所有极大独立集与极小覆盖集一次性给出的逻辑及递归算法。

关于Ramsey图:一个递归型查找图中所有给定元素个数独立集的算法

改进了作者在文献〔1〕中给出的算法 ,给出一个速度较快的新算法 ,对一个可能的 ( s,t,n) -Ramsey图 ,该算法可以找出其中所有给定元素个数的独立集 ,进而可以检验该图是否是一个 ( s,t,n) -Ramsey图 .

基于二次独立集的数据融合调度算法

针对无线传感器网络数据融合中服务质量与加权公平性保证问题,提出了一种基于二次独立集的数据融合调度算法MISS。该算法采用时分复用思想,通过2次构造最大独立集实现对加权数据的无冲突调度。首先构建以最大独立集为基础的树型结构,并根据能量消耗预测进行调整形成最终的数据融合平衡树;然后通过优化调度对象集合,利用近似最大加权独立集为允许通信的链路分配传输时隙。实验结果表明,该算法能够在降低融合时延、加权公平性保证以及延长网络生命周期等方面实现性能平衡。

极大独立集的逻辑算法

给出了利用命题逻辑公式的析取范式和主析取范式求图的独立集和极大独立集的方法 ,并给出了一般算法 .

基于离散Hopfield网络求解极大独立集的茎区选择算法以及在RNA二级结构预测中的应用

提出了一种利用离散Hopfield网络求解图论极大独立集的启发式算法,并将其应用于RNA二级结构的茎区选择和预测当中.算法通过映射RNA序列的茎区为无向图中的节点,将预测RNA二级结构的问题转化为求解图的极大独立集的问题.定义了合理的能量变化函数,利用离散Hopfield网络进行迭代,以获得能量最优的预测结构.文中将算法与传统的最大匹配数算法以及最小自由能算法在运行时间上进行比较,并且选择特定的序列在茎区和碱基对水平上进行精度测试,结果证明该算法在效率和精度上具有一定的优势.算法的时间复杂性为max{O(n2),O(N2)},空间复杂度为O(N2),其中n为RNA序列长度,N为RNA的茎区段个数.

论简单图所含k阶i爪独立集个数的可重构性

设Ｉ是图Ｇ的一个含有ｋ个点的独立集（简称ｋ独立集）．如果Ｉ不是Ｇ的其它任何独立集的真子集，则称Ｉ为Ｇ的一个极大独立集．Ｇ中所含的极大ｋ独立集的个数记为ｍ（ｇｋ，Ｇ）．设ｇｋ是图Ｇ的任一个ｋ独立集，如果存在（ｖ１，ｖ２…ｖｉ｝Ｖ（Ｇ）－ｇｋ，ｉ≥１，使得（１）对任意ｊ∈｛１，２，…，ｉ｝，ｇｋ＋｛ｖｉ｝的都是Ｇ的（ｋ＋１）－独立集；（２）对任意的都不是Ｇ的独立集，则称ｇｋ为Ｇ的一个ｉ爪ｋ独立集，Ｇ所含的ｉ爪ｋ独立集的个数记为ｍｉ（ｇｋ，Ｇ）．该文证明了对简单图Ｇ，ｍ１（ｇｋ，Ｇ）和ｍ（ｇｋ，Ｇ）都是可重构的．另外，用同样的方法可以证明Ｇ中的极大ｋ团的个数及ｉ爪ｋ团的个数也是可重构的．

边可迁图的线独立集

证明了当群关于可迁且为阿贝尔群或幂零群时,每个非图包含两个不相交的最大线独立集.

一类求解最大独立集问题的混合神经演化算法

提出一类求解最大独立集问题 (MIS)的混合型神经演化算法 .该算法基于空间剖分与“排除”策略 ,有效综合了神经网络快速收敛及遗传算法稳健全局搜索的特别优点 .与标准遗传算法和神经网络算法相比 ,该算法显示了极高的全局优化性态与计算效率 .

基于极大独立集的最小连通支配集的分布式算法

全网范围的广播在无线传感器网络和移动自组织网络中有着广泛的应用.为节省网络资源,减少冗余转发节点成为广播中需解决的关键问题.广播过程中最小化参与转发节点数问题与图论中求解最小连通支配集问题等价,而在任意图中求解最小连通支配集是NP完全问题.本文基于极大独立集,提出了一种求解最小连通支配集的分布式算法(MISB),并证明了算法的正确性.仿真结果表明,使用该算法能得到较小的连通支配集,从而有效减少网络广播过程中的转发节点数,大大节省了网络资源.

生成图的全部极大独立集的一般方法

图的极大独立集问题是图论中重要的NPC问题,独立集具有广泛的应用领域,如编码理论、信道分配、资源配置、纠错码理论等。文章运用拟序关系理论,系统研究了生成图的全部极大独立集的一般方法,该方法简单实用,程序化实现容易。

超立方体的3－独立集及其在神经联想存储器中的应用

用Ｉ３（ｎ）表示ｎ－立方体Ｑｎ的３－独立数。提出了构造Ｑｎ的３－独立集的一个算法，证明了２ｎ－［ｌｏｇ２ｎ］－１≤Ｉ３（ｎ）≤［２ｎ／（ｎ＋１）］．这些结果被应用于神经联想存储器的设计．

图的k-独立集与Grbner基求解

本文给出一种求解任一具有n个顶点的有限图G的极大独立集和独立数的代数计算方法.该方法是通过将求解G的极大独立集问题加强为对每个1≤k≤n求解G的k-独立集问题来给出的.首先证明了G中k-独立集的存在性等价于一个多元多项式方程组的解的存在性,使得可以通过使用多项式理想的Grbner来判断所得方程组解的存在性并进一步求解方程组.由于k-独立集存在时只有有限多个,得到的Grbner基构成的方程组是很容易求解的三角形方程组,G的极大独立集和独立数在求解最多n个方程组即可得到.最后,通过实例验证了代数计算方法的有效性.

用神经网络新方法求解图的最大独立集问题

在Hopfield神经网络优化方法的基础上,根据模拟退火算法逃离局部最优解的原理,提出了一种神经网络优化计算的新方法,并用这种方法求解图的最大独立集问题。结果表明,该方法获得最优解比Hopfield神经网络优化算法获得的解要好,且所需时间比模拟退火算法少得多,

复杂网络独立集的免疫策略分析

根据独立集的概念,提出了新的复杂网络的免疫策略,免疫一个独立集中度数最大顶点的免疫方法,称为独立集的目标免疫。当独立集中免疫节点度数和等于全网络的目标免疫节点度数和时,独立集的目标免疫策略比全网络的目标免疫更加有效,并从网络结构的角度阐明这一结果出现的原因。随后比较了独立集中的随机免疫策略与全网络的随机免疫策略,实验结果表明对独立集的随机免疫并没有去掉更多的高度数节点。对于经典的SI传播模型,所有节点都只有两种状态:易染状态和感染状态。在复杂网络免疫策略的研究中,SI传播模型与SIR、SIS传播模型相比较,使用SI传播模型对于免疫策略的研究将更加有利。

最大独立集算法

本文提出了网络中的一种特殊结构──负包络图。原来是它包含了网络的最小截，因而制约了网络的最大流量。研究表明，负包络图也是关于网络最大独立集的充要条件。本文以既有的最大流算法为手段，利用这个充要条件，给出了在偶网络上求最大独立集的有效算法，而且也给出了在奇网络上求最大独立集的递归算法。