Search

We study the convergence properties of Social Hegselmann-Krause dynamics, a {variant} of the Hegselmann-Krause (HK) model of opinion dynamics where a physical connectivity graph that accounts for the extrinsic factors that could prevent interaction between certain pairs of agents is incorporated. As opposed to the original HK dynamics (which terminate in finite time), we show that for any underlying connected and incomplete graph, under a certain mild assumption, the expected termination time of social HK dynamics is infinity. We then investigate the rate of convergence to the steady state, and provide bounds on the maximum $\epsilon$-convergence time in terms of the properties of the physical connectivity graph. We extend this discussion and observe that for almost all $n$, there exists an $n$-vertex physical connectivity graph on which social HK dynamics may not even $\epsilon$-converge to the steady state within a bounded time frame. We then provide nearly tight necessary and sufficient conditions for arbitrarily slow merging (a phenomenon that is essential for arbitrarily slow $\epsilon$-convergence to the steady state). Using the necessary conditions, we show that complete $r$-partite graphs have bounded $\epsilon$-convergence times.

We develop an automatic method for synaptic partner identification in insect brains and use it to predict synaptic partners in a whole-brain electron microscopy dataset of the fruit fly. The predictions can be used to infer a connectivity graph with high accuracy, thus allowing fast identification of neural pathways. To facilitate circuit reconstruction using our results, we develop CIRCUITMAP, a user interface add-on for the circuit annotation tool CATMAID. A deep-learning-based approach enables automatic identification of synaptically connected neurons in electron microscopy datasets of the fly brain.

Model supramolecular associates possessing nondirectional intermolecular interactions were investigated in order to demonstrate the opportunity of plotting of an atomic connectivity graph based on trajectories of Hessian eigenvector of electron density corresponding to the largest eigenvalue. Such trajectories are a reasonable alternative to the gradient bond paths in the case of proximity of the latter to the T-shaped form upon the presence of parallel surface of the zero-flux of electron density in the neighborhood of gradient-based trajectory.

Background Down syndrome (DS) is a chromosomal disorder that causes intellectual disability. Few studies have been conducted on functional connectivity using resting‐state fMRI (functional magnetic resonance imaging) signals or more specifically, on the relevant structure and density of the default mode network (DMN). Although data on this issue have been reported in adult DS individuals (age: >45 years), the DMN properties in young DS individuals have not been studied. The aim of this study was to describe the density and structure of the DMN network from fMRI signals in young DS (age, DMN in Down syndrome. Network indicators in DS. Functional connectivity.

Gossip Learning (GL) is a fully decentralized machine learning paradigm with the potential to enable highly scalability and to preserve user privacy. The majority of existing results however consider scenarios in which either each node communicates with all other nodes, or in which the connectivity graph is static, and they are therefore inapplicable in dynamic setups such as in VANETs. This work is a first attempt at designing and assessing GL schemes suited for scenarios with moving nodes with the application of predicting the trajectory of moving cars.

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.

Emerging data-driven modeling methods are affording new opportunities for building bio-inspired models for neurosensory integration. Of particular interest is understanding how neural pathways from input stimuli to motor-neuron driven behavioral responses function. Importantly, data-driven models are capable of framing neurosensory integration into a modern control theoretic framework, allowing for an improved understanding of the role of network structure and function. Two model organisms are considered here: Caenorhabditis elegans (C. elegans) and (ii) the Manduca Sexta (Manduca) moth. These well studied model organisms exploit different network architectures for functionality, with the former leveraging a small, stereotyped connectivity graph for its function, while the latter makes use of a large, randomly connected network for processing sensory (olfactory) information and learning. These two alternative strategies give insight into the diversity of neurosensory strategies available to organisms for producing robust and stable behaviors in a noisy stimulus environment.

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)".

International audience; The spatial distribution of atrophy in neurodegenerative diseases suggests that brain connectivity mediates disease propagation. Different descriptors of the connectivity graph potentially relate to different underlying mechanisms of propagation. Previous approaches for evaluating the influence of connectivity on neurodegeneration consider each descriptor in isolation and match predictions against late-stage atrophy patterns. We introduce the notion of a topological profile — a characteristic combination of topological descriptors that best describes the propagation of pathology in a particular disease. By drawing on recent advances in disease progression modeling, we estimate topological profiles from the full course of pathology accumulation, at both cohort and individual levels. Experimental results comparing topological profiles for Alzheimer’s disease, multiple sclerosis and normal ageing show that topological profiles explain the observed data better than single descriptors. Within each condition, most individual profiles cluster around the cohort-level profile, and individuals whose profiles align more closely with other cohort-level profiles show features of that cohort. The cohort-level profiles suggest new insights into the biological mechanisms underlying pathology propagation in each disease.

