Electric routing and concurrent flow cutting

We investigate an oblivious routing scheme, amenable to distributed computation and resilient to graph changes, based on electrical flow. Our main technical contribution is a new rounding method which we use to obtain a bound on the ?₁→?₁ operator norm of the inverse graph Laplacian. We show how this norm reflects both latency and congestion of electric routing.     

Multi-label classification via learning a unified object-label graph with sparse representation

Automatic annotation is an essential technique for effectively handling and organizing Web objects (e.g., Web pages), which have experienced an unprecedented growth over the last few years. Automatic annotation is usually formulated as a multi-label classification problem. Unfortunately, labeled data are often time-consuming and expensive to obtain. Web data also accommodate much richer feature space. This calls for new semi-supervised approaches that are less demanding on labeled data to be effective in classification. In this paper, we propose a graph-based semi-supervised learning approach that leverages random walks and ? ₁ sparse reconstruction on a mixed object-label graph with both attribute and structure information for effective multi-label classification. The mixed graph contains an object-affinity subgraph, a label-correlation subgraph, and object-label edges with adaptive weight assignments indicating the assignment relationships. The object-affinity subgraph is constructed using ? ₁ sparse graph reconstruction with extracted structural meta-text, while the label-correlation subgraph captures pairwise correlations among labels via linear combination of their co-occurrence similarity and kernel-based similarity. A random walk with adaptive weight assignment is then performed on the constructed mixed graph to infer probabilistic assignment relationships between labels and objects. Extensive experiments on real Yahoo! Web datasets demonstrate the effectiveness of our approach.     

Processing SPARQL queries over distributed RDF graphs

We propose techniques for processing SPARQL queries over a large RDF graph in a distributed environment. We adopt a “partial evaluation and assembly” framework. Answering a SPARQL query Q is equivalent to finding subgraph matches of the query graph Q over RDF graph G. Based on properties of subgraph matching over a distributed graph, we introduce local partial match as partial answers in each fragment of RDF graph G. For assembly, we propose two methods: centralized and distributed assembly. We analyze our algorithms from both theoretically and experimentally. Extensive experiments over both real and benchmark RDF repositories of billions of triples confirm that our method is superior to the state-of-the-art methods in both the system’s performance and scalability.     

Computer methods for efficient sampling from largely arbitrary statistical distributions

Given a basic pseudo-random number generator which returns uniformly distributed samplesU from the interval (0, 1) and a statistical distribution as defined by its distribution functionF(x). Then the inversion methodX←F ^?1 (U) produces samples fromF(x). A procedure is developed which prepares “guide tables” in order to facilitate this inversion so that sampling becomes efficient for arbitraryF(x). For discrete distributions these tables are small and easy to set up, and the resulting sampling algorithm compares well with known general methods. Continuous distributions require longer set-up times and more space for tables. These are prepared using given probability densitiesf(x). The method can cope with “reasonable”f(x) including most cases which are commonly encountered in statistics. The reported computational experience, on Poisson, Normal, Gamma and Cauchy distributions, indicates that our general routine is almost as fast as the best known sampling algorithms which were specially designed for these distributions.     

A new class of massively parallel direction splitting for the incompressible Navier–Stokes equations

We introduce in this paper a new direction splitting algorithm for solving the incompressible Navier–Stokes equations. The main originality of the method consists of using the operator (I ? ?_xx)(I ? ?_yy)(I ? ?_zz) for approximating the pressure correction instead of the Poisson operator as done in all the contemporary projection methods. The complexity of the proposed algorithm is significantly lower than that of projection methods, and it is shown the have the same stability properties as the Poisson-based pressure-correction techniques, either in standard or rotational form. The first-order (in time) version of the method is proved to have the same convergence properties as the classical first-order projection techniques. Numerical tests reveal that the second-order version of the method has the same convergence rate as its second-order projection counterpart as well. The method is suitable for parallel implementation and preliminary tests show excellent parallel performance on a distributed memory cluster of up to 1024 processors. The method has been validated on the three-dimensional lid-driven cavity flow using grids composed of up to 2 × 10⁹ points.     

Distributed control of LPV systems over arbitrary graphs with communication latency

