Search

In a multi-agent system, the presence of agents that intentionally share misleading information or have suffered a failure (non-cooperative agents) affects its normal operation. Specific characteristics of the connectivity graph of the system can help to avoid this situation. Here, a resilience algorithm for multi-agent systems is studied and applied so that the system is able to reach its global task. Specifically, the conditions on the connectivity graph, update rule and bounds on the deviation of shared information among the agents are studied so that a resilient consensus is achieved. Both, the algorithm and the analysis is applied in a group of heterogeneous robots whose global task is formation and trajectory tracking. Further, after the identification of non-cooperative agents, the re-configuration of the agents is such that the robustness of the graph is kept.

Graph network analysis (GNA) showed a remarkable role for understanding brain functions, but its application is mainly nar-rowed to fMRI research. Connectivity analysis (CA) is introduced as a signal-to-graph mapping in a time-causality framework. In this paper, we investigate the application of GNA/CA in fNIRS. To solve the inher-ent challenges of using CA, we also propose a novel metric: a maximum cross-lag magnitude (MCLM) that eÿciently extracts major causality in-formation. We tested MCLM in four types of cognitive activities (mental arithmetic, motor imagery, word generation, and brain workload) from 55 participants. CA/MCLM showed a compelling modeling capacity and re-vealed unexpected cross-subject network patterns. We found that motion imagery and mental arithmetic share a background network structure, and that the right prefrontal cortex, in AFp8, is an invariable destina-tion for information flows in every stimuli and participant. Therefore, CA/MCLM-fNIRS showed potential for its use along with fNIRS in clin-ical studies. This work is financially supported by the Research Council of Norway to the Project No. 273599, "Patient-Centric Engineering in Rehabilitation (PACER)".

Given high-dimensional, graph-smooth and grossly-corrupted signals, this paper presents the algorithm to simultaneously estimate the intrinsic low-rank components and the underlying graph from high-dimensional noisy graph signal. We assume that the perturbation on low-rank components is sparse and signals are smooth on unknown underlying graph. The proposed algorithm learns the low-rank components by exploiting estimate of the graph, and refines the graph estimation with learned low-rank components. We propose two solutions to this problem: One applies alternating optimization to solve the subproblems. The other solves the problem directly. Furthermore, we analyze the impact of inexact graph on low-rank components estimation to justify our approach. We conduct extensive experiments on the proposed algorithm with synthetic data and real brain imaging data, Magnetoencephalography (MEG) and compare it with state-of-the-art methods. In particular, our algorithm is applied to estimate the low-rank components for classifying MEG signals evoked when a subject views a face or non-face image. We observe that our proposed algorithm is competitive in estimating low-rank components, adequately capturing intrinsic task-related information in lower-dimensional representation. This leads to improved classification performance. Furthermore, we notice that our estimated graph indicates brain active regions for the visual activity that are consistent with neuroscientific findings.

We investigate a variant of the Hegselmann-Krause model of opinion dynamics that relaxes the assumption that every agent has knowledge of every other agent's opinion at all points in time. This is done by incorporating a physical connectivity graph that accounts for the external factors that may prevent interaction between certain pairs of agents. As opposed to the original Hegselmann-Krause dynamics (which terminate in finite time), we show that for any underlying graph that is connected but not complete, there exists an initial condition under which the dynamics never terminate. As a result, we show that for any continuous probability density function having the state space as its support, the expected termination time of the modified dynamics is infinity. We also study the rate of convergence to the steady state and derive bounds on the maximum convergence time in terms of the properties of the physical connectivity graph.

This paper proposes mapping and path planning algorithms for an unknown environment using a communication graph of an unlocalized robotic swarm system. Unlike the previous efforts that used the absolute position information of all the robots, in the proposed algorithms, the unknown environment is described as the communication connectivity graph achieved via a distributed consensus algorithm. Thus, since robots have no positioning sensors, the proposed mapping and path planning algorithms can simplify the procedures and reduce the costs. The numerical simulations are included to demonstrate the performance of the proposed algorithms.

