Search

Neural simulation is a very useful methodology for improving our understanding of the functions of brains, and expected to be applied to a number of practical applications related to autonomous systems and machines. However, computation time required for biophysically-meaningful simulation is often the limiting factor to mimic the large-scale neural network even if we implement custom hardware simulators on FPGAs. To overcome this issue, we focus on the spatial network connectivity of biological neurons and attempt to design a truly dataflow pipeline on FPGAs aiming at real-time Hodgkin-Huxley based simulation against more than 10,000 neurons. We implement our design on Xilinx Alveo U200 with HLS toolchains provided by Maxeler. From the results of evaluation, we find that mapping locality of neurons to the network connecting only to neighboring ones dramatically contributes to reducing the overheads for accumulation at the gap junction calculation. We demonstrate that our accelerator design can perform real-time simulation of network consisting 20736 neurons, which is 66.8 times larger than the existing implementation.

Timely and accurate crop type classification plays an essential role in the study of agricultural application. How-ever, large area or cross-regional crop classification confronts huge challenges owing to dramatic phenology discrepancy among training and test regions. In this work, we propose a novel framework to address these challenges based on deep recurrent network and unsupervised domain adaptation (DA). Specifically, we firstly propose a Temporal Spatial Network (TSNet) for pixelwise crop classification, which contains stacked RNN and self-attention module to adaptively extract multi-level features from crop samples under various planting conditions. To deal with the cross-regional challenge, an unsupervised DA-based framework named Phenology Alignment Network (PAN) is proposed. PAN consists of two branches of two identical TSNet pre-trained on source domain; one branch takes source samples while the other takes target samples as input. Through aligning the hierarchical deep features extracted from two branches, the discrepancy between two regions is decreased and the pre-trained model is adapted to the target domain without using target label information. As another contribution, a time series dataset based on Sentinel-2 was an-notated containing winter crop samples collected on three study sites of China. Cross-regional experiments demonstrate that TSNet shows comparable accuracy to state-of-the-art methods, and PAN further improves the overall accuracy by 5.62%, and macro average F1 score by 0.094 unsupervisedly.

We consider 1-local online routing on a special class of geometric graphs called Delaunay triangulations (DTs). A geometric graph G = (V, E) of a point set consists of a set of points in the plane and edges between them, where each edge weighs as the Euclidean distance between it’s end-points. DTs are one of the useful classes of these graphs because of some good properties which can help during the navigation process, therefore over the years DTs have been widely proposed as network topologies for several times.In this paper, we present a new memoryless online routing (MOR) algorithm for DTs which is simple, elegant, and easy to implement, while having an acceptable performance.The set of MOR algorithms are suitable for cases where we want to find a path using only local information, our proposed algorithm is memoryless or 1-local, in k-local routing, we find a path between a source vertex s to a destination vertex t while our knowledge at each step is limited to the locations of s and t, the location of current vertex and it’s k-neighborhood vertices.We also evaluate and compare the perforamnce of our prpopsed algorithm with existing MOR algorithms. Our experimental results implied that our proposed algorithm has an acceptable performance in both Euclidean and link metrics and it outperforms all of the existing MOR algorithms in Euclidean metric, and some of them in the link metric as well. Finally, we pose two open problems to solve in the future.

We present a new measure, CMetric, to classify driver behaviors using centrality functions. Our formulation combines concepts from computational graph theory and social traffic psychology to quantify and classify the behavior of human drivers. CMetric is used to compute the probability of a vehicle executing a driving style, as well as the intensity used to execute the style. Our approach is designed for realtime autonomous driving applications, where the trajectory of each vehicle or road-agent is extracted from a video. We compute a dynamic geometric graph (DGG) based on the positions and proximity of the road-agents and centrality functions corresponding to closeness and degree. These functions are used to compute the CMetric based on style likelihood and style intensity estimates. Our approach is general and makes no assumption about traffic density, heterogeneity, or how driving behaviors change over time. We present an algorithm to compute CMetric and demonstrate its performance on real-world traffic datasets. To test the accuracy of CMetric, we introduce a new evaluation protocol (called "Time Deviation Error") that measures the difference between human prediction and the prediction made by CMetric., Comment: Accepted to IROS 2020

