Finding near-optimal independent sets at scale

The maximum independent set problem is NP-hard and particularly difficult to solve in sparse graphs, which typically take exponential time to solve exactly using the best-known exact algorithms. In this paper, we present two new novel heuristic algorithms for computing large independent sets on huge sparse graphs, which are intractable in practice. First, we develop an advanced evolutionary algorithm that uses fast graph partitioning with local search algorithms to implement efficient combine operations that exchange whole blocks of given independent sets. Though the evolutionary algorithm itself is highly competitive with existing heuristic algorithms on large social networks, we further show that it can be effectively used as an oracle to guess vertices that are likely to be in large independent sets. We then show how to combine these guesses with kernelization techniques in a branch-and-reduce-like algorithm to compute high-quality independent sets quickly in huge complex networks. Our experiments against a recent (and fast) exact algorithm for large sparse graphs show that our technique always computes an optimal solution when the exact solution is known, and it further computes consistent results on even larger instances where the solution is unknown. Ultimately, we show that identifying and removing vertices likely to be in large independent sets opens up the reduction space—which not only speeds up the computation of large independent sets drastically, but also enables us to compute high-quality independent sets on much larger instances than previously reported in the literature.     

Fast computation of bounds for two-terminal network reliability

In this paper, an algorithm for the fast computation of network reliability bounds is proposed. The evaluation of the network reliability is an intractable problem for very large networks, and hence approximate solutions based on reliability bounds have assumed importance. The proposed bounds computation algorithm is based on an efficient BDD representation of the reliability graph model and a novel search technique to find important minpaths/mincuts to quickly reduce the gap between the reliability upper and lower bounds. Furthermore, our algorithm allows the control of the gap between the two bounds by controlling the overall execution time. Therefore, a trade-off between prediction accuracy and computational resources can be easily made in our approach. The numerical results are presented for large real example reliability graphs to show the efficacy of our approach.     

Greedy maximal independent sets via local limits

The random greedy algorithm for finding a maximal independent set in a graph constructs a maximal independent set by inspecting the graph's vertices in a random order, adding the current vertex to the independent set if it is not adjacent to any previously added vertex. In this paper, we present a general framework for computing the asymptotic density of the random greedy independent set for sequences of (possibly random) graphs by employing a notion of local convergence. We use this framework to give straightforward proofs for results on previously studied families of graphs, like paths and binomial random graphs, and to study new ones, like random trees and sparse random planar graphs. We conclude by analysing the random greedy algorithm more closely when the base graph is a tree.     

Ramsey goodness and beyond

In a seminal paper from 1983, Burr and Erdős started the systematic study of Ramsey numbers of cliques vs. large sparse graphs, raising a number of problems. In this paper we develop a new approach to such Ramsey problems using a mix of the Szemerédi regularity lemma, embedding of sparse graphs, Turán type stability, and other structural results. We give exact Ramsey numbers for various classes of graphs, solving five — all but one — of the Burr-Erdős problems.     

Recognizing graphs without asteroidal triples

We consider the problem of recognizing AT-free graphs. Although there is a simple O(n³) algorithm, no faster method for solving this problem had been known. Here we give three different algorithms which have a better time complexity for graphs which are sparse or have a sparse complement; in particular we give algorithms which recognize AT-free graphs in , , and O(n^2.82+nm). In addition we give a new characterization of graphs with bounded asteroidal number by the help of the knotting graph, a combinatorial structure which was introduced by Gallai for considering comparability graphs.     

Stochastic kronecker graphs

A random graph model based on Kronecker products of probability matrices has been recently proposed as a generative model for large‐scale real‐world networks such as the web. This model simultaneously captures several well‐known properties of real‐world networks; in particular, it gives rise to a heavy‐tailed degree distribution, has a low diameter, and obeys the densification power law. Most properties of Kronecker products of graphs (such as connectivity and diameter) are only rigorously analyzed in the deterministic case. In this article, we study the basic properties of stochastic Kronecker products based on an initiator matrix of size two (which is the case that is shown to provide the best fit to many real‐world networks). We will show a phase transition for the emergence of the giant component and another phase transition for connectivity, and prove that such graphs have constant diameters beyond the connectivity threshold, but are not searchable using a decentralized algorithm. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 38, 453–466, 2011     

Star网络S_5的Hamilton圈分解

最近Star网络和Pancake网络作为超立方体(并行计算机中多处理机互连的一种著名拓扑结构)的替代品而被许多作者研究.这两种网络的一个好的特点是:与超立方体相比较,它们有较小的直径和顶点度.尤其Star网络,更是受到研究人员的极大关注.在本文中:(a)我们提出了一种在这两种网络中找Hamilton圈的新方法.(b)证明了关于Star网络S_n的一个猜想在n=5时是正确的,即给出了S_5的两个边不交的Hamilton圈,且S_5是这两个Hamilton圈的并.     