We address the problem of identifying physical connectivity graphs that guarantee a finite upper bound on the time required for the associated social Hegselmann-Krause dynamics to ϵ-converge to the steady state. We handle the cases of consensus as well as non-consensus steady states, and for each case, we provide sufficient conditions for a physical connectivity graph to have unbounded ϵ-convergence time. We then show that every complete r-partite graph on n vertices has a finite maximum ϵ-convergence time, regardless of the values of r and n. Finally, we show that enhancing the connectivity of agents may not always speed up convergence to the steady state, even when the steady state is a consensus.

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.

Microstructural geometry plays a critical role in the response of heterogeneous materials. Consequently, methods for generating microstructural samples are increasingly crucial to advanced numerical analyses. We extend Sonon et al.'s unified framework, developed originally for generating particulate and foam-like microstructural geometries of Periodic Unit Cells, to non-periodic microstructural representations based on the formalism of Wang tiles. This formalism has been recently proposed in order to generalize the Periodic Unit Cell approach, enabling a fast synthesis of arbitrarily large, stochastic microstructural samples from a handful of domains with predefined compatibility constraints. However, a robust procedure capable of designing complex, three-dimensional, foam-like and cellular morphologies of Wang tiles has not yet been proposed. This contribution fills the gap by significantly broadening the applicability of the tiling concept. Since the original Sonon et al.'s framework builds on a random sequential addition of particles enhanced with an implicit representation of particle boundaries by the level-set field, we first devise an analysis based on a connectivity graph of a tile set, resolving the question where a particle should be copied when it intersects a tile boundary. Next, we introduce several modifications to the original algorithm that are necessary to ensure microstructural compatibility in the generalized periodicity setting of Wang tiles. Having established a universal procedure for generating tile morphologies, we compare strictly aperiodic and stochastic sets with the same cardinality in terms of reducing the artificial periodicity in reconstructed microstructural samples. We demonstrate the superiority of the vertex-defined tile sets for two-dimensional problems and illustrate the capabilities of the algorithm with two- and three-dimensional examples., 16 pages, 16 figures. Abstract has been shortened to match the arXiv.org's limit of 1920 characters

Hyperspectral image (HSI) classification plays an important role in the automatic interpretation of the remotely sensed data. However, it is a non-trivial task to classify HSI accurately and rapidly due to its characteristics of having a large amount of data and massive noise points. To address this problem, in this work, a novel, semi-supervised, superpixel-level classification method for an HSI was proposed based on a graph and discrete potential (SSC-GDP). The key idea of the proposed scheme is the construction of the weighted connectivity graph and the division of the weighted graph. Based on the superpixel segmentation, a weighted connectivity graph is constructed usingthe weighted connection between a superpixel and its spatial neighbors. The generated graph is then divided into different communities/sub-graphs by using a discrete potential and the improved semi-supervised Wu–Huberman (ISWH) algorithm. Each community in the weighted connectivity graph represents a class in the HSI. The local connection strategy, together with the linear complexity of the ISWH algorithm, ensures the fast implementation of the suggested SSC-GDP method. To prove the effectiveness of the proposed spectral–spatial method, two public benchmarks, Indian Pines and Salinas, were utilized to test the performance of our proposal. The comparative test results confirmed that the proposed method was superior to several other state-of-the-art methods.

Objective An epileptic seizure has a characteristic EEG pattern, which allows for its automatic detection. Statistical dependence between different brain regions measures by functional brain connectivity (FBC). Specific directional effects cannot be considered by FBC, and thus effective brain connectivity (EBC) is used to measure causal dependencies between brain regions. Our main purpose is to provide a reliable automatic seizure detection approach. Methods In this study, three new methods are provided. Multi-level modular network (MLMN) is proposed based on combining various EBC classification results at different frequencies. Another method named “modular effective neural networks (MENN).” This method combines the classification results of the three different EBCs at a specific frequency. “Modular frequency neural networks (MFNN)” is another method that combines the classification results of specific EBC at seven different frequencies. Results The mean accuracies of MFNN are 97.14 %, 98.53 %, and 97.91 % using directed transfer function (DTF), directed coherence (DC), and generalized partial directed coherence (GPDC), respectively. By using MENN method, the highest mean accuracy is 98.34 %. Finally, MLMN has the highest mean accuracy, which is equal to 99.43. To the best of our knowledge, the proposed method is a new method that provides the highest accuracy in comparison to other studies – that used the MIT-CHB database. Conclusion and significance The knowledge of structure-function relationships between different areas of the brain is necessary for characterizing the underlying dynamics. Hence, features based on EBC can provide a more reliable automatic seizure detection approach.