This paper focuses on spatially distributed control systems where the controller sensing and actuation topology is inherited from that of the plant. Specifically, this paper considers distributed systems composed of discrete‐time linear parameter‐varying subsystems interconnected over general graph structures. These distributed systems are subject to a communication latency of one sampling period, where the information sent by a subsystem at the current time step is received by the target subsystem at the next time step. Analysis and synthesis conditions are derived for control design in this setting using a parameter‐dependent Lyapunov approach with the ?₂‐induced norm as the performance measure. Fast and easy‐to‐implement algorithms are also provided for constructing the controller in real time. The techniques developed are finally applied to a leader‐follower formation problem with intermittent communications.     

2-local 5/4-competitive algorithm for multicoloring triangle-free hexagonal graphs

An important optimization problem in the design of cellular networks is to assign sets of frequencies to transmitters to avoid unacceptable interference. A cellular network is generally modeled as a subgraph of the infinite triangular lattice. The distributed frequency assignment problem can be abstracted as a multicoloring problem on a weighted hexagonal graph, where the weight vector represents the number of calls to be assigned at vertices. In this paper we present a 2-local distributed algorithm for multicoloring triangle-free hexagonal graphs using only the local clique numbers ω₁(v) and ω₂(v) at each vertex v of the given hexagonal graph, which can be computed from local information available at the vertex. We prove that the algorithm uses no more than colors for any triangle-free hexagonal graph G, without explicitly computing the global clique number ω(G). Hence the competitive ratio of the algorithm is 5/4.     

A random riemann zeta function and intersymbol interference

The probability density function (PDF) of z = Σa_nn^?α with n = 1,2,…∞ is considered where {a_n} are independent, identically distributed, zero mean random variables with equally likely values of ± 1. For $\text{1}\text{2}\text{< α ? 1}$ the series diverges; for 1 < α∞ the series converges. For the second situation, the associated characteristic function is bandlimited and we employ a sampling expansion to evaluate the PDF. Both cumulants and moments of z are evaluated. The error probability associated with the sequence is glen considered.     

The Forgiving Graph: a distributed data structure for low stretch under adversarial attack

We consider the problem of self-healing in peer-to-peer networks that are under repeated attack by an omniscient adversary. We assume that, over a sequence of rounds, an adversary either inserts a node with arbitrary connections or deletes an arbitrary node from the network. The network responds to each such change by quick “repairs,” which consist of adding or deleting a small number of edges. These repairs essentially preserve closeness of nodes after adversarial deletions, without increasing node degrees by too much, in the following sense. At any point in the algorithm, nodes v and w whose distance would have been ? in the graph formed by considering only the adversarial insertions (not the adversarial deletions), will be at distance at most ? log n in the actual graph, where n is the total number of vertices seen so far. Similarly, at any point, a node v whose degree would have been d in the graph with adversarial insertions only, will have degree at most 3d in the actual graph. Our distributed data structure, which we call the Forgiving Graph, has low latency and bandwidth requirements. The Forgiving Graph improves on the Forgiving Tree distributed data structure from Hayes et?al. (2008) in the following ways: 1) it ensures low stretch over all pairs of nodes, while the Forgiving Tree only ensures low diameter increase; 2) it handles both node insertions and deletions, while the Forgiving Tree only handles deletions; 3) it requires only a very simple and minimal initialization phase, while the Forgiving Tree initially requires construction of a spanning tree of the network.     

Distributed algorithms for finding and maintaining a k-tree core in a dynamic network

A k-core C_k of a tree T is subtree with exactly k leaves for k?n_l, where n_l the number of leaves in T, and minimizes the sum of the distances of all nodes from C_k. In this paper first we propose a distributed algorithm for constructing a rooted spanning tree of a dynamic graph such that root of the tree is located near the center of the graph. Then we provide a distributed algorithm for finding k-core of that spanning tree. The spanning tree is constructed in two stages. In the first stage, a forest of trees is generated. In the next stage these trees are connected to form a single rooted tree. An interesting aspect of the first stage of proposed spanning algorithm is that it implicitly constructs the (convex) hull of those nodes which are not already included in the spanning forest. The process is repeated till all non root nodes of the graph have chosen a unique parent. We implemented the algorithms for finding spanning tree and its k-core. A core can be quite useful for routing messages in a dynamic network consisting of a set of mobile devices.     

An SDP Primal-Dual Algorithm for Approximating the Lovász-Theta Function

