Search

There are many real world applications that require identifying public movements such as identifying movement corridors in cities and most popular paths. If one is not given user trajectories but rather sporadic location data, such as location-based social network data, finding movement related information becomes difficult. Rather than processing all points in a dataset given a query, a clever approach is to construct a graph, based on user locations, and query this graph to answer questions such as shortest paths, most popular paths, and movement corridors. Shortest path graph is one of the popular graphs. However, the shortest path graph can be inefficient and ineffective for analysing movement data, as it calculates the graph edges considering the shortest paths over all the points in a dataset. Therefore, edge sets resulting from shortest path graphs are usually very restrictive and not suitable for movement analysis because of its global view of the dataset. We propose the stepping stone graph, which calculates the graph considering point pairs rather than all points; the stepping stone graph focuses on possible local movements, making it both efficient and effective for location-based social network related data. We demonstrate its capabilities by applying it in the Location-Based Social Network domain and comparing with the shortest path graph. We also compare its properties to a range of other graphs and demonstrate how stepping stone graph relates to Gabriel graph, relative neighbourhood graph, and Delaunay triangulation.

In this paper, we define morphological topology (\(\mathcal {M}\)-topology) on intuitionistic fuzzy graph (IFG). We also define neighbourhood graph, continuity and isomorphism between \(\mathcal {M}\)-topologies.

As the visual reflections of our daily lives, images are frequently shared on the social network, which generates the abundant 'metadata' that records user interactions with images. Due to the diverse contents and complex styles, some images can be challenging to recognise when neglecting the context. Images with the similar metadata, such as 'relevant topics and textual descriptions', 'common friends of users' and 'nearby locations', form a neighbourhood for each image, which can be used to assist the annotation. In this paper, we propose a Metadata Neighbourhood Graph Co-Attention Network (MangoNet) to model the correlations between each target image and its neighbours. To accurately capture the visual clues from the neighbourhood, a co-attention mechanism is introduced to embed the target image and its neighbours as graph nodes, while the graph edges capture the node pair correlations. By reasoning on the neighbourhood graph, we obtain the graph representation to help annotate the target image. Experimental results on three benchmark datasets indicate that our proposed model achieves the best performance compared to the state-of-the-art methods.

© 2019 IEEE. Maximal clique enumeration is a fundamental problem in graph database. In this paper, we investigate this problem in the context of spatial database. Given a set P of spatial objects in a 2-dimensional space (e.g., geo-locations of users or point of interests) and a distance threshold r, we can come up with a spatial neighbourhood graph Pr by connecting every pair of objects (vertices) in P within distance r. Given a clique S of Pr, namely a spatial clique, it is immediate that any pairwise distance among objects in S is bounded by r. As the maximal pairwise distance has been widely used to capture the spatial cohesiveness of a group of objects, the maximal spatial clique enumeration technique can identify groups of spatially close objects in a variety of location-based-service (LBS) applications. In addition, we show that the maximal spatial clique enumeration can also be used to identify maximal clique pattern instances in the co-location pattern mining applications. Given the existing techniques for maximal clique enumeration, which can be immediately applied on the spatial neighbourhood graph Pr, two questions naturally arise for the enumeration of maximal spatial cliques: (1) the maximal clique enumeration on general graph is NP hard, can we have a polynomial time solution on the spatial neighbourhood graph? and (2) can we exploit the geometric property of the spatial clique to speed up the computation? In this paper, we give a negative answer to the first question by an example where the number of maximal spatial cliques is exponential to the number of the objects. While the answer to the second question is rather positive: we indeed develop two pruning techniques based on geometric properties of the maximal spatial clique to significantly enhance the computing efficiency. Extensive experiments on real-life geolocation data demonstrate the superior performance of proposed methods compared with two baseline algorithms.

In this paper, we present a study on sample preselection in large training data set for CNN-based classification. To do so, we structure the input data set in a network representation, namely the Relative Neighbourhood Graph, and then extract some vectors of interest. The proposed preselection method is evaluated in the context of handwritten character recognition, by using two data sets, up to several hundred thousands of images. It is shown that the graph-based preselection can reduce the training data set without degrading the recognition accuracy of a non pretrained CNN shallow model., Paper of 10 pages. Minor spelling corrections brought regarding the v2. Accepted as an oral paper in the 13th IAPR Internationale Workshop on Document Analysis Systems (DAS 2018)