For a smooth bounded real algebraic surface in R n , a roadmap of it is a one-dimensional semi-algebraic subset of the surface whose intersection with each connected component of the surface is nonempty and semi-algebraically connected. In this paper, we introduce the notion of a numerical roadmap of a surface, which is a set of disjoint polygonal chains such that there is a bijective map between the chains and the connected components of a given roadmap of the surface. Moreover, the chains are ϵ-close to the connected components. We present an algorithm to compute such a numerical roadmap through constructing a topological graph. The topological graph also enables us to compute an approximate graph and a more intrinsic connectivity graph to represent the roadmap and its connectivity property, which is important for applications such as determining if two points on the surface belong to the same connected component and if so, finding a connected path between them.

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.

Quantum annealing has shown significant potential as an approach to near-term quantum computing. Despite promising progress towards obtaining a quantum speedup, quantum annealers are limited by the need to embed problem instances within the (often highly restricted) connectivity graph of the annealer. This embedding can be costly to perform and may destroy any computational speedup. Here we present a hybrid quantum-classical paradigm to help mitigate this limitation, and show how a raw speedup that is negated by the embedding time can nonetheless be exploited in certain circumstances. We illustrate this approach with initial results on a proof-of-concept implementation of an algorithm for the dynamically weighted maximum independent set problem., In Proceedings PC 2018, arXiv:1807.10563

In this work we continue the investigation of different approaches to conception and modeling of composite materials. The global method we focus on, is called 'stochastic homogenization'. In this approach, the classical deterministic homogenization techniques and procedures are used to compute the macroscopic parameters of a composite starting from its microscopic properties. The stochastic part is due to averaging over some series of samples, and the fact that these samples fit into the concept of RVE (Representative Volume Element) in order to reduce the variance effect. In this article, we present a novel method for computation of effective electric properties of composites -- it is based on the analysis of the connectivity graph (and the respective adjacency matrix) for each sample of a composite material. We describe how this matrix is constructed in order to take into account complex microscopic geometry. We also explain what we mean by homogenization procedure for electrical conductivity, and how the constructed matrix is related to the problem. The developed method is applied to a test study of the influence of micromorphology of composites materials on their conductivity., 16 pages, 10 figures; version accepted to Composite Structures

Although many methods of spatial analysis have been developed for a better understanding and modelling of urban space analysis, there is still a need for exploration of new analytical techniques for modelling urban spaces. Space Syntax models the spatial configurations of urban spaces by using a connectivity graph representation. Such a configuration of space identifies patterns that can be used to study urban structures and human behaviors. This paper tries to present a new methodology to investigate the urban spatial structure by using Space Syntax with the GIS information including land use, buildings’ characteristics and practical evaluations of the potential of the Space Syntax approach with GIS and multivariate analysis technique. Finally we try to offer some recommendations that attempt to improve the identified problems faced in Kitakyushu, Japan.

This work was aimed at reconstructing the structural model of as-built industrial facilities like plants purely from on-site point cloud measurement data. Focus was set on finding the internal structure of complex objects hidden behind the massive point cloud by exploiting connectivity information in the data and the linear characteristics of the typical components. A workflow is presented with emphasis on data filtering, connectivity graph construction, as well as the recognition of elementary objects and their relations. Results are demonstrated using data of an industrial case study.