The evolution of cooperation can be investigated using Prisoners’ Dilemma game(PD) models on spatial networks. It has been shown that other-regarding preferences, such as inequality aversion, a taste for fairness, or reciprocal preference, can cause cooperative behavior to evolve. In this paper, we consider whether relationships among agents, alone or in combination with reciprocal preference, can drive cooperation. We study the emergence of cooperation in PD games on a two-dimensional spatial network where some individuals are reciprocators, altering their future behavior based on comparison with a randomly chosen neighbor. Simulation results show that, if the intensity of reciprocal preference is fixed, the frequency of cooperation increases with the fraction of reciprocators. When reciprocal preference intensity is high, a low level of cooperation can be sustained, even if there are few reciprocators -- though cooperation does not diffuse through the population. We also show that the particular linking rule matters, in that cooperators are more likely to survive under a Cooperate-Stay, Defect-Shift (CSDS) linking rule, as opposed to a Win-Stay, Lose-Shift (WSLS) rule. As the fraction of reciprocators increases, the CSDS rule provides a more favorable environment for the evolution of cooperation. In addition, there is a threshold fraction of reciprocators such that a large value of network evolution strength contributes to cooperation most the threshold is exceeded. On the other side of the threshold, stronger reciprocal preference intensity does not necessarily promote cooperation more powerfully. Our results provide insight into how relations between neighbors can be a potent force, in combination with reciprocal preference, in inducing cooperation.

Based on the perspective of supply and demand, this study takes Xinjiang in China as an example, and uses tourist attractions as elements of the spatial object to identify the spatial structure of tourism in Xinjiang with the help of GIS spatial analysis function. On this basis, this study will optimize the spatial network of tourism. The results in this study show that: (1) In terms of supply side and demand side, the tourist attractions in Xinjiang all present a clustered distribution trend. Compared with the space of scenic areas on supply side, that on demand side has a smaller distribution range. And they are concentrated along Tianshan Mountain and in the northern region of Altay; (2) In Xinjiang, the accessibility of tourist attractions is poor, and tourist attractions on demand side is slightly higher than that on supply side; (3) In the system of tourism network space on supply and demand side, the tourism scenic areas in Xinjiang have the phenomenon of stratified clustering, and there is a significant trend of cohesion development; (4) According to the identification results of supply-side and demand-side tourism spatial structure, this study will integrate the core tourist attractions, build and improve their traffic system of roads, so as to construct a “Three-axis, Four-core and Four-group” tourism spatial network. At the same time, this study will provide a new idea for the identification and optimization of regional tourism spatial structure, so as to provide a scientific reference for the construction of tourist attractions, the design of tourist routes and the integration of tourism resources.

Effective video representation is a key ingredient in action recognition, but how to learn effective spatial features remains a fundamental and challenging task. The existing CNN-based methods apply low-resolution feature maps to get the high-level semantic labels. However, the slenderer spatial information for action representation has lost. In this paper, we propose a novel stacked spatial network (SSN), which integrates multi-layer feature maps in an end-to-end manner. Spatial features extraction network based on encoder-decoder is firstly used to obtain multi-level and multi-resolution spatial features under the supervision of high-level sematic labels. The multi-level features are aggregated through a stacked spatial fusion layer, which intrinsically refines the traditional convolutional neural network. Then, refined spatial network (RSN) is proposed to aggregate spatial network and SSN. Particularly, the learned representation of RSN comprises two components for representing semantic label information and local slenderer spatial information. Extensive experimental results on UCF-101 and HMDB-51 datasets demonstrate the effectiveness of the proposed RSN.

Studying the topology of cerebral microvessels has been shown to be essential for understanding the mechanisms underlying neurovascular coupling and brain microphysiology. One can derive topological models of these microvessels after labeling them based on their raw acquisitions from two-photon microscopy (TPM). However, adequate 3D mapping of cerebral microvasculature from TPM remains difficult due to the uneven intensities and shadowing effects. In this paper, we present a novel 2D/3D skeletonization solution to generate topological graph models of microvessels regardless of the quality of their binary maps. Our scheme first constructs a random initial graph encapsulated within the boundary of a binary mask. The vertices of the initial model are then iteratively contracted toward the centerline of microvessels by local connectivity-encoded gravitational forces. At each iteration, the model is decimated through vertices clustering and connectivity surgery processes. Lastly, a refinement algorithm is applied to convert the final decimated model into a curve skeleton. Synthetic angiograms and real TPM datasets are used for evaluation. By comparing against other efficient graphing schemes, we demonstrate that our solution performs better when applied to extract topological information from cerebral microvessel labels.