Grafy sousednosti (proximity), jako je graf nejbližších sousedů, nejbližší dvojice, graf relativního sousedství a graf k nejbližších sousedů jsou nástroje užitečné v mnoha problémech, kde se zkoumají vzájemné vztahy, podobnost a blízkost objektů. Článek se věnuje vztahu grafů sousednosti k lokálně minimální triangulaci (LMT) a ukazuje, že ve většině případů LMT obsahuýje všechny hrany Neighbourhood (or proximity) graphs, such as nearest neighbour graph, closest pairs, relative neighbourhood graph and k-nearest neighbour graph are useful tools in many tasks inspecting mutual relations, similarity and closeness of objects. Some of neighbourhood graphs are subsets of Delaunay triangulation (DT) and this relation can be used for efficient computation of these graphs. This paper concentrates on relation of neighbourhood graphs to the locally minimal triangulation (LMT) and shows that, although generally these graphs are not LMT subgraphs, in most cases LMT contains all or many edges of these graphs. This fact can also be used for the neighbourhood graphs computation, namely in kinetic problems, because LMT computation is easier.

We study the problem of finding large cuts in $d$-regular triangle-free graphs. In prior work, Shearer (1992) gives a randomised algorithm that finds a cut of expected size $(1/2 + 0.177/\sqrt{d})m$, where $m$ is the number of edges. We give a simpler algorithm that does much better: it finds a cut of expected size $(1/2 + 0.28125/\sqrt{d})m$. As a corollary, this shows that in any $d$-regular triangle-free graph there exists a cut of at least this size. Our algorithm can be interpreted as a very efficient randomised distributed algorithm: each node needs to produce only one random bit, and the algorithm runs in one synchronous communication round. This work is also a case study of applying computational techniques in the design of distributed algorithms: our algorithm was designed by a computer program that searched for optimal algorithms for small values of $d$., 1+17 pages, 8 figures

This paper introduces a new kind of geometric graph, called the degree-sensitive neighbourhood graph (dNNG), for a more precise modelling of neighbourhoods. Based on dNNG, we define better shape-based metrics and then propose a neighbourhood-driven force-directed algorithm, called NEFO, for neighbourhood faithfulness. Our evaluation on both real-world and randomly generated graphs shows that the dNNG gives more effective shape-based measures when compared to existing geometric graphs. The NEFO algorithm is shown to be effective for improving neighbourhood faithfulness of graph drawings.

A subset D of vertices of a graph G is called a global neighbourhood dominating set(gnd - set) if D is a dominating set for both G and GN, where GN is the neighbourhood graph of G. The global neighbourhood domination number(gnd - number) is the minimum cardinality of a global neighbourhood dominating set of G and is denoted by γ gn(G). In this paper sharp bounds for γ gn, are supplied for graphs whose girth is greater than three. Exact values ofthis number for paths and cycles are presented as well. The characterization result for a subset ofthe vertex set of G to be a global neighbourhood dominating set for G is given and also characterized the graphs of order n having gnd -numbers 1, 2, n — 1,n — 2, n.

Recent advances in molecular biology and Bioinformatics techniques brought to an explosion of the information about the spatial organisation of the DNA in the nucleus. High-throughput chromosome conformation capture techniques provide a genome-wide capture of chromatin contacts at unprecedented scales, which permit to identify physical interactions between genetic elements located throughout the human genome. These important studies are hampered by the lack of biologists-friendly software. In this work we present NuchaRt, an R package that wraps NuChart-II, an efficient and highly optimized C++ tool for the exploration of Hi-C data. By rising the level of abstraction, NuchaRt proposes a high-performance pipeline that allows users to orchestrate analysis and visualisation of multi-omics data, making optimal use of the computing capabilities offered by modern multi-core architectures, combined with the versatile and well known R environment for statistical analysis and data visualisation.

Long-range chromosomal associations between genomic re- gions, and their repositioning in the 3D space of the nucleus, are now considered to be key contributors to the regulation of gene expressions, and important links have been highlighted with other genomic features involved in DNA rearrangements. Recent Chromosome Conformation Capture (3C) measurements performed with high throughput sequenc- ing (Hi-C) and molecular dynamics studies show that there is a large correlation between co-localization and co-regulation of genes, but these important researches are hampered by the lack of biologists-friendly anal- ysis and visualisation software. In this work we present NuChart-II, a software that allows the user to annotate and visualize a list of input genes with information relying on Hi-C data, integrating knowledge data about genomic features that are involved in the chromosome spatial or- ganization. This software works directly with sequenced reads to identify related Hi-C fragments, with the aim of creating gene-centric neighbour- hood graphs on which multi-omics features can be mapped. NuChart-II is a highly optimized implementation of a previous prototype package de- veloped in R, in which the graph-based representation of Hi-C data was tested. The prototype showed inevitable problems of scalability while working genome-wide on large datasets: particular attention has been paid in optimizing the data structures employed while constructing the neighbourhood graph, so as to foster an efficient parallel implementation of the software. The normalization of Hi-C data has been modified and improved, in order to provide a reliable estimation of proximity likelihood for the genes.