Diffusion magnetic resonance imaging (MRI) is a powerful non-invasive method to study white matter integrity, and is sensitive to detect differences in Alzheimer's disease (AD) patients. Diffusion MRI may be able to contribute towards reliable diagnosis of AD. We used diffusion MRI to classify AD patients (N=77), and controls (N=173). We use different methods to extract information from the diffusion MRI data. First, we use the voxel-wise diffusion tensor measures that have been skeletonised using tract based spatial statistics. Second, we clustered the voxel-wise diffusion measures with independent component analysis (ICA), and extracted the mixing weights. Third, we determined structural connectivity between Harvard Oxford atlas regions with probabilistic tractography, as well as graph measures based on these structural connectivity graphs. Classification performance for voxel-wise measures ranged between an AUC of 0.888, and 0.902. The ICA-clustered measures ranged between an AUC of 0.893, and 0.920. The AUC for the structural connectivity graph was 0.900, while graph measures based upon this graph ranged between an AUC of 0.531, and 0.840. All measures combined with a sparse group lasso resulted in an AUC of 0.896. Overall, fractional anisotropy clustered into ICA components was the best performing measure. These findings may be useful for future incorporation of diffusion MRI into protocols for AD classification, or as a starting point for early detection of AD using diffusion MRI.

Diffusion magnetic resonance imaging (MRI) is a powerful non-invasive method to study white matter integrity, and is sensitive to detect differences in Alzheimer's disease (AD) patients. Diffusion MRI may be able to contribute towards reliable diagnosis of AD. We used diffusion MRI to classify AD patients (N=77), and controls (N=173). We use different methods to extract information from the diffusion MRI data. First, we use the voxel-wise diffusion tensor measures that have been skeletonised using tract based spatial statistics. Second, we clustered the voxel-wise diffusion measures with independent component analysis (ICA), and extracted the mixing weights. Third, we determined structural connectivity between Harvard Oxford atlas regions with probabilistic tractography, as well as graph measures based on these structural connectivity graphs. Classification performance for voxel-wise measures ranged between an AUC of 0.888, and 0.902. The ICA-clustered measures ranged between an AUC of 0.893, and 0.920. The AUC for the structural connectivity graph was 0.900, while graph measures based upon this graph ranged between an AUC of 0.531, and 0.840. All measures combined with a sparse group lasso resulted in an AUC of 0.896. Overall, fractional anisotropy clustered into ICA components was the best performing measure. These findings may be useful for future incorporation of diffusion MRI into protocols for AD classification, or as a starting point for early detection of AD using diffusion MRI.

An approach to the formation of operational visibility and ecological risks scene displaying in geographic information systems (GIS) of environmental protection is offered. The approach is based on structural-symbolic method of presenting the basic graphic elements (BGE) (models) of ecological risks, the linguistic rules and grammar construction of BGE on the basis of a given set of contours, BGE connectivity graph and set-theoretic operations of ecological risk maps synthesis using GIS. The main methods of structural electronic BGE library construction described in the article: direct structural-symbolic method of ecological risks graphical models representing; linguistic method of representing the alphabet and ecological risk models; program and program-linguistic method for representing the alphabet of basic graphic models of ecological risks.

The problem of finding structural features of growing structures for which a specified growth shape is allowable is considered within the model of layer-by-layer growth of tilings or packings and the generalization of this model to connectivity graphs. In particular, the problem of revealing growth shapes that are impossible for periodic structures is solved.

Over the past few years Personal Navigation Systems have become an established tool for route planning, but they are mainly designed for outdoor environments. Indoor navigation is still a challenging research area for several reasons: positioning is not very accurate, users can freely move between the interior boundaries of buildings, path network construction process may not be easy and straightforward due to complexity of indoor space configurations. Therefore the creation of a good network is essential for deriving overall connectivity of a building and for representing position of objects within the environment. This paper reviews current approaches to automatic derivation of route graphs for indoor navigation and discusses some of their limitations. Then, it introduces a novel algorithmic strategy for extracting a 3D connectivity graph for indoor navigation based on 2D floor plans.

Over-segmentation, or super-pixel generation, is a common preliminary stage for many computer vision applications. New acquisition technologies enable the capturing of 3D point clouds that contain color and geometrical information. This 3D information introduces a new conceptual change that can be utilized to improve the results of over-segmentation, which uses mainly color information, and to generate clusters of points we call super-points. We consider a variety of possible 3D extensions of the Local Variation (LV) graph based over-segmentation algorithms, and compare them thoroughly. We consider different alternatives for constructing the connectivity graph, for assigning the edge weights, and for defining the merge criterion, which must now account for the geometric information and not only color. Following this evaluation, we derive a new generic algorithm for over-segmentation of 3D point clouds. We call this new algorithm Point Cloud Local Variation (PCLV). The advantages of the new over-segmentation algorithm are demonstrated on both outdoor and cluttered indoor scenes. Performance analysis of the proposed approach compared to state-of-the-art 2D and 3D over-segmentation algorithms shows significant improvement according to the common performance measures.