A perfect matching algorithm for sparse bipartite graphs

This paper considers an algorithm for finding a perfect matching, if there is one, in a bipartite graph G. It is shown that the search for a perfect matching in G may be carried on separately in the strongly connected components of appropriate directed graphs. The algorithm may be particularly useful for block triangularization of very large, sparse, nonsingular matrices.     

一个求解一类投影问题的总体线性收敛的迭代法

所求的解就是c在p上的投影。 对于问题(1.1),He基于求解线性互补问题的投影收缩(PC)法,把投影问题转化为等价的广义线性互补问题,提出了一个求解这类问题的迭代方法。 原始的PC方法只能证明迭代是全局收敛的,而无法估计其收敛速度。为此,[4]和[5]对原始的PC方法作了改进,提出了固定步长的PC法并证明了其收敛速度是线性的。但在实际应用中,固定步长的PC法比原始的PC法慢的多,而且在求步长时,还要估计约束矩阵范数的大小。 本文基于[5]的思想,对于(1.1)提出了一个新的PC方法,该方法是全局线性收敛的。 本文中用到的符号说明如下:x_i表示x的第i个分量。如果u∈(?)且Ω(?)(?)为凸闭集,则P_Ω[u]定义为u到Ω上的投影。特别地,u_+定义为u到非负卦限(?)上的投影,对于一个正定矩阵G,范数||u++G表示(u~TGu)(?)。     

Combining simulated annealing with local search heuristics

We introduce a meta-heuristic to combine simulated annealing with local search methods for CO problems. This new class of Markov chains leads to significantly more powerful optimization methods than either simulated annealing or local search. The main idea is to embed deterministic local search techniques into simulated annealing so that the chain explores only local optima. It makes large, global changes, even at low temperatures, thus overcoming large barriers in configuration space. We have tested this meta-heuristic for the traveling salesman and graph partitioning problems. Tests on instances from public libraries and random ensembles quantify the power of the method. Our algorithm is able to solve large instances to optimality, improving upon local search methods very significantly. For the traveling salesman problem with randomly distributed cities, in a square, the procedure improves on 3-opt by 1.6%, and on Lin-Kernighan local search by 1.3%. For the partitioning of sparse random graphs of average degree equal to 5, the improvement over Kernighan-Lin local search is 8.9%. For both CO problems, we obtain new best heuristics.     

Mining social networks using wave propagation

With the development of modern technology(communication, transportation, etc.), many new social networks have formed and influenced our life. The research of mining these new social networks has been used in many aspects. But compared with traditional networks, these new social networks are usually very large. Due to the complexity of the latter, few model can be adapted to mine them effectively. In this paper, we try to mine these new social networks using Wave Propagation process and mainly discuss two applications of our model, solving Message Broadcasting problem and Rumor Spreading problem. Our model has the following advantages: (1) We can simulate the real networks message transmitting process in time since we include a time factor in our model. (2) Our Message Broadcasting algorithm can mine the underlying relationship of real networks and represent some clustering properties. (3) We also provide an algorithm to detect social network and find the rumor makers. Complexity analysis shows our algorithms are scalable for large social network and stable analysis proofs our algorithms are stable.     

A bandwidth reduction algorithm for L-shaped and Z-shaped grid structured graphs

In this paper, a viable bandwidth reduction algorithm based on graphs for reducing the bandwidth of sparse symmetric matrices, arising from standard L-structured and Z-structured graphs, is presented. Bandwidth results for these matrices are obtained using this algorithm and compared with that of existing algorithms. This algorithm can easily be applied to these matrices while the bandwidths obtained are as good as those obtained with the existing algorithms.     

Lasso变量选择的分布式算法

Lasso是机器学习中比较常用的一种变量选择方法,适用于具有稀疏性的回归问题.当样本量巨大或者海量的数据存储在不同的机器上时,分布式计算是减少计算时间提高效率的重要方式之一.本文在给出Lasso模型等价优化模型的基础上,将ADMM算法应用到此优化变量可分离的模型中,构造了一种适用于Lasso变量选择的分布式算法,证明了...     

Finding minimum height elimination trees for interval graphs in polynomial time

The elimination tree plays an important role in many aspects of sparse matrix factorization. The height of the elimination tree presents a rough, but usually effective, measure of the time needed to perform parallel elimination. Finding orderings that produce low elimination is therefore important. As the problem of finding minimum height elimination tree orderings is NP-hard, it is interesting to concentrate on limited classes of graphs and find minimum height elimination trees for these efficiently. In this paper, we use clique trees to find an efficient algorithm for interval graphs which make an important subclass of chordal graphs. We first illustrate this method through an algorithm that finds minimum height elimination for chordal graphs. This algorithm, although of exponential time complexity, is conceptionally simple and leads to a polynomial-time algorithm for finding minimum height elimination trees for interval graphs.This work was supported by grants from the Norwegian Research Council.     