High-throughput molecular biology techniques are widely used to identify physical interactions between genetic elements located throughout the human genome. Chromosome Conformation Capture (3C) and other related techniques allow to investigate the spatial organisation of chromosomes in the cell's natural state. Recent results have shown that there is a large correlation between co-localization and co-regulation of genes, but these important information are hampered by the lack of biologists-friendly analysis and visualisation software. In this work we introduce NuChart-II, a tool for Hi-C data analysis that provides a gene-centric view of the chromosomal neighbourhood in a graph-based manner. NuChart-II is an efficient and highly optimized C++ re-implementation of a previous prototype package developed in R. Representing Hi-C data using a graph-based approach overcomes the common view relying on genomic coordinates and permits the use of graph analysis techniques to explore the spatial conformation of a gene neighbourhood.

The implication of semi-supervised method has become crucial to automate tasks that require the manual human expertise for data labelling, the advantage of this method resides in the fact that they require a low amount of labelled information. In this work, we are particularly interested in self-training paradigm. These techniques use the same principle as those of supervised techniques, but with a confidence measure that allows only a selection of the most confident samples. We propose a novel self-training algorithm named reinforced confidence in self-training (R-COSET) based on an iterative process. In each iteration the learned hypothesis can be improved by confidence data, where the proposed confidence measure is reinforced by two confidence levels in order to increase the robustness of the self-training process. Experiments show that the introduction of the second level of the neighbourhood graph in confidence measure is beneficial and that R-COSET can effectively improve classification performance.

Let V(G) be the set of points of G. The open neighbourhood N(u) of a point u. in V(G) is the set of points adjacent to u. The closed neighbourhood N[u] of a point u in V(G) is given by . For each point vi of G, we take a new point ui and the resulting set of points is denoted by V 1(G). The total closed neighbourhood graph Ntc (G) of a graph G is defined as the graph having point set V(G) ⋃ V 1(G) with two points as adjacent if they correspond to two adjacent points of G or one corresponds to a point ui of V 1(G) and the other to a point wj of G where wj is in N[vi ]. In this paper, we present characterization of graphs whose total closed neighbourhood graphs are planar, outerplanar, minimally nonouterplanar. We give characterizations of graphs with planar total closed neighbourhood graphs and outerplanar total closed neighbourhood graphs in terms of forbidden subgraphs.

In this paper we deal with the heuristic solution of the classical job shop problem. Both the constructive and the iterative phase of our algorithm apply insertion techniques combined with beam search. In the first phase we successively insert the operations into feasible partial schedules. In the iterative phase we generate paths in a particular neighbourhood graph instead of investigating the neighbourhood completely. To select “interesting” neighbours, we use the combinatorial path structure of feasible solutions of the job shop problem. The results of our algorithm are compared with those from other well-known methods on benchmark problems.

In this paper, we studied the flocking motion of multiple agents in mixed absolute/relative navigation condition with communication. The difference between navigation and communication in the role taken part in the neighbourhood relations was firstly pointed out. We gave a criterion which can judge whether a communication neighbourhood graph with mixed absolute/relative navigation devices is connected. We also proposed an algorithm to achieve the absolute navigation using the communication. Based on above preliminaries, we design a control law to stabilize the flocking motion of multiple agents whose dynamics are nonlinear with noise. The simulation in three different scenarios was performed and the corresponding results illustrated the effectiveness of the control law.

John Horton Conway’s Game of Life is a simple two-dimensional, two state cellular automaton (CA), remarkable for its complex behaviour. That behaviour is known to be very sensitive to a change in the CA rules. Here we continue our investigations into its sensitivity to changes in the lattice, by the use of an aperiodic Penrose tiling lattice.