We present a graph-theoretical interpretation of the recently developed interface theory of single zigzag chains N(n) in form of connectivity graphs. A remarkable property of the connectivity graphs is the possibility of constructing the full set of Clar covers of N(n) as the complete set of walks on these graphs. Connectivity graphs can be constructed in a direct form, in which the number of vertices is growing linearly with the length n of N(n), and in a reduced form, in which the number of vertices is independent of the actual length of the chain. The presented results can be immediately used for the determination of the Zhang-Zhang (ZZ) polynomials of N(n) in an easy and natural manner. Two techniques for computing the ZZ polynomial are proposed, one based on direct recursive computations and the other based on a general solution to a set of recurrence relations. Generalization of the interface theory to arbitrary benzenoid structures, the construction of associated connectivity graphs, and techniques for the computation of the associated ZZ polynomials will be presented in the near future. This work is licensed under a Creative Commons Attribution 4.0 International License.

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.

Identifying the relations among different regions of the brain is vital for a better understanding of how the brain functions. While a large number of studies have investigated the neuroanatomical and neurochemical connections among brain structures, their specific findings are found in publications scattered over a large number of years and different types of publications. Text mining techniques have provided the means to extract specific types of information from a large number of publications with the aim of presenting a larger, if not necessarily an exhaustive picture. By using natural language processing techniques, the present paper aims to identify connectivity relations among brain regions in general and relations relevant to the paraventricular nucleus of the thalamus (PVT) in particular. We introduce a linguistically motivated approach based on patterns defined over the constituency and dependency parse trees of sentences. Besides the presence of a relation between a pair of brain regions, the proposed method also identifies the directionality of the relation, which enables the creation and analysis of a directional brain region connectivity graph. The approach is evaluated over the manually annotated data sets of the WhiteText Project. In addition, as a case study, the method is applied to extract and analyze the connectivity graph of PVT, which is an important brain region that is considered to influence many functions ranging from arousal, motivation, and drug-seeking behavior to attention. The results of the PVT connectivity graph show that PVT may be a new target of research in mood assessment.

The conventional raster-based least-cost path technique, in which the connectivity graph is constructed by treating each raster cell as a node and linking each node to its adjacent neighbors, has been widely used to determine optimum paths in space. Unfortunately, paths calculated with this method are subject to distortions that stem from the imposed node-link structure. Due to the distortions, the calculated paths may be longer than the true optimum paths in continuous space, and because of this, they may also look highly unrealistic when displayed on a map. This study examines how the quality of the raster-based paths can be improved by using larger connectivity patterns on the one hand, and placing nodes on the sides of the cells of a raster instead of at their centers, on the other. In addition, the utility of the quadtree structure is examined. The different methods are evaluated against three different datasets using the cost distance of the calculated paths and processing times as evaluation criteria. The results indicate that raster-based paths can be improved by using the evaluated techniques, although the degree of improvement is also dependent on the properties of the underlying cost raster.

Probability hypothesis density (PHD) filter and cardinalized PHD (CPHD) filter have proved to be promising algorithms for tracking an unknown number of targets in real time. However, they do not provide the identities of the individual estimated targets, so the target tracks cannot be obtained. To solve this problem, we propose a new track maintenance algorithm based on the cross entropy (CE) technique. Firstly, the particle filter PHD (PF-PHD) algorithm is used to estimate the target states and the target number. Then, the results of the estimation are used as vertexes to construct a connectivity graph with associated weights, and the CE technique is employed as a global optimization scheme to calculate the optimal feasible associated events. Furthermore, due to the advantages of the CPHD filter and the Rao-Blackwellized particle filter (RBPF), we propose another track maintenance algorithm based on the CE technique, named the RBPF-CPHD tracker, which can further improve the track maintenance performance due to the more accurate state estimates and their number estimates. Simulation results show that the proposed algorithms can effectively achieve the track continuity, with stronger robustness and greater anti-jamming capability.