Modern navigation services often provide multiple paths connecting the same source and destination for users to select. Hence, ranking such paths becomes increasingly important, which directly affects service quality. We present PathRank, a data-driven framework for ranking paths based on historical trajectories. If a trajectory used path P from source s to destination d, PathRank considers this as an evidence that P is preferred over all other paths from s to d. Thus, a path that is similar to P should have a larger ranking score than a path that is dissimilar to P. Based on this intuition, PathRank models path ranking as a regression problem that assigns each path a ranking score. We first propose an effective method to generate a compact set of diversified paths using trajectories as training data. Next, we propose an end-to-end deep learning framework to solve the regression problem. In particular, a spatial network embedding is proposed to embed each vertex to a feature vector by considering the road network topology. Since a path is represented by a sequence of vertices, which is now a sequence of feature vectors after embedding, recurrent neural network is applied to model the sequence. Empirical studies on a substantial trajectory data set offer insight into the designed properties of the proposed framework and indicating that it is effective and practical.

In this paper, a flow-guided temporal-spatial network (FGTSN) is proposed to enhance the quality of HEVC compressed video. Specifically, we first employ a robust motion estimation subnet via trainable optical flow module to estimate the motion flow between the target frame and its adjacent frames, and these adjacent frames are pre-warped guided by the predicted motion flow. Then, a temporal encoder is proposed to fuse the related information between the target frame and its pre-warped frames. Finally, a quality enhancement subnet with multi-scale encoder-decoder structure is designed to generate high quality frame by training the network in a multi-supervised fashion. Experimental results show the superior performance of our proposed FGTSN method for the reconstruction quality of HEVC compressed frames, much better than the state-of-the-art quality enhancement methods. In addition, our FGTSN method can also effectively mitigate the quality fluctuation of adjacent frames.

In most scheduling problems, such as plant and supply chain problems, the linkages between resources, and operations are often clearly demarcated due to their lateral, sequential nature. In comparison, the combinatorial nature, arising from the inherent network structure of a flexible manufacturing system problem causes the associated jobs, automated guided vehicles and job shops to be intermeshed topologically and temporally. The temporal and spatial network structure impedes direct application of conventional decomposition approaches. In this study, a reusable scheduling problem decomposition framework for Industry 4.0 that facilitates agent embedded optimization is being proposed. Modularity is enabled when each agent and its respective governed resource or resource group is replaceable by one that is similar in functionality, but possibly of a different layout. This schema is attractive to potential schedulers as the plug-and-play nature of resources, via modularity, optimizes user friendliness via minimal customizations.

In this article, we analyze the limiting eigen-value distribution (LED) of random geometric graphs (RGGs). The RGG is constructed by uniformly distributing n nodes on the d-dimensional torus $\Gamma^{d}\equiv [0, 1]^{d}$ and connecting two nodes if their $\ell_{p}$-distance, $ p\in [1,\ \infty]$ is at most r n . In particular, we study the LED of the adjacency matrix of RGGs in the connectivity regime, in which the average vertex degree scales as $\log(n)$ or faster, i.e., $\Omega(\log(n))$. In the connectivity regime and under some conditions on the radius r n , we show that the LED of the adjacency matrix of RGGs converges to the LED of the adjacency matrix of a deterministic geometric graph (DGG) with nodes in a grid as n goes to infinity. Then, for n finite, we use the structure of the DGG to approximate the eigenvalues of the adjacency matrix of the RGG and provide an upper bound for the approximation error. Index Terms--Random geometric graphs, adjacency matrix, limiting eigenvalue distribution, Levy distance.

A hotsport is a reflection of dense areas of human activities in a city. Hotspots can be widely used in public applications, such as transport management, disease prevention and control, crowd management, environmental monitoring. Nevertheless, existing work mainly utilize static models to detect hotspots in spatial dimension, which ignores the evolving characteristic of hotspots in temporal dimension. Such work does not help to study the evolution law of man-land relationships behind the hotspots in real-life applications. In this paper, we propose a dynamic spatial network (DSN) considering evolving characteristics to discover hotspots (collective gathering, traffic congestion, and so on) in urban road networks. Based on the model, we propose a generate-and-test framework for hotspot detection, which generates the (k+1)-edge candidate hotspots based on the k-edge hotspots, and then tests each candidate if it is qualified and closed. Finally, experiments on real taxi data have verified the effectiveness and efficiency of the proposed concepts and algorithms.

