Hardness results for covering arrays avoiding forbidden edges and error-locating arrays

Covering arrays avoiding forbidden edges (CAFEs) are used in testing applications (software, networks, circuits, drug interaction, material mixtures, etc.) where certain combinations of parameter values are forbidden. Danziger et al. (2009) [8] have studied this problem and shown some computational complexity results. Around the same time, Martinez et al. (2009) [19] defined and studied error-locating arrays (ELAs), which are closely related to CAFEs. Both papers left some computational complexity questions. In particular, these papers showed polynomial-time solvability of the existence of CAFEs and ELAs for binary alphabets (g=2), and the NP-hardness of these problems for g≥5. In this paper, we prove that optimizing CAFEs and ELAs is indeed NP-hard even when restricted to the case of binary alphabets, using a reduction from edge clique covers of graphs (ECCs). We also provide a hardness of approximation result. We explore important relationships between ECCs and CAFEs and give some new bounds for uniform ECCs and CAFEs.     

一种新型的桥梁健康检测算法

针对大型桥梁故障诊断问题,提出一种新型高效的诊断算法。该算法将一座桥梁系统看成由大量的“团”组成,每个“团”由一个挠度检测点及其相应的传感器构成,具体分3个阶段进行：(1)受到“挠度共振”的启发,根据线性回归预测理论建立一个测试模型;(2)利用测试模型对所有“团”进行测试;(3)在测试基础上进行综合分析得出检测结果。对真实桥梁进行检测实验,结果表明该方法故障检测率达81.8%。     

求解最大团问题的并行多层图划分方法

在当今大数据环境下,针对图中节点的海量性和分析的复杂性对最大团问题的研究在速度和精度上都提出了更高要求的问题,提出求解最大团问题的并行多层图划分方法（PMGP_SMC）。首先,提出一种新的多层图划分（MGP）方法,在保持原有图的团结构不被破坏的情况下对大规模图例划分产生子图,并对规模较大的子图进行多层图划分,进一步缩小子图规模,并且应用GraphX图计算框架实现MGP,形成并行MGP（PMGP）方法;然后,依据划分后的子图规模,减少了惩罚值局部搜索算法（PBLS）的迭代次数,提出基于速度优化的PBLS（SPBLS）来求解划分后的各个子图的最大团;最后,将PMGP和SPBLS相结合形成PMGP_SMC。采用Stanford大规模数据集运行测试,实验结果表明,PMGP相比并行单层图划分方法（PSGP）,求得的最大子图规模能缩小至原来的1/100,平均子图规模能缩小至原来的1/2;PMGP_SMC相比求解最大团问题的PSGP（PSGP_SMC）,总体时间缩短至原来的1/100,并且PMGP_SMC求解最大团的精度和基于极大团枚举求解最大团问题的并行多层图划分方法（PMGP_MCE）一致。PMGP_SMC能够快速精准地求解大规模图例的最大团。     

S-Clique：属性约束的极大团枚举

极大团枚举是图论中一个基础性研究问题,并被广泛应用到社交网络等各种领域。现实生活中的图数据不仅规模大,而且顶点上往往都带有重要的属性信息。然而当前极大团枚举算法主要关注图的结构特性,很大程度上忽视了顶点上的属性信息。提出一种结合图的结构特性和顶点属性的极大团S-Clique：各顶点属性值集合的交集的大小满足最小支持度的极大团,并提出了它的应用场景。针对S-Clique问题,提出一种有效求解算法SCE-PE,其充分利用父结点等价剪枝策略。同时重新优化顶点访问次序提出SCE-PES,进一步提高SCE-PE算法性能。实验结果表明,算法SCE-PES的效率较SCE-PE提高了40%左右。     

A fast iterative-clique percolation method for identifying functional modules in protein interaction networks

