A new algorithm for error-tolerant subgraph isomorphism detection

We propose a new algorithm for error-correcting subgraph isomorphism detection from a set of model graphs to an unknown input graph. The algorithm is based on a compact representation of the model graphs. This representation is derived from the set of model graphs in an off-line preprocessing step. The main advantage of the proposed representation is that common subgraphs of different model graphs are represented only once. Therefore, at run time, given an unknown input graph, the computational effort of matching the common subgraphs for each model graph onto the input graph is done only once. Consequently, the new algorithm is only sublinearly dependent on the number of model graphs. Furthermore, the new algorithm can be combined with a future cost estimation method that greatly improves its run-time performance     

采用元组聚类的增量式数据分区方法

数据分区是提升数据库可扩展能力的有效方法。在事务查询密集的系统中,合理的分区策略可减少分布式事务查询数量,并提高事务查询响应速度。提出了一种基于元组聚类的增量式分区方法,通过将元组聚簇和采用分区感知的数据筛选策略来降低算法的复杂度。首先依据时间窗口模型聚类元组,并构建簇节点图,然后利用分区感知策略对图进行删减,最后采用图划分算法对图进行子图划分来得到分区。与现有方法相比,该方法减少了分区响应时间,保证了较少的分布式事务数量,并提高了分区事务查询速度。     

Strongly connected components based efficient computation of page rank

In this paper, an efficient page rank (PR) exact algorithm is proposed, which can improve the computation efficiency without sacrificing results accuracy. The existing exact algorithms are generally based on the original power method (PM). In order to reduce the number of I/Os required to improve efficiency, they partition the big graph into multiple smaller ones that can be totally fitted in memory. The algorithm proposed in this paper can further reduce the required number of I/Os. Instead of partitioning the graph into the general subgraphs, our algorithm partitions graph into a special kind of subgraphs: SCCs (strongly connected components), the nodes in which are reachable to each other. By exploiting the property of SCC, some theories are proposed, based on which the computation iterations can be constrained on these SCC subgraphs. Our algorithm can reduce lots of I/Os and save a large amount of computations, as well as keeping the results accuracy. In a word, our algorithm is more efficient among the existing exact algorithms. The experiments demonstrate that the algorithms proposed in this paper can make an obvious efficiency improvement and can attain high accurate results.     

LESS-mapping: Online environment segmentation based on spectral mapping

Given the features obtained from a sequence of consecutively acquired sensor readings, this paper proposes an on-line algorithm for unsupervisedly detecting a transition on this sequence, i.e. the frame that divides the sequence into two tightly related parts that are dissimilar between them. Contrary to recently proposed approaches that address this partitioning problem dealing with a sequence of robot’s poses, our proposal considers each individual feature as a node of an incrementally built graph whose edges link two nodes if their associated features were simultaneously observed. These graph edges carry non-negative weights according to the locality of the features. Given a feature, its locality defines the set of features that has been observed simultaneously with it at least once. At each execution of the algorithm, the feature-based graph is split into two subgraphs using a normalized spectral clustering algorithm. The obtained partitions correspond to those parts in the environment that share the minimum amount of information. If this graph partition is validated, the algorithm determines that there is a significant change on the perceived scenario, assuming that a transition area has been traversed. In a map partitioning framework, we have tested the proposed approach in real environments where features are obtained using 2D laser sensors or vision (stereo and monocular cameras). The statistical evaluation of the experimental results demonstrates the performance of the proposal.     

基于L-Metric重叠子图发现的B细胞表位预测模型

针对现有表位预测方法对抗原中存在的重叠表位预测能力不佳的问题,提出了将基于局部度量（L-Metric）的重叠子图发现算法用于表位预测的模型。首先,利用抗原上的表面原子构建原子图并升级为氨基酸残基图;然后,利用基于信息流的图划分算法将氨基酸残基图划分为互不重叠的种子子图,并使用基于L-Metric的重叠子图发现算法对种子子图进行扩展以得到重叠子图;最后,利用由图卷积网络（GCN）和全连接网络（FCN）构建的分类模型将扩展后的子图分类为抗原表位和非抗原表位。实验结果表明,所提出的模型在相同数据集上的F_{\mathrm{1}}值与现有表位预测模型DiscoTope 2、ElliPro、EpiPred和Glep相比分别提高了267.3%、57.0%、65.4%和3.5%。同时,消融实验结果表明,所提出的重叠子图发现算法能够有效改善预测能力,使用该算法的模型相较于未使用该算法的模型的F_{\mathrm{1}}值提高了19.2%。     