When a graph is embedded in a surface, the faces that result can be regarded as the blocks of a combinatorial design. The resulting design may be thought of as being embedded in the surface. This perspective leads naturally to a number of fascinating questions about embeddings, in particular about embeddings of Steiner triple systems and related designs. Can every Steiner triple system be embedded, can every pair of Steiner triple systems be biembedded, and how many embeddings are there of a given type?

In this paper we propose a heuristic for the reconstruction of a planar curve from a noisy sample. This is based on an earlier scheme we had proposed for reconstructing a curve from a noise-free sample, based on the relative neighbourhood graph. We also report on the performance of our heuristic on a variety of noisy samples.

This paper addresses a special type of graph, the k-neighbourhood graph, for the usage in huge multi agent systems. It can be used to establish slim communication structures in extensive groups of agents as they are present e.g. in swarm applications. We will prove some properties of k-neighbourhood graphs in two- and three-dimensional Euclidean space, i.e. we show that the maximum number of incoming connections per agent is limited to a value independent from the overall number of agents in the system. For the two-dimensional case we prove a maximum in-degree of 6 ·k. Furthermore, for agents interacting in three dimensions an upper and a lower bound for this value is presented.

International audience; To develop a method for structured document recognition, it is necessary to know the relative position of the graphical elements in a document. In order to deal with this notion, we build a neighbourhood graph based on Vorono¨ı tessellation. We propose to combine the use of this interesting notion of neighbourhood with an existing generic document recognition method, DMOS, which has been used to describe various kinds of documents. This association allows exploiting different aspects of the neighbourhood graph, separating the graph analysis from the knowledge linked to a kind of document. Thus, we set up a cooperation between neighbourhood graph, that contains numerical information, and DMOS method, that can convert this data into symbolic information. Moreover, DMOS method can specify a context of analysis when exploiting neighbourhood graph, which makes it possible to establish a bidirectional relation between the analyser and the graph. We apply this method on the analysis of various documents.

This paper is concerned with the neighbourhood-based supervised learning of a continuous class. It deals with identifying and handling outliers. We first explain why and how to use the neighbourhood graph issued from predictors in the prediction of a continuous class. Global quality of the representation is evaluated by a neighbourhood autocorrelation coefficient derived from the Moran spatial autocorrelation coefficient. Extending the analogy with spatial analysis, we suggest to identify outliers by using the scattering diagram associated to the Moran coefficient. Several experiments realized on classical benchmarks show the interest of removing the outliers with this new method.

The aim of this paper is to explore the sensitivity of relational matching to attribute and structural information. Broadly speaking there are two main aspects to this study. First, we determine the relative importance of attribute and structural information in matching noise corrupted graphs. The second aspect of our analysis concerns the nature of the relational structures used in matching. Here we compare the matching results obtained using four different graph structures, namely the Delaunay graph, the N-nearest neighbour graph, the Gabriel graph and the relative neighbourhood graph. Our results are presented as noise sensitivity curves. The main conclusion of the study is that attributes are essential when the fractional corruption exceeds 20% and that the Delaunay graph has optimal noise robustness.

Image segmentation in mathematical morphology is essentially based on one method: the watershed of a gradient image from a set of markers. We show that this watershed can be obtained from the neighbourhood graph of the initial image. The result of the segmentation is then a minimum spanning forest of the neighbourhood graph. Powerful interactive and very fast segmentation methods are derived

The following geometrical proximity concepts are discussed: relative closeness and geographic closeness. Consider a setV={v 1,v 2, ...,v n } of distinct points in atwo-dimensional space. The pointv j is said to be arelative neighbour ofv i ifd p (v i ,v j )≤max{d p (v j ,v k ),d p (v j ,v k )} for allv k ∈V, whered p denotes the distance in theL p metric, 1≤p≤∞. After dividing the space around the pointv i into eight sectors (regions) of equal size, a closest point tov i in some region is called anoctant (region, orgeographic) neighbour ofv i. For anyL p metric, a relative neighbour ofv i is always an octant neighbour in some region atv i. This gives a direct method for computing all relative neighbours, i.e. for establishing therelative neighbourhood graph ofV. For every pointv i ofV, first search for the octant neighbours ofv i in each region, and then for each octant neighbourv j found check whether the pointv j is also a relative neighbour ofv i. In theL p metric, 1

The method of differences is used to establish that every 2-regular multigraph onv− 1≡0,2 (mod 3) points occurs as the neighbourhood graph of an element in a twofold triple system of orderv, with two exceptions: C2∪C3and C3∪C3.