一种基于拓扑势的网络社区发现方法

从数据场思想出发,提出了一种基于拓扑势的社区发现算法.该方法引入拓扑势描述网络节点间的相互作用,将每个社区视为拓扑势场的局部高势区,通过寻找被低势区域所分割的连通高势区域实现网络的社区划分.理论分析与实验结果表明,该方法无须用户指定社区个数等算法参数,能够揭示网络内在的社区结构及社区间具有不确定性的重叠节点现象.算法的时间复杂度为O(m+n^3/γ)～O(n²),n为网络节点数,m为边数,2<γ<3为一个常数.     

虫孔路由Mesh上的连通分量算法及其应用

用倍增技术在带有Wormhole路由技术的n×n二维网孔机器上提出了时间复杂度为O(log²n)的连通分量和传递闭包并行算法,并在此基础上提出了一个时间复杂度为O(log³n)的最小生成树并行算法.这些都改进了Store-and-Forward路由技术下的时间复杂度下界O(n).同其他运行在非总线连接分布式存储并行计算机上的算法相比,此连通分量和传递闭包算法的时间复杂度是最优的.     

光RP(k)网络上Hypercube通信模式的波长指派算法

波长指派是光网络设计的基本问题,设计波长指派算法是洞察光网络通信能力的基本方法.基于光RP(k)网络,讨论了其波长指派问题. 含有N=2ⁿ个节点的Hypercube通信模式,构造了节点间的一种排列次序Xn,并设计了RP(k)网络上的波长指派算法.在构造该算法的过程中,得到了在环网络上实现n维Hypercube通信模式的波长指派算法.这两个算法具有较高的嵌入效率.在RP(k)网络上,实现Hypercube通信模式需要max{2,「5(2^n-5/3」}个波长.而在环网络上,实现该通信模式需要复用(N/3+N/12(个波长,比已有算法需要复用「N/3+N/4」个波长有较大的改进.这两个算法对于光网络的设计具有较大的指导价值.     

一类实际网络中的最小截算法

讨论了节点和边都有容量限制的无向平面网络中的两点间的最小截问题.传统方法是把节点和边都有容量的网络中的最小截问题转化为只有边有容量的问题,但该方法用在平面网络时不能保持网络的平面性,因此网络的平面性不能得到利用.使用传统方法的计算时间为O(n²logn)(其中n为网络的节点数).给出了可以充分利用网络平面性的方法.对源和汇共面的s-t平面网络,把最小截问题转化为平面图上两点间的最短路径问题,从而可以得到O(n)时间的算法;对一般的平面网络,给出了新的将节点和边都有容量的问题转化为仅边有容量问题的方法,这种转化方法不破坏网络的平面性,从而可以利用平面网络中仅边有容量问题的计算方法,使原问题在O(nlogn)时间内获得解决.     

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

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

基于重要度贡献的无标度网络节点评估方法

针对无标度网络的节点重要度评估问题,通过分析节点的邻居数量与其邻居间的拓扑结构,得到节点的结构洞重要性指标,再融合相邻节点的K核重要性指标值来确定相邻节点间的重要度贡献,以此表征相邻节点的局部信息;在此基础上,再结合表征节点位置信息的节点自身的K核重要性,从而提出一种基于节点间重要度贡献关系来评估无标度网络的节点重要度的方法.该方法综合考虑了节点的结构洞特征和K核中心性特征来确定节点的重要度,同时兼顾到了网络的局部和全局重要性.理论分析表明,此方法的时间复杂度仅为o（n²）.与其他几种算法仿真对比的结果表明,该方法可行有效,拥有理想计算能力,适用无标度网络.     

半动态矩形交查询算法

本文讨论了动态矩形交查询算法.文中介绍了两个半动态矩形查询的新算法，它们分别基于一维数据结构和二维数据结构.一维查询算法的查询时间复杂度是O（logM＋k′），更新时间复杂度是O（logMlogn），空间复杂度是O（nlogM/）.二维查询算法的查询时间复杂度是O（log²M＋k），更新时间复杂度是O（log²Mlogn），空间复杂度是O（nlog²M）.本文分别实现了这两个算法，通过对它们的性能进行比较，发现一维查询算法是一种高效、实用的算法.     

在消息传递并行机上的高效的最小生成树算法

基于传统的Borǔ vka串行最小生成树算法,提出了一个在消息传递并行机上的高效的最小生成树算法.并且采用3种方法来提高该算法的效率,即通过两趟合并及打包收缩的方法来减少通信开销,通过平衡数据分布的办法使各个处理器的计算量平衡.该算法的计算和通信复杂度分别为O(n²/p)和O((t_sp+t_wn)n/p).在曙光-1000并行机上运行的实际效果是,对于有10 000个顶点的稀疏图,通过16个节点的运行加速比是12.     

基于新约束图模型的布图规划和布局算法

布图规划和布局构形的表示是基于随机优化方法的布图规划和布局算法的核心问题.针对Non-slicing结构的布图规划和布局,提出了一种新的基于约束图表示的模型.基于该模型及其性质,可以得到近似O(n)时间复杂度的有效的布局算法.通过引入变形网格的假设,得到了一种新的更加精确的Non-Slicing结构的表示模型:梯形网格模型.其空间复杂度为n(3+lg[n]),时间复杂度为O(n),解空间规模为n!2^3n-7.已经证明,梯形网格模型可以表示所有的Slicing结构的布局,同时又可以有效地表示Non-Slicing结构的布局,而时间复杂度与Slicing表示相同.实验结果表明,该表示优于刚刚发表的O-tree模型.梯形网格模型是一种拓扑模型,而O-tree的表示依赖于模块的尺寸,因而梯形网格能更有效地处理含有软模块的的布图规划问题.     

一类可分离SAT问题的O(1.890n)精确算法

布尔可满足性问题（SAT）是指对于给定的布尔公式,是否存在一个可满足的真值指派.这是第1个被证明的NP完全问题,一般认为不存在多项式时间算法,除非P=NP.学者们大都研究了子句长度不超过k的SAT问题（k-SAT）,从全局搜索到局部搜索,给出了大量的相对有效算法,包括随机算法和确定算法.目前,最好算法的时间复杂度不超过O（（2-2/k）ⁿ）,当k=3时,最好算法时间复杂度为O（1.308ⁿ）.而对于更一般的与子句长度k无关的SAT问题,很少有文献涉及.引入了一类可分离SAT问题,即3-正则可分离可满足性问题（3-RSSAT）,证明了3-RSSAT是NP完全问题,给出了一般SAT问题3-正则可分离性的O（1.890ⁿ）判定算法.然后,利用矩阵相乘算法的研究成果,给出了3-RSSAT问题的O（1.890ⁿ）精确算法,该算法与子句长度无关.     

Complexity of Clausal Constraints Over Chains

We investigate the complexity of the satisfiability problem of constraints over finite totally ordered domains. In our context, a clausal constraint is a disjunction of inequalities of the form x≥d and x≤d. We classify the complexity of constraints based on clausal patterns. A pattern abstracts away from variables and contains only information about the domain elements and the type of inequalities occurring in a constraint. Every finite set of patterns gives rise to a (clausal) constraint satisfaction problem in which all constraints in instances must have an allowed pattern. We prove that every such problem is either polynomially decidable or NP-complete, and give a polynomial-time algorithm for recognizing the tractable cases. Some of these tractable cases are new and have not been previously identified in the literature.     

Consistency techniques for continuous constraints

We consider constraint satisfaction problems with variables in continuous, numerical domains. Contrary to most existing techniques, which focus on computing one single optimal solution, we address the problem of computing a compact representation of the space of all solutions admitted by the constraints. In particular, we show how globally consistent (also called decomposable) labelings of a constraint satisfaction problem can be computed.Our approach is based on approximating regions of feasible solutions by 2 ^k -trees, a representation commonly used in computer vision and image processing. We give simple and stable algorithms for computing labelings with arbitrary degrees of consistency. The algorithms can process constraints and solution spaces of arbitrary complexity, but with a fixed maximal resolution.Previous work has shown that when constraints are convex and binary, path-consistency is sufficient to ensure global consistency. We show that for continuous domains, this result can be generalized to ternary and in fact arbitrary n-ary constraints using the concept of (3,2)-relational consistency. This leads to polynomial-time algorithms for computing globally consistent labelings for a large class of constraint satisfaction problems with continuous variables.     

High-Order Consistency in Valued Constraint Satisfaction

k-consistency operations in constraint satisfaction problems (CSPs) render constraints more explicit by solving size-k subproblems and projecting the information thus obtained down to low-order constraints. We generalise this notion of k-consistency to valued constraint satisfaction problems (VCSPs) and show that it can be established in polynomial time when penalties lie in a discrete valuation structure.A generic definition of consistency is given which can be tailored to particular applications. As an example, a version of high-order consistency (face consistency) is presented which can be established in low-order polynomial time given certain restrictions on the valuation structure and the form of the constraint graph.     

Neural networks for finite constraint satisfaction

Constraint Satisfaction Problems (CSPs) are in general NP-hard, and a general deterministic polynomial time algorithm is not known. They play a central role in real-life problems. The satisfaction of a Conjunctive Normal Form (CNF-SAT)is the core of any CSP. We present a new modelisation technique for any CSP with finite variable domains, and, in particular, for solving CNF-SAT. The knowledge representation is based on two fundamental types of constraint: the choice constraint, and the exclusion constraint. These models are then implemented by means of several different neural networks, some based on backpropagation learning and others on different procedures. All these networks are trained through a supervised procedure, and learn to efficiently solve CNF-SAT. The results of significant tests are described: they show that some networks can effectively solve the proposed problems.     

Boosting Search with Variable Elimination in Constraint Optimization and Constraint Satisfaction Problems

There are two main solving schemas for constraint satisfaction and optimization problems: i) search, whose basic step is branching over the values of a variables, and ii) dynamic programming, whose basic step is variable elimination. Variable elimination is time and space exponential in a graph parameter called induced width, which renders the approach infeasible for many problem classes. However, by restricting variable elimination so that only low arity constraints are processed and recorded, it can be effectively combined with search, because the elimination of variables may reduce drastically the search tree size.In this paper we introduce BE-BB(k), a hybrid general algorithm that combines search and variable elimination. The parameter k controls the tradeoff between the two strategies. The algorithm is space exponential in k. Regarding time, we show that its complexity is bounded by k and a structural parameter from the constraint graph. We provide experimental evidence that the hybrid algorithm can outperform state-of-the-art algorithms in constraint satisfaction, Max-CSP and Weighted CSP. Especially in optimization tasks, the advantage of our approach over plain search can be overwhelming.     

Periodic Constraint Satisfaction Problems: Tractable Subclasses

We study a generalization of the constraint satisfaction problem (CSP), the periodic constraint satisfaction problem. An input instance of the periodic CSP is a finite set of generating constraints over a structured variable set that implicitly specifies a larger, possibly infinite set of constraints; the problem is to decide whether or not the larger set of constraints has a satisfying assignment. This model is natural for studying constraint networks consisting of constraints obeying a high degree of regularity or symmetry. Our main contribution is the identification of two broad polynomial-time tractable subclasses of the periodic CSP.     

Optimal Distributed Arc-Consistency

This paper presents DisAC-9, the first optimal distributed algorithm performing the arc-consistency of a constraint network. Our method is optimal according to the number of message passing operations. This algorithm can firstly, give speed-up over the fastest central arc-consistency algorithms; secondly, achieve the fast processing of distributed constraint satisfaction problems (DCSP). Experimental results include classical benchmark and large hard randoms problems. These results allow us to show that the phase transition phenomenon of distributed arc-consistency is closely related to the granularity of the distributed system. The consequences of this analysis are showed to be very important for the future of distributed constraint satisfaction.     

A Repeated-Update Problem in the DeltaBlue Algorithm

We observe a repeated-update problem in the process of updating walkabout strengths of the DeltaBlue algorithm, which is known as a fast constraint solving method based on local propagation. According to the basic references on the DeltaBlue algorithm, the time complexity of the planning phase is described as O(MN) for a constraint problem such that the number of constraints is N and the maximum number of methods a constraint has is M . We, however, point out that the time complexity is not O(MN) using a very simple example. In this example, the time complexity is exponential order for N . Then we present a corrected DeltaBlue algorithm whose time complexity is O(EN ²) for a constraint problem such that the number of constraints is N and the maximum number of variables a constraint has is E . Finally we measure the performance of the corrected DeltaBlue algorithm using two benchmarks.     

Boosting MUC extraction in unsatisfiable constraint networks

One very fertile domain of applied Artificial Intelligence is constraint solving technologies. Especially, constraint networks that concern problems that can be represented using discrete variables, together with constraints on allowed instantiation values for these variables. Every solution to a constraint network must satisfy every constraint. When no solution exists, the user might want to know the actual reasons leading to the absence of global solution. In this respect, extracting mucs (Minimal Unsatisfiable Cores) from an unsatisfiable constraint network is a useful process when causes of unsatisfiability must be understood so that the network can be re-engineered and relaxed to become satisfiable. Despite bad worst-case computational complexity results, various muc-finding approaches that appear tractable for many real-life instances have been proposed. Many of them are based on the successive identification of so-called transition constraints. In this respect, we show how local search can be used to possibly extract additional transition constraints at each main iteration step. In the general constraint networks setting, the approach is shown to outperform a technique based on a form of model rotation imported from the sat-related technology and that also exhibits additional transition constraints. Our extensive computational experimentations show that this enhancement also boosts the performance of state-of-the-art DC(WCORE)-like MUC extractors.     

Properties of tree convex constraints

It is known that a tree convex network is globally consistent if it is path consistent. However, if a tree convex network is not path consistent, enforcing path consistency on it may not make it globally consistent. In this paper, we investigate the properties of some tree convex constraints under intersection and composition. As a result, we identify a sub-class of tree convex networks that are locally chain convex and strictly union closed. This class of problems can be made globally consistent by arc and path consistency and thus is tractable. Interestingly, we also find that some scene labeling problems can be modeled by tree convex constraints in a natural and meaningful way.