Establishing corresponding features on two non-rigidly deformed 3D surfaces is a challenging and well-studied problem in computer graphics. Unlike previous approaches that constrain the matching between feature pairs using isometry-invariant distance metrics, we constrain the matching using a discrete connectivity graph derived from the Morse–Smale complex of the Auto Diffusion Function. We observed that the graph remains stable even for surfaces differing by topology or by significant deformation. This algorithm is simple to implement and efficient to run. When tested on a range of examples, our algorithm produces comparable results with state-of-art methods on surfaces with strong isometry but with greatly improved efficiency, and often gets better correspondences on surfaces with larger shape variances.

This paper proposes a novel generalization model for selecting characteristic streets in an urban street network. This model retains the central structure of a street network. It relies on a structural representation of a street network using graph principles where vertices represent named streets and links represent street intersections. Based on this representation, so-called connectivity graph, centrality measures are introduced to qualify the status of each individual vertex within the graph. We show that these measures can be used for characterizing the structural properties of an urban street network, and for the selection of important streets. The proposed approach is validated by a case study applied to a middle-sized Swedish city.

Motivated by the need of observers that are both robust to disturbances and guarantee fast convergence to zero of the estimation error, we propose an observer for linear time-invariant systems with noisy output that consists of the combination of N coupled observers over a connectivity graph. At each node of the graph, the output of these interconnected observers is defined as the average of the estimates obtained using local information. The convergence rate and the robustness to measurement noise of the proposed observer's output are characterized in terms of $\mathcal{KL}$ bounds. Several optimization problems are formulated to design the proposed observer so as to satisfy a given rate of convergence specification while minimizing the $H_\infty$ gain from noise to estimates or the size of the connectivity graph. It is shown that that the interconnected observers relax the well-known tradeoff between rate of convergence and noise amplification, which is a property attributed to the proposed innovation term that, over the graph, couples the estimates between the individual observers. Sufficient conditions involving information of the plant only, assuring that the estimate obtained at each node of the graph outperforms the one obtained with a single, standard Luenberger observer are given. The results are illustrated in several examples throughout the paper., Comment: The technical report accompanying "Interconnected Observers for Robust Decentralized Estimation with Performance Guarantees and Optimized Connectivity Graph" to be published in IEEE Transactions on Control of Network Systems, 2015

Much effort has been directed towards using mathematical models to understand and predict contagious disease, in particular Ebola outbreaks. Classical SIR (susceptible-infected-recovered) compartmental models capture well the dynamics of the outbreak in certain communities, and accurately describe the differences between them based on a variety of parameters. However, repeated resurgence of Ebola contagions suggests that there are components of the global disease dynamics that we don't yet fully understand and can't effectively control. In order to understand the dynamics of a more widespread contagion, we placed SIR models within the framework of dynamic networks, with the communities at risk of contracting the virus acting as nonlinear systems, coupled based on a connectivity graph. We study how the effects of the disease (measured as the outbreak impact and duration) change with respect to local parameters, but also with changes in both short-range and long-range connectivity patterns in the graph. We discuss the implications of optimizing both these measures in increasingly realistic models of coupled communities., Comment: 16 pages, 8 figures

This paper presents an automated tool for estimating assembly times of products based on a three step process: connectivity graph generation from assembly mate information, structural complexity metric analysis of the graph, and application of the complexity metric vector to predictive artificial neural network models. The tool has been evaluated against different training set cases, suggesting that partially defined assembly models and training product variety are critical characteristics. Moreover, the tool is shown to be robust and insensitive to different modeling engineers. The tool has been implemented in a commercial CAD system and shown to yield results of within ±25% of predicted values. Additional extensions and experiments are recommended to improve the tool.

This material contains the description and the links where to find the datasets used in the paper Assessing cross-cut shredded document assembly Abstract In this paper we address the problem of quantitative evaluation of cross-cut shredded document reconstruction. We propose quantitative metrics using graph theory and classic information retrieval concepts to compare the neighborhood connectivity graph of a reassembled document shredded by a cross-cut machine against the neighborhood graph of the ground-truth. These metrics focus entirely on the proper relative positioning of the shredded pieces. To do so, we have shredded 12 documents containing diverse content, such as handwriting, printed text, images and photographs. We then scanned, extracted the pieces, and reassembled them into the ground-truth. This dataset is available to the readers, with the original documents, the digital representation of the shreds, and the scripts that provide the quantitative evaluation of the user’s reconstructions.