For human pose estimation in videos, it is significant how to use temporal information between frames. In this paper, we propose temporal flow maps for limbs (TML) and a multi-stride method to estimate and track human poses. The proposed temporal flow maps are unit vectors describing the limbs' movements. We constructed a network to learn both spatial information and temporal information end-to-end. Spatial information such as joint heatmaps and part affinity fields is regressed in the spatial network part, and the TML is regressed in the temporal network part. We also propose a data augmentation method to learn various types of TML better. The proposed multi-stride method expands the data by randomly selecting two frames within a defined range. We demonstrate that the proposed method efficiently estimates and tracks human poses on the PoseTrack 2017 and 2018 datasets., Comment: Won the Honorable Mention Award in the 18'ECCV PoseTrack challenge. Accepted in the 19'IJCNN conference

In this study, we focus on the efficient disintegration method in spatial networks. First, we present an optimization model for the disintegration strategy in the spatial network and introduce a heuristic algorithm to seek the efficient disintegration strategy. Experiment in American fiber network indicates that our method could seek the efficient disintegration strategy with the tabu search. Also, the disintegration effect based on tabu search substantially exceeds the degree-core strategy and betweenness-core strategy.

In this work, we consider the problem of online centralized kinodynamic multi-robot replanning (from potentially non-stationary initial states) and coordination in known and cluttered workspaces. Offline state lattice reachability analysis is leveraged to decouple the planning problem into two sequential graph searches–one in the explicit geometric graph of the environment and the other in the graph of the higher-order derivatives of the robot’s state–in a manner such that the intermediate vertices of a safe set of geometric paths are guaranteed to have a feasible assignment of higher-order derivatives. Without additional iterative refinement procedures, the resulting time parameterized polynomial trajectories are dynamically feasible and collision-free. Planning results with up to 20 robots in two and three dimensional workspaces suggest the suitability of the proposed approach for multi-robot replanning in known environments.

Presently a days remarkable improvement of the web innovation and sensor innovation, the worldwide spatial information, alongside its huge volume and multi-scale highlights, clarifies higher prerequisites for information association. The spatial network has been generally utilized in many guide list. In any case, when spatial articles have multi-scale, the spatial matrix list with proportionate networks has been critized for its low-efficiencies. To tackle this issue, here proposed an intelligent list just as upset record dependent on GeoSOT subdivision lattices. By methods for this list, we can accomplish question task productively paying little heed to the sizes of spatial articles.

The variety of local geology conditions gives rise to different destructive effects caused by disasters on network links at different locations. To cope with these effects on optical networks, we propose a network planning approach considering empirical seismic hazard constraints. Our method is to find two appropriate geographical paths (working and protection path) for network links under certain cost constraint. The introduced cost metrics aim at maximizing the robustness of the network and minimizing the joint failure probability of the paths. The survivability of a physical network against natural disaster is analyzed and a spatial network planning scheme is proposed based on physical layer effects. In addition to reducing the probability of service loss, the cost of connection is decreased and the quality of received signal is also improved. The numerical simulation results on a telecommunication network in Iran show doubling of average received SNR by maintaining the loss of service probability around 0.0017.

With massive real-world networks added with spatial attributes, query processing in spatial networks has been widely used in real-life applications. Considering the high costs of spatial network queries, outsourcing querying services to cloud provides a cost-effective way for data owners. However, directly outsourcing such services may cause serious privacy concerns. To address this privacy problem, existing studies apply anonymous or differential privacy techniques on spatial network queries, which are not under the semi-trusted secure model. Other existing works primarily focus on query processing over either encrypted spatial or network data, which cannot directly be applied to work out the secure spatial network query problem. To this end, we define and study Secure Spatial Network kNN Query (SSNQ) problem on cloud platform. We first present Basic Secure Spatial Network kNN Query (BSSNQ) method, in which we compute secure kNN for the query node to construct candidate sequences using secure subprotocols. With pre-encrypted network distances, we then compute shortest paths between the query node and each candidate, and securely update the candidate sequences according to Euclidean restriction to derive final query results. To improve the efficiency of BSSNQ, we further propose Heuristic Secure Spatial Network kNN Query (HSSNQ) method, which securely calculates shortest paths from the query node to the visiting nodes iteratively, and use optimistic estimate distances as the key to lead the heuristic search within a priority queue. Thorough analysis shows the security and complexity of the proposed methods, and extensive experimental results on real datasets demonstrate the efficiency of the query performance.