Accumulating evidence suggests that biological systems are composed of interacting, separable, functional modules-groups of vertices within which connections are dense but between which they are sparse. Identifying these modules is likely through capturing the biologically meaningful interactions. In recent years, many algorithms have been developed for detecting such structures. These algorithms, however, are computationally demanding, which limits their applications. In this paper, we propose a fast iterative-clique percolation method (ICPM) for identifying overlapping functional modules in protein-protein interaction (PPI) networks. Our method is based on clique percolation method (CPM), and it not only considers the degree of nodes to minimize the search space (the vertices in k-cliques must have the degree of k − 1 at least), but also converts k-cliques to (k − 1)-cliques. It finds k-cliques by appending one node to (k − 1)-cliques. By testing our method on PPI networks, our analysis of the yeast PPI network suggests that most of these modules have well-supported biological significance.     

一种求解最大团问题的蚁群算法

将最大团问题看作子集类问题,提出了基于子集类问题的特殊蚁群算法用于求解最大团问题。该算法将信息素和局部启发信息与图的顶点相关联,而不再与边相关联,从而提高算法的运行速度。仿真实验研究表明,该算法较传统求解最大团问题的蚁群算法有着更短的运行时间,较强的求解能力,更适合用于求解最大团问题。     

一种基于贝叶斯网络的作战重心评估模型

作战重心（Center of Gravity）是指战役体系中敌我双方的关键环节。作战重心评估是一个经验性、模糊性的过程。贝叶斯网络作为一种不确定知识表示模型,具有概率论及图论基础,对于解决复杂系统决策问题具有较强的优势,适合用于作战重心评估。文中提出并实现了一种基于贝叶斯网络推理的作战重心评估模型。通过该模型,可以定量地评估各个环节对于证据的重要程度,从而确定该作战过程中的作战重心。文中使用联合树（Clique Tree）算法进行贝叶斯网络精确推理,并详细阐述了推理过程中联合树建立,消息传递的过程。最后通过实例验证,基于贝叶斯网络推理的模型能够有效地对作战重心进行定量的评估。     

一种基于极大团的蛋白质相互作用预测方法

针对大规模、高通量方法识别出的蛋白质相互作用数据集包含噪声较高的问题,根据蛋白质相互作用网络中噪声数据的特点和网络拓扑属性,提出了一种基于极大团的相互作用预测方法以提高识别出的这种数据集的可靠性.该方法通过蛋白质与蛋白质团之间的关联程度来预测蛋白质间是否存在相互作用,同时结合噪声数据在网络中的特点将预测结果放大并将伪相互作用分离出来,最后可获得可靠性较高的预测数据集.实验结果显示,所提出的方法不仅可以预测更多相互作用而且具有更高的可靠性.     

无线城市数据中的社团发现方法

为了在缺失社交关系的无线城市接入日志中挖掘频繁共现的社团结构。提出了一种基于无向有权图的社团发现方法：团搜索（Clique Search）。该算法将日志数据映射到图空间,通过挖掘其中的团来对潜在的社团关系进行挖掘。相较于传统算法,该算法显著减小了运算时间复杂度与空间复杂度。实验结果表明,随着输入数据集规模的增长,该算法仍然能够在常数级别时间内完成计算。算法中的参数[δ]对结果社团中成员的联系紧密度影响比较明显,使用不同的[δ]值可以满足不同应用的需求。     

SAE AS6802协议研究及模块化仿真平台设计

分析安全关键领域的时间触发网络协议SAE AS6802与时间同步算法技术,分别对同步流程、时间同步角色、时序保持算法、集中控制算法、时钟纠正算法、同/异步派系检测算法以及通道择优方法等进行研究,归纳时间同步精度的影响因素。在此基础上,设计一种时间同步算法IP核,并构建基于SystemVerilog的模块化仿真验证平台。利用该平台对时间同步算法进行RTL级仿真,结果验证了该时间同步算法的正确性,其同步精度保持在亚微秒级,满足下一代高安全关键领域的应用要求。