We have implemented a multiscale vision model based on the wavelet transform to analyse field astronomical images. The discrete transform is performed by the a trous algorithm. The vision model is based on the notion of significant structures. We identify the pixels of the associated wavelet transform space (WTS) with the objects. For each scale a region labelling is carried out. An interscale connectivity graph is then established. In accordance with some rules that permit false detections to be removed, the objects and their sub-objects are identified. They define respectively trees and sub-trees in the graph. In this way, the identification of the WTS pixels of the tree related to a given object leads to the reconstruction of its image by the conjugate gradient method. The model has been tested successfully on simulated images of stars and galaxies which allow us to show the capabilities of the detection and restoration procedures of the model. Finally, tests on real images show that one can analyse complex structures better than with classical astronomical vision models.

We have implemented a multiscale vision model based on the wavelet transform to analyse field astronomical images. The discrete transform is performed by the a trous algorithm. The vision model is based on the notion of the significant structures. We identify the pixels of the wavelet transform space (WTS) associated with the objects. At each scale a region labelling is carried out. An interscale connectivity graph is then established. In accordance with some rules that permit false detections to be removed, the objects and their sub-objects are identified. They define respectively trees and sub-trees in the graph. So, the identification of the WTS pixels of the tree related to a given object leads to the reconstruction of its image by the conjugate gradient method. The model has been tested successfully on astronomical images which shows that complex structures are better analysed than using usual astronomical vision models.

This note studies a network of agents having continuous-time dynamics with quantized interactions and time-varying directed topology. Due to the discontinuity of the dynamics, solutions of the resulting ODE systems are intended in the sense of Krasovskii. A limit connectivity graph is defined, which encodes persistent interactions between nodes: if such graph has a globally reachable node, Krasovskii solutions reach consensus (up to the quantizer precision) after a finite time. Under the additional assumption of a time-invariant topology, the convergence time is upper bounded by a quantity which depends on the network size and the quantizer precision. It is observed that the convergence time can be very large for solutions which stay on a discontinuity surface.

The success in backbone resonance sequential assignment is fundamental to three dimensional protein structure determination via Nuclear Magnetic Resonance (NMR) spectroscopy. Such a sequential assignment can roughly be partitioned into three separate steps: grouping resonance peaks in multiple spectra into spin systems, chaining the resultant spin systems into strings, and assigning these strings to non-overlapping consecutive amino acid residues in the target protein. Separately dealing with these three steps has been adopted in many existing assignment programs, and it works well on protein NMR data with close-to-ideal quality, while only moderately or even poorly on most real protein datasets, where noises as well as data degeneracies occur frequently. We propose in this work to partition the sequential assignment not by physical steps, but only virtual steps, and use their outputs to cross validate each other. The novelty lies in the places, where the ambiguities at the grouping step will be resolved in finding the highly confident strings at the chaining step, and the ambiguities at the chaining step will be resolved by examining the mappings of strings at the assignment step. In this way, all ambiguities at the sequential assignment will be resolved globally and optimally. The resultant assignment program is called Graph-based Approach for Sequential Assignment (GASA), which has been compared to several recent similar developments including PACES, RANDOM, MARS, and RIBRA. The performance comparisons with these works demonstrated that GASA is more promising for practical use.

A new method to obtain a rough description of a 3-D object from its outline shape is presented in this paper. Firstly the outline shape is split up into parts that are related in a connectivity graph. The boundary features of every part (lines, curves) and the information about its junction with other parts are extracted in order to provide a semantic content to the outline shape graph. A specific language to describe this graph has been developed. Finally, some results obtained applying our approach over real images are presented and discussed.

The study of the Internet topology has recently received much attention from the research community. In particular, the observation that the network graph has interesting properties, such as power laws, that might be explored in a myriad of ways. Most of the work in characterizing the Internet graph is based on the physical network graph, i.e., the connectivity graph. In this paper we investigate how logical relationships between nodes of the AS graph can be used to gain insight to its structure. We characterize the logical graph using various metrics and identify the presence of power laws in the number of customers that a provider has. Using these logical relationships we define a structural model of the AS graph. The model highlights the hierarchical nature of logical relationships and the preferential connection to larger providers. We also investigate the consistency of this model over time and observe interesting properties of the hierarchical structure.