The Lovász ?-function (Lovász in IEEE Trans. Inf. Theory, 25:1–7, 1979) of a graph G=(V,E) can be defined as the maximum of the sum of the entries of a positive semidefinite matrix X, whose trace Tr(X) equals 1, and X _ij =0 whenever {i,j}∈E. This function appears as a subroutine for many algorithms for graph problems such as maximum independent set and maximum clique. We apply Arora and Kale’s primal-dual method for SDP to design an algorithm to approximate the ?-function within an additive error of δ>0, which runs in time $O(\frac{\vartheta ^{2} n^{2}}{\delta^{2}} \log n \cdot M_{e})$ , where ?=?(G) and M _e =O(n ³) is the time for a matrix exponentiation operation. It follows that for perfect graphs G, our primal-dual method computes ?(G) exactly in time O(? ² n ⁵logn). Moreover, our techniques generalize to the weighted Lovász ?-function, and both the maximum independent set weight and the maximum clique weight for vertex weighted perfect graphs can be approximated within a factor of (1+?) in time O(? ^?2 n ⁵logn).     

A Distributed Algorithm for Computing the Node Search Number in Trees

We present a distributed algorithm to compute the node search number in trees. This algorithm extends the centralized algorithm proposed by Ellis et al. (Inf. Comput. 113(1):50–79, 1994). It can be executed in an asynchronous environment, requires an overall computation time of O(nlog?n), and n messages of log?₃ n+4 bits each. The main contribution of this work lies in the data structure proposed to design our algorithm, called hierarchical decomposition. This simple and flexible data structure is used for four operations: updating the node search number after addition or deletion of any tree-edges in a distributed fashion; computing it in a tree whose edges are added sequentially and in any order; computing other graph invariants such as the process number and the edge search number, by changing only initialization rules; extending our algorithms for trees and forests of unknown size (using messages of up to 2log?₃ n+5 bits).     

A unifying framework for ℓ 0-sampling algorithms

The problem of building an ? ₀-sampler is to sample near-uniformly from the support set of a dynamic multiset. This problem has a variety of applications within data analysis, computational geometry and graph algorithms. In this paper, we abstract a set of steps for building an ? ₀-sampler, based on sampling, recovery and selection. We analyze the implementation of an ? ₀-sampler within this framework, and show how prior constructions of ? ₀-samplers can all be expressed in terms of these steps. Our experimental contribution is to provide a first detailed study of the accuracy and computational cost of ? ₀-samplers.     

Edge-pancyclicity and path-embeddability of bijective connection graphs

An n-dimensional Bijective Connection graph (in brief BC graph) is a regular graph with 2ⁿ nodes and n2ⁿ⁻¹ edges. The n-dimensional hypercube, crossed cube, Möbius cube, etc. are some examples of the n-dimensional BC graphs. In this paper, we propose a general method to study the edge-pancyclicity and path-embeddability of the BC graphs. First, we prove that a path of length l with dist(X_n, x, y) + 2 ? l ? 2ⁿ − 1 can be embedded between x and y with dilation 1 in X_n for x, y ∈ V(X_n) with x ≠ y in X_n, where X_n (n ? 4) is a n-dimensional BC graph satisfying the three specific conditions and V(X_n) is the node set of X_n. Furthermore, by this result, we can claim that X_n is edge-pancyclic. Lastly, we show that these results can be applied to not only crossed cubes and Möbius cubes, but also other BC graphs except crossed cubes and Möbius cubes. So far, the research on edge-pancyclicity and path-embeddability has been limited in some specific interconnection architectures such as crossed cubes, Möbius cubes.     

Approximation and Tidying—A Problem Kernel for?s-Plex Cluster Vertex Deletion

We introduce the NP-hard graph-based data clustering problem s-Plex Cluster Vertex Deletion, where the task is to delete at most?k vertices from a graph so that the connected components of the resulting graph are s-plexes. In an s-plex, every vertex has an edge to all but at most s?1?other vertices; cliques are 1-plexes. We propose a new method based on “approximation and tidying” for kernelizing vertex deletion problems whose goal graphs can be characterized by forbidden induced subgraphs. The method exploits polynomial-time approximation results and thus provides a useful link between approximation and kernelization. Employing “approximation and tidying”, we develop data reduction rules that, in?O(ksn ²) time, transform an s-Plex Cluster Vertex Deletion instance with n vertices into an equivalent instance with O(k ² s ³)?vertices, yielding a problem kernel. To this end, we also show how to exploit structural properties of the specific problem in order to significantly improve the running time of the proposed kernelization method.     