Event‐triggered MPC design for distributed systems toward global performance

This paper studies the coordination control problem of stabilizing large‐scale dynamically coupled systems via a novel event‐triggered distributed model predictive control (DMPC) approach. In order to achieve global performance, certain constraints relevant to the triggering instant are imposed on the DMPC optimization problem, and triggering mechanisms are designed by taking into account coupling influences. Specifically, the triggering conditions derived from the feasibility and stability analysis are based on the local subsystem state and the information received from its neighbors. Based on these triggering mechanisms, the event‐triggered DMPC algorithm is built, and a dual‐mode strategy is adopted. As a result, the controllers solve the optimization problem and coordinate with each other asynchronously, which reduces the amount of communication and lowers the frequency of controller updates while achieving global performance. The recursive feasibility of the proposed event‐triggered DMPC algorithm is proved, and sufficient parameter conditions about the prediction horizon and the triggering threshold are established. It shows that the system state can be gradually driven into the terminal set under the proposed strategy. Finally, an academic example and a realistic simulation problem to the water level of a 4‐tank system are provided to verify the effectiveness of the proposed algorithm.     

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

在当今大数据环境下,针对图中节点的海量性和分析的复杂性对最大团问题的研究在速度和精度上都提出了更高要求的问题,提出求解最大团问题的并行多层图划分方法（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能够快速精准地求解大规模图例的最大团。     

Perceptual grouping of line features in 3-D space: a model-based framework

In this paper, we propose a novel model-based perceptual grouping algorithm for the line features of 3-D polyhedral objects. Given a 3-D polyhedral model, perceptual grouping is performed to extract a set of 3-D line segments which are geometrically consistent with the 3-D model. Unlike the conventional approaches, grouping is done in 3-D space in a model-based framework. In our unique approach, a decision tree classifier is employed for encoding and retrieving the geometric information of the 3-D model. A Gestalt graph is constructed by classifying input instances into proper Gestalt relations using the decision tree. The Gestalt graph is then decomposed into a few subgraphs, yielding appropriate groups of features. As an application, we suggest a 3-D object recognition system which can be accomplished by selecting a best-matched group. In order to evaluate the performance of the proposed algorithm, experiments are carried out on both synthetic and real scenes.     

基于顶点组重分配的动态增量图划分算法

图划分是分布式图计算中的一项基础工作, 其作用是将大规模图进行划分并分配到集群中的不同机器上. 图划分的质量对分布式图计算的性能有很大的影响, 其目标是降低负载平衡和最小化边割. 如今, 现实中的图数据通常呈动态增长态势, 这就需要一种能够处理动态增量图的划分方法, 在图数据动态增长的过程中确保划分的质量不受影响. 目前虽然有一些动态图划分算法被提出, 但它们不能同时专注于实时处理动态变化和获得高质量的划分结果. 提出基于顶点组重分配的动态增量图划分算法(ED-IDGP)来解决大规模动态增量图的划分问题. 在ED-IDGP算法中, 设计实时处理4种不同单元更新类型的动态处理器, 并在每次处理完单元更新后通过在分区发生动态变化的附近执行局部优化器进一步提高图划分的质量. 在ED-IDGP的局部优化器中, 利用基于改进标签传播算法的顶点组搜索策略搜索顶点组, 并利用提出的顶点组移动增益公式衡量最有益的顶点组, 将该顶点组移动到目标分区中做优化. 在真实数据集上从不同的角度和度量指标评估了ED-IDGP算法的性能和效率.     

硬件加速功能验证问题的DAG划分算法