Contour extraction is a fundamental problem in computer vision, and widely applied to visual projects. However, for some scenes with complex background or objects to be extracted are similar to background, traditional methods seem powerless. In this paper, we present a new approach to tackle this problem. Given an image sequence, the approach is decomposed into two main phases: background modeling, contour extracting. In the first phase, Gaussian mixture distribution is applied to build the background model in dynamic environment. In the second phase, we map the segmented foreground pixels to a two-dimensional point set, through which we construct a geometric graph based on Euclidean distance, and then all border nodes are connected to generate the contour using the orientation information. Actual project results show that the approach is capable of generating contours with high accuracy and strong robustness.

With the continuous development of satellite technology, to achieve a complete and reliable information transmission has become a hot space information technology research, building space information network is imperative. Aiming at the characteristics of the existing spatial information network structure and the complexity of technical problems, the spatial network is studied and analyzed according to the method of functional classification and structure stratification. Firstly, the networking structure of spatial comprehensive information network is introduced. Then the existing spatial information network is classified according to the functional purpose, and the existing spatial network system research status is introduced according to the category. Finally, the spatial network is divided by the idea of analog stratification. The research hotspots of each layer are introduced, and the key technologies of spatial routing are analyzed.

With the advancement and development of urbanization in China, human activities are closely related to the changes in the internal structure and external layout of the city. The human migration model reflects the internal structure of the city to some extent. In two places where the city is far apart, the layout is very similar, and people's activities may also have certain similarities. Inspired by Graphwave, the city's spatial network was constructed using data from human travel. It was found that the city's more important and potentially influential areas of urban functioning. This paper uses the data of Shanghai Mobike and taxis to build a network, identifies the similarity nodes in the city, uses the POI data set to verify the final data, and explains its important geographical significance. Experiments show that similarity nodes are mostly distributed in schools and communities, and are relatively close to transportation hubs.

We propose a B-spline deformation model, which can be efficiently updated from sequential measurements. Our incremental update is based on the Kalman filtering, is optimal in the least squares sense, and is very fast, an order of magnitude faster than the direct methods, while converging to the same solution. While this method can be applied to any multidimensional scattered data interpolation task, our main application is a geometric graph matching algorithm, which is used for registering large images from the biomedical domain or remote sensing, based on matching linear structures such as blood vessels or roads. The B-spline transformation model needs to be updated incrementally as more points are added to the match and using the proposed Kalman-like update yields substantial speed gains over the previously used bi-Lipschitz model.

Resting state fMRI (rsfMRI) has been used widely to explore intrinsic brain activities and networks. Although there are a large number of model-driven and data-driven methods that have been employed to model rsfMRI data, it is challenging to model longitudinal rsfMRI data given the time gaps. Currently, sparse dictionary learning (SDL) method has already shown great promise and attracted increasing attention in the rsfMRI research field. The vital advantage of this SDL methodology is that it can identify concurrent brain networks efficiently and systematically. However, the current SDL is not directly applicable to longitudinal rsfMRI data with multiple time points. In response, we propose a longitudinal supervised stochastic coordinate coding (LSSCC) algorithm for longitudinal rsfMRI data analysis. At the first time point, concurrent brain networks are learned and approximated based on the spatial network templates by SDL with l 2 norm. Then, the learned networks at the first time point are transferred to the following time points and the LSSCC is employed to conduct the approximations of functional networks longitudinally. The application of LSSCC on the ADNI-2 longitudinal rsfMRI datasets has shown the effectiveness of our proposed methods.

The aerospace-based communications can be managed more efficiently through the construction of an integrated space/air information network by the convergence of satellite (space) and unmanned aerial vehicle (air) networks. Such an integrated network would best fit the advent of delay- and disruption-tolerant networking, in which the data transmission can tolerate long delay and disruption under a store-carry-forward mechanism. Such a network, however, has some challenging research needs due to the network’s high mobility of nodes and time-varying topology that may result in high error bit rate and long delay. In this paper, we propose a unified routing framework for this integrated network, where a Hybrid time-space Graph supporting Hierarchical Routing (HGHR) algorithm is achieved. More specifically, the HGHR performs on a hybrid time-space graph, including two subgraphs: a deterministic graph for the space network and a semi-deterministic one for the air network. This latter graph is based on a discrete time homogeneous semi-Markov prediction model. The hybrid time-space graph is then transformed into a state-space graph, based on which, a message forwarding rule under the store-carry-forward mechanism is adopted. Simulation results show that the proposed HGHR algorithm has good performance in terms of message delivery ratio, end-to-end delay, and power consumption.