Efficient processing of label-constraint reachability queries in large graphs

In this paper, we study a variant of reachability queries, called label-constraint reachability (LCR) queries. Specifically, given a label set S and two vertices u₁ and u₂ in a large directed graph G, we check the existence of a directed path from u₁ to u₂, where edge labels along the path are a subset of S. We propose the path-label transitive closure method to answer LCR queries. Specifically, we t4ransform an edge-labeled directed graph into an augmented DAG by replacing the maximal strongly connected components as bipartite graphs. We also propose a Dijkstra-like algorithm to compute path-label transitive closure by re-defining the “distance” of a path. Comparing with the existing solutions, we prove that our method is optimal in terms of the search space. Furthermore, we propose a simple yet effective partition-based framework (local path-label transitive closure+online traversal) to answer LCR queries in large graphs. We prove that finding the optimal graph partition to minimize query processing cost is a NP-hard problem. Therefore, we propose a sampling-based solution to find the sub-optimal partition. Moreover, we address the index maintenance issues to answer LCR queries over the dynamic graphs. Extensive experiments confirm the superiority of our method.     

Mixed l −/l 1 fault detection observer design for positive switched systems with time-varying delay via delta operator approach

This paper investigates the problem of fault detection observer design for positive switched systems with time-varying delay via delta operator approach. A new fault sensitivity measure, called l _?index, is proposed. The l _? fault detection observer design and multi-objective l _?/l ₁ fault detection observer design problems are addressed. Based on the average dwell time approach and the piecewise copositive type Lyapunov-Krasovskii functional method in delta domain, sufficient conditions for the existence of such two kinds of fault detection observers are firstly given, and then the design methods are presented. Finally, two examples are provided to show the effectiveness and the applicability of the proposed methods.     

A delay optimal coterie on the k-dimensional folded Petersen graph

Coteries are an effective tool for enforcing mutual exclusion in distributed systems. Communication delay is an important metric to measure the performance of a coterie. The topology of the interconnection network in a distributed system also has an impact on its performance. The k-dimensional folded Petersen graph, a graph with 10^k nodes and diameter 2k, qualifies as a good network topology for large distributed systems. In this paper, we present a delay optimal coterie on the k-dimensional folded Petersen graph, FP_k. For any positive integer k, the coterie has message complexity 4^k and delay k. Moreover, this coterie is not vote-assignable.     

Finding multiple induced disjoint paths in general graphs

In an undirected graph, paths P₁,P₂,…,Pk are induced disjoint if each one of them is chordless (i.e., is an induced path) and any two of them have neither common nodes nor adjacent nodes. This paper investigates the Maximum Induced Disjoint Paths (MIDP) problem: in an undirected graph G=(V,E), given k node pairs {s₁,t₁},…,{sk,tk}, connect maximum number of these node pairs via induced disjoint paths. Till now, the only things known about MIDP are: i) it is NP-hard; ii) it is NP-hard even when k=2; iii) it can be solved in polynomial time when k is a fixed constant and the given graph is a directed planar graph (Kobayashi, 2009 [9]). This paper proves that for general k and any ?>0, it is NP-hard to approximate MIDP within m1/2−?, where m=|E|. Two algorithms for MIDP are given by this paper: a greedy algorithm whose approximation ratio is and an on-line algorithm which has a good lower bound.     

Dynamic graph learning for spectral feature selection

Previous spectral feature selection methods generate the similarity graph via ignoring the negative effect of noise and redundancy of the original feature space, and ignoring the association between graph matrix learning and feature selection, so that easily producing suboptimal results. To address these issues, this paper joints graph learning and feature selection in a framework to obtain optimal selected performance. More specifically, we use the least square loss function and an ? _2,1-norm regularization to remove the effect of noisy and redundancy features, and use the resulting local correlations among the features to dynamically learn a graph matrix from a low-dimensional space of original data. Experimental results on real data sets show that our method outperforms the state-of-the-art feature selection methods for classification tasks.