Siting a linear facility such as a highway or a pipeline often requires a preliminary study in which one or several corridors are identified. Here we construct corridors as a collection of adjacent polygons specifying a ‘path’ from origin s to destination t . Formally, we make use of a graph, called the connectivity graph, in which vertices correspond to polygons and edges to adjacent polygons. Within this formal representation, a corridor corresponds to an s to t path in the connectivity graph. The corridors are evaluated on two criteria: (1) a quantitative criterion measuring the length of the corridor, and (2) a qualitative criterion measuring the quality of the corridor with respect to the suitability of crossing its component polygons. We first introduce a three-phase approach based on a coupling between a geographical information system (GIS) and multicriteria evaluation and devoted to handling biobjective corridor siting problems. Then, the proposed approach is validated through an example of a real-world application. Keywords: GIS, corridor siting, multicriteria evaluation, spatial analysis, multiobjective shortest path

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.

There is growing interest in studying dynamic graphs, or graphs that evolve with time. In this work, we investigate a new type of dynamic graph analysis - finding regions of a graph that are evolving in a similar manner and are topologically similar over a period of time. For example, these regions can be used to group a set of changes having a common cause in event detection and fault diagnosis. Prior work [6] has proposed a greedy framework called cSTAG to find these regions. It was accurate in datasets where the regions are temporally and spatially well separated. However, in cases where the regions are not well separated, cSTAG produces incorrect groupings. In this paper, we propose a new algorithm called regHunter. It treats the region discovery problem as a multi-objective optimisation problem, and it uses a multi-level graph partitioning algorithm to discover the regions of correlated change. In addition, we propose an external clustering validation technique, and use several existing internal measures to evaluate the accuracy of regHunter. Using synthetic datasets, we found regHunter is significantly more accurate than cSTAG in dynamic graphs that have regions with small separation. Using two real datasets - the access graph of the 1998 World Cup website, and the BGP connectivity graph during the landfall of Hurricane Katrina - we found regHunter obtained more accurate results than cSTAG. Furthermore, regHunter was able to discover two interesting regions for the World Cup access graph that CSTAG was not able to find.

In this paper, two measures are proposed for valuation of size and coupling complexities of design products as abstracted by three distinct representations. The proposed size complexity measure is based on the information theoretic definition of complexity that connects the complexity of a design to the level of entropy, or uncertainty, inherent in the design product. The proposed coupling complexity measure evaluates the decomposability of the graph-based representation of design products. To validate the proposed measures, an experiment is conducted to calculate the complexities of three consumer products based on three product representations, namely, function structure, connectivity graph, and parametric associativity graph. The findings indicate that coupling and size are independent measures of a product’s complexity. Thus, it is recommended that both measures should be used. Further, the complexity of a product is not independent of the choice of representation model used to describe the product. This suggests that the complexity of a product will vary with the selected view. Finally, it is shown that the two approaches for measuring complexity of a product are generalizable and can be applied to different representations.

In this paper, we developed a model-based and a data-driven estimator for directed information (DI) to infer the causal connectivity graph between electrocorticographic (ECoG) signals recorded from brain and to identify the seizure onset zone (SOZ) in epileptic patients. Directed information, an information theoretic quantity, is a general metric to infer causal connectivity between time-series and is not restricted to a particular class of models unlike the popular metrics based on Granger causality or transfer entropy. The proposed estimators are shown to be almost surely convergent. Causal connectivity between ECoG electrodes in five epileptic patients is inferred using the proposed DI estimators, after validating their performance on simulated data. We then proposed a model-based and a data-driven SOZ identification algorithm to identify SOZ from the causal connectivity inferred using model-based and data-driven DI estimators respectively. The data-driven SOZ identification outperforms the model-based SOZ identification algorithm when benchmarked against visual analysis by neurologist, the current clinical gold standard. The causal connectivity analysis presented here is the first step towards developing novel non-surgical treatments for epilepsy., This paper is accepted for publication in IEEE Journal of Selected Topics in Signal Processing, special issue on Advanced Signal Processing in Brain Networks, October 2016. 16 pages, 11 figures and 2 tables

We formulate the delay-tolerant networking routing problem, where messages are to be moved end-to-end across a connectivity graph that is time-varying but whose dynamics may be known in advance. The problem has the added constraints of finite buffers at each node and the general property that no contemporaneous end-to-end path may ever exist. This situation limits the applicability of traditional routing approaches that tend to treat outages as failures and seek to find an existing end-to-end path. We propose a framework for evaluating routing algorithms in such environments. We then develop several algorithms and use simulations to compare their performance with respect to the amount of knowledge they require about network topology. We find that, as expected, the algorithms using the least knowledge tend to perform poorly. We also find that with limited additional knowledge, far less than complete global knowledge, efficient algorithms can be constructed for routing in such environments. To the best of our knowledge this is the first such investigation of routing issues in DTNs.

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.