Topology discovery of sparse random graphs with few participants

We consider the task of topology discovery of sparse random graphs using end‐to‐end random measurements (e.g., delay) between a subset of nodes, referred to as the participants. The rest of the nodes are hidden, and do not provide any information for topology discovery. We consider topology discovery under two routing models: (a) the participants exchange messages along the shortest paths and obtain end‐to‐end measurements, and (b) additionally, the participants exchange messages along the second shortest path. For scenario (a), our proposed algorithm results in a sub‐linear edit‐distance guarantee using a sub‐linear number of uniformly selected participants. For scenario (b), we obtain a much stronger result, and show that we can achieve consistent reconstruction when a sub‐linear number of uniformly selected nodes participate. This implies that accurate discovery of sparse random graphs is tractable using an extremely small number of participants. We finally obtain a lower bound on the number of participants required by any algorithm to reconstruct the original random graph up to a given edit distance. We also demonstrate that while consistent discovery is tractable for sparse random graphs using a small number of participants, in general, there are graphs which cannot be discovered by any algorithm even with a significant number of participants, and with the availability of end‐to‐end information along all the paths between the participants. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Dynamic graph generation for the shortest path problem in time expanded networks

In discrete optimization problems the progress of objects over time is frequently modeled by shortest path problems in time expanded networks, but longer time spans or finer time discretizations quickly lead to problem sizes that are intractable in practice. In convex relaxations the arising shortest paths often lie in a narrow corridor inside these networks. Motivated by this observation, we develop a general dynamic graph generation framework in order to control the networks’ sizes even for infinite time horizons. It can be applied whenever objects need to be routed through a traffic or production network with coupling capacity constraints and with a preference for early paths. Without sacrificing any information compared to the full model, it includes a few additional time steps on top of the latest arcs currently in use. This “frontier” of the graphs can be extended automatically as required by solution processes such as column generation or Lagrangian relaxation. The corresponding algorithm is efficiently implementable and linear in the arcs of the non-time-expanded network with a factor depending on the basic time offsets of these arcs. We give some bounds on the required additional size in important special cases and illustrate the benefits of this technique on real world instances of a large scale train timetabling problem.     

An inexact interior point method for L 1-regularized sparse covariance selection

Sparse covariance selection problems can be formulated as log-determinant (log-det) semidefinite programming (SDP) problems with large numbers of linear constraints. Standard primal–dual interior-point methods that are based on solving the Schur complement equation would encounter severe computational bottlenecks if they are applied to solve these SDPs. In this paper, we consider a customized inexact primal–dual path-following interior-point algorithm for solving large scale log-det SDP problems arising from sparse covariance selection problems. Our inexact algorithm solves the large and ill-conditioned linear system of equations in each iteration by a preconditioned iterative solver. By exploiting the structures in sparse covariance selection problems, we are able to design highly effective preconditioners to efficiently solve the large and ill-conditioned linear systems. Numerical experiments on both synthetic and real covariance selection problems show that our algorithm is highly efficient and outperforms other existing algorithms.     

一个复杂网络中完全子图的搜索算法

现实中很多复杂网络是由完全子图通过公共的节点连接而成的．本文提出了一个复杂网络中完全子图的搜索算法，并通过实例说明了所提算法的有效性．     

An Improved Multi-parametric Programming Algorithm for Flux Balance Analysis of Metabolic Networks

Flux balance analysis has proven an effective tool for analyzing metabolic networks. In flux balance analysis, reaction rates and optimal pathways are ascertained by solving a linear program, in which the growth rate is maximized subject to mass-balance constraints. A variety of cell functions in response to environmental stimuli can be quantified using flux balance analysis by parameterizing the linear program with respect to extracellular conditions. However, for most large, genome-scale metabolic networks of practical interest, the resulting parametric problem has multiple and highly degenerate optimal solutions, which are computationally challenging to handle. An improved multi-parametric programming algorithm based on active-set methods is introduced in this paper to overcome these computational difficulties. Degeneracy and multiplicity are handled, respectively, by introducing generalized inverses and auxiliary objective functions into the formulation of the optimality conditions. These improvements are especially effective for metabolic networks because their stoichiometry matrices are generally sparse; thus, fast and efficient algorithms from sparse linear algebra can be leveraged to compute generalized inverses and null-space bases. We illustrate the application of our algorithm to flux balance analysis of metabolic networks by studying a reduced metabolic model of Corynebacterium glutamicum and a genome-scale model of Escherichia coli. We then demonstrate how the critical regions resulting from these studies can be associated with optimal metabolic modes and discuss the physical relevance of optimal pathways arising from various auxiliary objective functions. Achieving more than fivefold improvement in computational speed over existing multi-parametric programming tools, the proposed algorithm proves promising in handling genome-scale metabolic models.