功能验证是超大规模集成电路(very large scale integration, VLSI)设计的一个基本环节. 随着超大规模电路的普及与发展, 在单处理器上对整个电路进行功能验证在可行性和效率上都存在较大的缺陷. 基于硬件加速器的功能验证是将整个电路划分成若干个规模更小的子电路; 然后在多个硬件处理器上并行的执行功能验证. 当电路划分结果的并行性较优时可提高功能验证的效率, 缩短时间周期. 类似电路设计中的其他划分问题, 用于硬件加速功能验证的电路划分问题可以被抽象成图划分问题. 相较于传统图划分问题, 硬件加速功能验证的划分问题还需要保证较小的模拟深度和较高的调度并行性. 为了满足硬件加速功能验证的划分需求, 提出了一种基于传统多级图划分策略的有效算法. 该算法结合调度思想, 利用电路的关键路径信息和时序信息, 将硬件加速功能验证问题转化为有向无环图的多级划分问题. 随机电路网表数据的实验结果表明, 所构造的算法可以有效的减少关键路径长度并且不会引起切边数的增长恶化.     

基于任务-资源分配图优化选取的网格依赖任务调度

任务调度是网格应用系统获得高性能的关键.网格计算中一个大型的应用程序往往被分解为具有依赖关系的多个任务.在资源个体差异较大、广域互连的网格环境下任务间的依赖关系对传统的调度策略提出了新的挑战.任务调度的主要工作是为任务分配资源以及确定任务的执行次序,将依赖任务的可能的资源分配方案表示为任务-资源分配图（T-RAG）,在该图的基础上提出了基于T-RAG优化选取的依赖任务调度模型,将依赖任务调度问题转化为图的优化选取问题,解析最优任务-资源分配图可以同时确定资源分配方案和任务的执行次序即为最优调度方案.最后,实现了基于该模型的任务调度算法,该算法与ILHA算法的对比分析表明,在资源差异较大及任务间存在大量数据传输的情况下所提出的算法更优.     

一种新的频繁子图挖掘算法

传统Aprior频繁子图挖掘算法中存在大量冗余子图.针对该问题,提出一种新的频繁子图挖掘算法(GAI).介绍一种三层MADI索引结构,用于存储图集的信息,以减少图集的扫描次数,通过扩展ETree树构造频繁子图,并用表来存储候选子图,避免扩展过程中冗余图的产生以及对整个数据库的扫描,从而简化支持度的计算,提高图/子图同构...     

属性公平的异质信息网络上的社区搜索算法

近年来,异质信息网络上的社区搜索问题已经吸引了越来越多的关注,而且被广泛应用在图数据分析工作中.但是现有异质信息网络上的社区搜索问题都没有考虑子图上属性的公平性.将属性的公平性与异质信息网络上的kPcore挖掘问题相结合,提出了基于属性公平的异质信息网络上的极大core挖掘问题.针对该问题,首先提出了一个子图模型FkPcore.当对FkPcore进行枚举时,基础算法Basic-FkPcore遍历了所有路径实例,并枚举了大量k Pcore及其子图.为了提高算法效率,提出了Adv-FkPcore算法,以避免在枚举FkPcore时对所有的kPcore及其子图进行判断.另外,为了提高点的P＿neighbor的获取效率,提出了结合点标记的遍历方法(traversalmethod with vertex sign, TMS),并基于TMS算法提出了FkPcore枚举算法Opt-FkPcore.在异质信息网络数据集上进行的大量实验证明了所提方法的有效性和效率.     

一种基于二部图谱划分的聚类集成方法

将二部图模型引入聚类集成问题中,使用二部图模型同时建模对象集和超边集,充分挖掘潜藏在对象之间的相似度信息和超边提供的属性信息.设计正则化谱聚类算法解决二部图划分问题,在低维嵌入空间运行K-means++算法划分对象集,获得最终的聚类结果.在多组基准数据集上进行实验,实验结果表明所提出方法不仅能获得优越的结果,而且具有较高的运行效率.     

基于过程划分技术的服务组合拆分方法