Group centrality is an extension of the conventional node centrality in which the importance of a group of nodes together is the target for performance evaluation. We used this notion and formulated a link creation problem to a spatial network. The kind of problem we want to solve is to find the best places to construct k new roads to maximize the evacuation performance. The problem is formulated as an optimization problem to maximize the gain of the group closeness centrality by creating a set of new roads (k links) with the constraints on the road range distance (link length limit Δ). The problem is NP-hard. We show that this problem is reduced to a node selection problem and the objective function is submodular when there is no constraint on the link length limit. We devised an efficient greedy algorithm to search for the best k new roads under the constraint of Δ that comprises three steps: centrality calculation, parents selection and nodes selection. We applied this algorithm to three real road networks of different cities and evaluated its performance with respect to k and Δ. The algorithm is quite efficient and obtains the efficiency gain of 10^3 to 10^6 compared with a naive method in which every single node is blindly tested as a candidate from which to create a new road.

Ultra dense networks (UDN) are treated as a promising technology to meet the challenges of the future wireless communications where interference plays an important role in the network performance. Interference alignment (IA) has been considered to be a resultful technique for achieving the optimal capacity scaling. However, in practical communication system, mitigating all interference via IA requires heavy signaling overhead and high iteration complexity. In this paper, we propose a dynamic clustering algorithm based on graph partitioning with low complexity. Our work focuses on dividing the whole network into a number of clusters under size constraint and realizes the maximum intra-cluster interference and minimum inter-cluster interference. In addition, neighbor selecting scheme based on neighbor interference ratio (NIR) in proposed algorithm can get the proper cluster result in the random spatial network model. Furthermore, proposed algorithm is compared with other traditional algorithms in complexity and performance. The simulation results show that proposed algorithm reduces the complexity of clustering process significantly and achieves average 7% higher performance gain than existing clustering algorithms.

In this paper, we propose a novel algorithm for intelligent drawing based on context awareness in dynamic geometry system. First, the algorithm collects the context information of geometric graph. Second, during the user is drawing, if the user's current operations and context information meet a matching condition, the algorithm will recommend the next graph to be drawn. With this algorithm, users can accurately and efficiently draw more than twenty kinds of geometric graphs only by mouse operations and without clicking toolbar button or menu. Through the experiments, we demonstrate the simplicity, effectiveness, and efficiency of our algorithm.1

Extracting spatial-temporal descriptors is a challenging task for video-based human action recognition. We decouple the 3D volume of video frames directly into a cascaded temporal spatial domain via a new convolutional architecture. The motivation behind this design is to achieve deep nonlinear feature representations with reduced network parameters. First, a 1D temporal network with shared parameters is first constructed to map the video sequences along the time axis into feature maps in temporal domain. These feature maps are then organized into channels like those of RGB image (named as Motion Image here for abbreviation), which is desired to preserve both temporal and spatial information. Second, the Motion Image is regarded as the input of the latter cascaded 2D spatial network. With the combination of the 1D temporal network and the 2D spatial network together, the size of whole network parameters is largely reduced. Benefiting from the Motion Image, our network is an end-to-end system for the task of action recognition, which can be trained with the classical algorithm of back propagation. Quantities of comparative experiments on two benchmark datasets demonstrate the effectiveness of our new architecture.

We study compressed sensing of graph signals defined over complex networks. In particular, we propose and analyze a convex optimization method for recovering smooth graph signals from a small number of samples. Assuming the true underlying graph signal to be constant over well connected subset of nodes (clusters), we derive a sufficient condition on the sampling set and network structure such that the proposed convex method is accurate. This condition, which we coin the network nullspace property, characterizes which nodes of the graph should be sampled in order to retain the full information about the underlying graph signal.

Human mobility patterns have been widely investigated due to the application in various fields, such as urban planning and epidemiology. However, most existing researches mainly focus on human mobility patterns at the individual level. In this paper, we analyze collective mobility patterns using data usage detail records (UDRs) for over one million users from the cellular networks in a city of China. We first construct spatial networks where nodes represent base stations (BSs) and edge weights denote users' moving strength between BSs. The difference between communities detected from the networks are then identified. Finally, we discover users with different mobility patterns according to the community difference. Experimental results show that our method can effectively discover users with different mobility patterns. Moreover, we analyze different collective mobility patterns between the Spring Festival vacation and workdays combined with geographical information. Results show that human collective mobility are not always constrained by administrative boundaries, but also affected by social and environmental factors, such as transportations, geographical barriers and area economic types, etc. Besides, the discovered collective mobility patterns can be used to reveal spatial relationship, providing a new insight of human activity pattern and spatial interaction analysis.