We present a technique for calculating free-energy profiles for the nucleation of multicomponent structuresthat contain as many species as building blocks. We find that a key factor is the topology of the graphdescribing the connectivity of the target assembly. By considering the designed interactions separately fromweaker, incidental interactions, our approach yields predictions for the equilibrium yield and nucleation bar-riers. These predictions are in good agreement with corresponding Monte Carlo simulations. We show that afew fundamental properties of the connectivity graph determine the most prominent features of the assemblythermodynamics. Surprisingly, we find that polydispersity in the strengths of the designed interactions stabi-lizes intermediate structures and can be used to sculpt the free-energy landscape for self-assembly. Finally, wedemonstrate that weak incidental interactions can preclude assembly at equilibrium due to the combinatorialpossibilities for incorrect association.Building nanostructures out of multiple, distinct com-ponents offers enormous possibilities for high-fidelitymanufacturing at the molecular level. Such ‘addressable’structures are fundamentally different from conventionalcrystals or ordered clusters, since every building block isdistinct and thus occupies a specific location in the tar-get structure. Because the interactions between buildingblocks are specified independently, it is possible to designfinite-sized, three-dimensional structures that assemblenearly error-free.

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

Consider a set \(S\) of sensors in a plane, each equipped with a directional antenna of beamwidth \(\frac{\pi }{2}\) and radius \(r\in O(1)\). The antennas are symmetric, i.e. for two sensors \(u\) and \(v\) to communicate, \(u\) has to be covered by the antenna of \(v\) and vice versa. Assuming the Unit Disc Graph (\(\mathrm{UDG}\)) of \(S\) is connected, the problem we attack is: How to orient the antennas so that the resulting connectivity graph is a \(k\)-spanner of the \(\mathrm{UDG}\), while minimizing the radius used?

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

Electric stimulation in neural cultures in neural cultures may be used for creating adjacent physical or logical connections in the connectivity graph following Hebb’s Law modifying the neural responses principal parameters. The created biological structure may be used for computing a certain function, however this achieved structure vanished with time as the stimulation stops. A DTCNN architecture, specifically designed for optimum parallel implementation over dedicated hardware, is proposed to emulate the behavior ans structure of the biological neuronal culture. The FPGA circuit can be used as a permanent model and is also intended to facilitate and speed up further experimentation.

Standard representations of irregular finite element meshes combine vertex data (sample coordinates and node values) and connectivity (tetrahedron–vertex incidence). Connectivity specifies how the samples should be interpolated. It may be encoded as four vertex-references for each tetrahedron, which requires 128 m bits where m is the number of tetrahedra in the mesh. Our ‘Grow & Fold’ format reduces the connectivity storage down to 7 bits per tetrahedron: three of these are used to encode the presence of children in a tetrahedron spanning tree; the other four constrain sequences of ‘folding’ operations, so that they produce the connectivity graph of the original mesh. Additional bits must be used for each handle in the mesh and for each topological ‘lock’ in the tree. However, as our experiments with a prototype implementation show, the increase of the storage cost due to this extra information is typically no more than 1–2%. By storing vertex data in an order defined by the tree, we avoid the need to store tetrahedron–vertex references and facilitate variable length coding techniques for the vertex data. We provide the details of simple, loss-less compression and decompression algorithms and discuss a way of decreasing the storage cost to about 6 bits per tetrahedron.

In the past, many methods of spatial analysis have been developed for a better understanding and modelling of real-world phenomena. However there is still a need for exploration of new analytical techniques for modelling urban spaces. Space syntax models the spatial configurations of urban spaces by using a connectivity graph representation. Such a configuration of space identifies patterns that can be used to study urban structures and human behaviours. This paper proposes methodological and practical evaluations of the potential of the space syntax approach within GIS. We present the main principles that are the basis of space syntax, in addition to methodological perspectives for a closer integration with GIS, which should be of use for many GIS applications, such as urban planning and design.

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.

In this paper we study formal indicators of connectivity for a city community of researchers in Informatics and Cybernetics. The analysis is based on data available at the Scientific Electronic Library portal http://eLibrary.ru. Starting from the co-authorship relation we construct connectivity graph for research institutions for all major Russian cities and suggest using size of the 2-core component to measure the connectivity of the local communities.