针对集中式服务组合内的中心控制器瓶颈问题,提出一种基于过程划分技术的非集中式服务组合构建方法。首先,利用类型有向图对业务过程进行建模;然后,基于图转换的方法提出分组算法,根据分组算法对过程模型进行拆分;最后,根据拆分后的结果来构建非集中式服务组合。经实验测试,分组算法对模型1的耗时与单线程算法相比降低了21.4%,构建的非集中式服务组合拥有更低响应时间和更高吞吐量。实验结果表明,所提方法能有效地拆分服务组合中的业务过程,所构建的非集中式服务组合能提升服务性能。     

最大频繁子图挖掘算法研究

随着图的广泛应用,图的规模不断扩大,因此提高频繁子图挖掘效率势在必行。本文针对频繁子图挖掘所产生的庞大的结果集,提出了一个最大频繁子图挖掘算法MFME,从而极大地减少了结果集的数量。MFME使用了映射的思想将图集中的边映射到边表中并在此表上进行子图挖掘,有效地提高了算法的效率。实验结果表明,MFME的效率较经典算法SPIN有明显提高。     

Efficient algorithm for graph-partitioning problem using a problem transformation method

This paper shows that the uniform k-way partitioning problem can be transformed into the max-cut problem using a graph modification technique. An iterative algorith, based on Kernighan-Lin's (KL) method, for partitioning graphs is presented that exploits the problem equivalence property. The algorithm deals with nodes of various sizes without any performance degradation. The computing time per pass of the algorithm is O(itkN²), where N is the number of nodes in the given graph. In practice, only a small number of passes are typically needed, leading to a fast approximation algorithm for k-way partitioning. Experimental results show that the proposed algorithm outperforms the KL algorithm in the quality of solutions. The performance gap between the proposed and KL algorithms becomes much bigger as the amount of size differences between nodes increases.     

A recursion-based broadcast paradigm in wormhole routed networks

A novel broadcast technique for wormhole-routed parallel computers based on recursion is presented in this paper. It works by partitioning the interconnection graph into a number of higher-level subgraphs. Then, we identify the transmission subgraph (TSG) in each subgraph. Both the higher-level subgraphs and the TSGs are recursively defined, i.e., we split each level i subgraph into several level i+1 subgraphs and identify-level i+1 TSGs accordingly. We first split and scatter the source message into the TSG of the original graph. Next, in each recursive round message transmissions are from lower-level TSGs to higher-level TSGs and all transmissions at the same level happen concurrently. The algorithm proceeds recursively from lower-level subgraphs to higher level subgraphs until each highest-level subgraph (a single node) gets the complete message. We have applied this general paradigm to a number of topologies including two or higher dimension mesh/torus and hypercube. Our results show considerable improvements over all other algorithms for a wide range of message sizes under both one-port and all-port models.     

基于Ncut准则的图分割的新算法

针对有权图分割时不能很好解决子图内部耦合度不高的问题,使用可以同时优化子图内部顶点耦合度和子图之间顶点耦合度的Ncut准则,提出了一种新的基于迭代改善策略的RNK分割算法。算法通过不断交换可以改善Ncut值的顶点对优化现有分割。与传统分割算法相比,可以同时保证子图内最大耦合度和子图间最小的耦合度。并提出一种散列技术,提高查找最优交换顶点对的效率。当图为稠密矩阵时,改善效果尤为明显。通过对随机图分割的实验结果表明,该算法较传统的KL算法可以得到更理想的分割结果。     

基于极大团的边缘云节点聚合算法

组合多个边缘云可以向用户提供更强大的云计算服务,在大量边缘云节点集合中选择适当的节点进行组合是一项具有挑战性的任务。该问题被建模成由云节点作为顶点、节点之间的链路作为边的资源拓扑图。云组合的构建过程等同于在该图中选择子图的过程,这是一个NP完全问题。子图的选择策略是决定云组合性能的重要因素,现有的minStar算法贪心地选择节点之间通信延迟最小的子图,将最优资源分配给当前用户,导致了局部最优和全局性能不良的问题。鉴于此,提出基于极大团的边缘云资源分配算法,提取图中的极大团并将其划分为若干互不重叠的规模较小的完全子图,以子图为单位构建资源块,以资源块为单位进行资源的分配。实验结果表明,与minStar算法相比,新算法将全局最大通信延迟降至原来的50%。