In real life networks like social and biological networks, the network is said to have community structure if the vertices of the network can be partitioned into groups of nodes such that each group contains the nodes that are densely connected in the original graph that represents this network. These groups are referred to as communities. Detecting and identifying communities in networks is essential in many domains. The paper proposes a simple method for detecting communities that is based on the node clustering coefficient which is a local structural property of the graph underlying the network. The clustering value indicates the clique formation among the node neighbors.

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.

Disseminating content to a given subset of nodes in a network in a cost-effective manner is a fundamental problem in networks, and is referred to as multicast. If reaching all the nodes in the set is not necessary and reaching a quorum of size k within the set is sufficient, then the problem is referred to as k-anycast or any-k-cast. This has applications in a wide range of networks, e.g., function computation in spatial wireless networks such as sensor networks and influence flow in social networks. Since the k-anycast optimization problem is NP-complete, we propose two heuristic algorithms to address the problem: the first is based on greedy growth from the root node and the second is based on pruning from a larger multicast tree. We perform a comparative numerical study of their performance tradeoffs for a social collaboration network and a spatial network by evaluating the effect of terminal node distributions on the cost and exploration overhead of the k-anycast tree for different regimes of k for each network.

Dense small cell networks have been considered as a promising solution for improving system throughput in the future 5G networks. When a large number of small cells are overlapped, serious inter-cell interference (ICI) becomes one of the major technical challenges. Meanwhile, the energy efficiency (EE) of dense small cell networks is of great concern. So, in this paper, we attempt to explore the potential of EE of cooperative dense small cell networks with caching at each small cell base stations (SCBS). By adopting a random spatial network model, we formulate the user-centric cooperative interference mitigation strategy and derive an approximate expression of the successful transmission probability to the typical user. By deriving the closed-form expression of the EE based on interference mitigation method, we analyze the relationship between EE and the cache hit ratio. Through numerical and simulation based on analysis, we demonstrate the feasibility and validity of our analysis.

Degree distribution, hierarchy, clustering and small-world are typical graph features to measure the structure of complex networks. This paper uses these features to compare and evaluate the performances of biased and unbiased sampling algorithms on two types of scale-free networks. The numerical analysis verifies that the biased sampling performs better than the unbiased sampling on networks in which high-degree nodes are loosely interconnected. Our work is useful for the in-depth understanding of the biased and unbiased samplings.

A novel multi-criteria optimization framework for matching of partially visible shapes in multiple images using joint geometric graph embedding is proposed. The proposed framework achieves matching of partial shapes in images that exhibit extreme variations in scale, orientation, viewpoint and illumination and also instances of occlusion; conditions which render impractical the use of global contour-based descriptors or local pixel-level features for shape matching. The proposed technique is based on optimization of the embedding distances of geometric features obtained from the eigenspectrum of the joint image graph, coupled with regularization over values of the mean pixel intensity or histogram of oriented gradients. It is shown to obtain successfully the correspondences denoting partial shape similarities as well as correspondences between feature points in the images. A new benchmark dataset is proposed which contains disparate image pairs with extremely challenging variations in viewing conditions when compared to an existing dataset [18]. The proposed technique is shown to significantly outperform several state-of-the-art partial shape matching techniques on both datasets.

A notion of fc-robustness for complex networks has received much attention recently. The motivation for this notion of robustness is to measure the effectiveness of local-information-based diffusion algorithms in the presence of adversarial nodes. In this paper, we first correct the relationship between fc-robustness and fc-connectivity studied in related work. Then we derive a sharp zero-one law for fc-robustness in a random graph model called binomial random s-intersection graph, which has a wide range of applications. In such a graph, each node is equipped with a set of items following a binomial process, and any two nodes establish an undirected edge in between if and only if they have at least s common items. Our zero-one law improves relevant results in the literature.

The sensing coverage of a directional sensor network (DSN) depends on the directionality and size-specific sensing angle of the directional sensors. The conditions are dissimilar from those of omnidirectional sensor networks for researches, especially on sensing coverage. The geometric graph of Delaunay Triangulation was used in some of related researches. However, Delaunay Triangulation has not drawn the attention of researchers for directional field coverage problem in DSNs. This study proposed two distributed algorithms of sensor direction control with the characteristics of the geometric graph of Delaunay Triangulation to achieve the field coverage improvement in DSNs. The simulation results of the proposed two algorithms are provided in this paper and can give the clarity of the coverage performances.

International audience; This paper focuses on the process of generating a sequence of sector configurations composed of two airspace component types Sharable Airspace Modules (SAMs) and Sectors Building Blocks (SBBs). An algorithm has been developed that manages the main features of the dynamic sectors configuration (including sector design criteria). In order to make it run efficiently a pre-processing step will be presented to create a graph modelling of the inputs. Based on this initial graph, a mathematical model is defined which can be summarized by a multi-periods geometric graph partitioning problem. State, space, objective function and constraints will be also presented. Due to the induced complexity, a stochastic optimization algorithm based on artificial evolution is then proposed. A two layer chromosome is used for such a genetic algorithm for which recombination operators are proposed. Evaluation of the algorithm will be presented with a comparison to existing tools and operational approach.

One-dimensional geometric random graphs are constructed by distributing n nodes uniformly and independently on a unit interval and then assigning an undirected edge between any two nodes that have a distance at most rn. These graphs have received much interest and been used in various applications including wireless networks. A threshold of rn for connectivity is known as r*n = ln n/n in the literature. In this paper, we prove that a threshold of rn for the absence of isolated node is ln n/2n (i.e., a half of the threshold r*n). Our result shows there is a gap between thresholds of connectivity and the absence of isolated node in one-dimensional geometric random graphs; in particular, when rn equals c ln n/n for a constant c ∈ (1/2, 1), a one-dimensional geometric random graph has no isolated node but is not connected. This gap in one-dimensional geometric random graphs is in sharp contrast to the prevalent phenomenon in many other random graphs such as two-dimensional geometric random graphs, Erdős-Renyi graphs, and random intersection graphs, all of which in the asymptotic sense become connected as soon as there is no isolated node.

The Internet of Things will comprise billions of randomly placed devices, forming a dense and unstructured network environment with overlapping wireless topologies. In such demanding environment, the grouping of IoT devices into clusters is a promising approach for the management and the control of network resources in the context of an autonomous system. This paper proposes the SYSTAS algorithm for the distributed discovery and formation of clusters in random geometric graphs of fixed wireless nodes by exploiting local topology knowledge and without having any information about the expected number of clusters. The density of the network graph, discovered by interacting with neighboring nodes and the topological features, as well as the model of preferential attachment are used by the proposed scheme. The effectiveness of SYSTAS is evaluated in various topologies. Experimental evaluation demonstrates that SYSTAS outperforms other clustering schemes; in some occasions these solutions have comparable results with SYSTAS but they require global network view, which leads to higher signaling cost.

With the help of location-aware mobile device user can issue a query and obtain information on nearest point of interest as it moves within a spatial network. This evolving computing paradigm offers great level of convenience to information access and usage. Nevertheless, the convenience comes with a price in the form of exposing user private information to potential abuse and misuse. This paper proposes a novel idea to protect user private information in a location-based services continuous nearest neighbor query with a focus on moving query and static object. Most proposed solutions for privacy use third party anonymizer, or offer protection only for snapshot query, however most queries are continuous. In this proposal we combine Voronoi tessellation and Hilbert curve order with R-tree index of geometric data storage to provide transition points that indicate where nearest neighbor changes. With a database arranged as a square matrix of size n bits, we execute double private information retrieval protocol in the server to return exact nearest neighbor point of interest throughout the query segment with minimal cost, and without revealing any user private information. Our experimental evaluation of the transmission cost using ns-3 simulator and the complexity analysis show a system capable of being scaled to different population size with minimal performance impact and with improvement on the complexity over related technique.

Ad-hoc network is an important applied branch of scale-free networks, which has been widely studied. In this paper, insertions and failures of nodes in ad-hoc networks are modeled in spatial growth models. The preferential attachment probability is based on the topological degree and modulated by a Euclidean distance dependent power-law function. Node failures are represented by random node deletions in the model. Degree distributions of the proposed spatial growth models for ad-hoc networks are evaluated. The results show that both the Euclidean distance dependent preferential attachment and the random node deletion can change the degree distribution. When the distance exponent is smaller than-1 or the deletion ratio is larger than 0.5, the network is not scale-free any more, and the degree distribution follows the exponential decay law. The varying of the average degree of the node with time is also evaluated. The results show that, irrelevant to the distance exponent, the average degree can achieve a convergent value for each value of the deletion ratio and simulation results match calculated values completely.