Search

Wireless sensor network (WSNs) technology and Internet technology penetrate and extend each other. It is a good way for physical changes of objects, state recognition and data collection, and becomes an important source of network data in big data. Compared with traditional wireless networks, WSNs have the characteristics of integrating sensing, processing, and transmission, limited hardware resources, limited power supply capacity, no center, self-organization, multi-hop routing, dynamic topology, large number of nodes, and dense distribution. In order to improve the energy utilization rate of a single node to a greater extent, reduce the energy consumption of the entire WSNs, and extend the life cycle of WSNs, high-efficiency networking is essential in the application of WSNs. Networking is one of the foundations to the large-scale WSNs. The network model and node location deployment are important technologies for WSNs networking. Based on the network characteristics of large-scale WSNs and the transmission capacity of big data, a new type of network model suitable is presented which combined the advantages of Star model and Mesh model. More importantly, the deployment environment of sensor nodes is a spatial network. The data collected and transmitted by large-scale WSNs is very large. The deployment of sensor nodes in space can ensure that the big data collected and transmitted are true and effective. This research proposes the space density first (SDF) algorithm, which improves the neighbor density first algorithm with the space node deployment and the density-optimized SDF algorithm. The SDF algorithm saves network energy and extends the life of the network. Experimental results show that large-scale WSNs built with a new networking model and SDF algorithm can collect and transmit big data stably and reliably, which saves network energy and improves the accuracy of big data.

We introduce the concept of local spanners for planar point sets with respect to a family of regions, and prove the existence of local spanners of small size for some families. For a geometric graph G on a point set $$P$$ and a region R belonging to a family $${\mathcal {R}}$$ , we define $$G \cap R$$ to be the part of the graph G that is inside R (or is induced by R). A local t-spanner w.r.t $${\mathcal {R}}$$ is a geometric graph G on $$P$$ such that for any region $$R \in {\mathcal {R}}$$ , the graph $$G\cap R$$ is a t-spanner for $$K(P) \cap R$$ , where $$K(P)$$ is the complete geometric graph on P. For any set $$P$$ of n points and any constant $$\varepsilon > 0$$ , we prove that $$P$$ admits local $$(1 + \varepsilon )$$ -spanners of sizes $$O(n \log ^{6} n)$$ and $$O(n \log n)$$ w.r.t axis-parallel squares and vertical slabs, respectively. If adding Steiner points is allowed, then local $$(1 + \varepsilon )$$ -spanners with O(n) edges and $$O(n \log ^2 n)$$ edges can be obtained for axis-parallel squares and disks using O(n) Steiner points, respectively.

The interaction of regional ecological efficiency is important for promoting ecological efficiency. Using a gravity model and social network analysis, this study investigated the spatial network characteristics of the sustainable total-factor ecology efficiency (STFEcE) in 30 provinces of China from 2005 to 2016 for the first time. The quadratic assignment procedure (QAP) was also used to analyze the factors affecting the network. The results are as follows. (1) The STFEcE between regions exhibited a spatial network relationship. (2) Jiangsu, Guangdong, Shandong, Ningxia, and other provinces were in the center of the network, whereas Guangxi, Anhui, and other provinces were on the edge. (3) The 30 provinces were divided into four plates, and the connections in the network were primarily based on the relationship between plates. (4) The difference between urban population, energy structure, and technical advancement negatively impacted the network relationship. The provinces should fully understand the value of the STFEcE network and implement appropriate measures to achieve collaborative improvement of regional ecological efficiency according to their roles in the network.

In the study of human action recognition, two-stream networks have made excellent progress recently. However, there remain challenges in distinguishing similar human actions in videos. This paper proposes a novel local-aware spatio-temporal attention network with multi-stage feature fusion based on compact bilinear pooling for human action recognition. To elaborate, taking two-stream networks as our essential backbones, the spatial network first employs multiple spatial transformer networks in a parallel manner to locate the discriminative regions related to human actions. Then, we perform feature fusion between the local and global features to enhance the human action representation. Furthermore, the output of the spatial network and the temporal information are fused at a particular layer to learn the pixel-wise correspondences. After that, we bring together three outputs to generate the global descriptors of human actions. To verify the efficacy of the proposed approach, comparison experiments are conducted with the traditional hand-engineered IDT algorithms, the classical machine learning methods (i.e., SVM) and the state-of-the-art deep learning methods (i.e., spatio-temporal multiplier networks). According to the results, our approach is reported to obtain the best performance among existing works, with the accuracy of 95.3% and 72.9% on UCF101 and HMDB51, respectively. The experimental results thus demonstrate the superiority and significance of the proposed architecture in solving the task of human action recognition.

Parochialism occurs when an individual mentally codes the population into in-group and out-group members and cooperates only with in-group members. Conditional cooperation of this kind is distinct from strategies such as tit-for-tat where the decision to cooperate is conditioned on others’ previous actions. Parochialists practice in-group favoritism by cooperating with others, conditional on their spatial proximity or cultural similarity. We consider an evolutionary model of local interaction with three types of strategies: altruists “always cooperate”; egoists “always defect”; and parochialists cooperate only with neighbors within a certain radius on a spatial network. In the model, we provide a new explanation for why parochialism is durable and can stably remain prevalent in human populations. The main driving force is the homophily effect. Interestingly, the homophily effect leads to the prevalence of parochialists but not altruists who benefit more from homophilic association, because altruists are invaded by parochialists. The two groups can coexist only if egoists buffer their direct interaction. Accordingly, the proportion of egoists can be greater than that of altruists in our model, contrary to the result of Eshel et al. (1998). Simulations show, for most parameter values, that the socially optimal cooperation radius (achieving the greatest mean fitness across the entire population) is two and that narrow in-group parochialism is prevalent regardless of frequency of interaction within a society.

We propose a novel phase based analysis with the purpose of quantifying the periodic bursts of activity observed in various neuronal systems. The way bursts are intiated and propagate in a spatial network is still insufficiently characterized. In particular, we investigate here how these spatiotemporal dynamics depend on the mean connection length. We use a simplified description of a neuron’s state as a time varying phase between firings. This leads to a definition of network bursts, that does not depend on the practitioner’s individual judgment as the usage of subjective thresholds and time scales. This allows both an easy and objective characterization of the bursting dynamics, only depending on system’s proper scales. Our approach thus ensures more reliable and reproducible measurements. We here use it to describe the spatiotemporal processes in networks of intrinsically oscillating neurons. The analysis rigorously reveals the role of the mean connectivity length in spatially embedded networks in determining the existence of “leader” neurons during burst initiation, a feature incompletely understood observed in several neuronal cultures experiments. The precise definition of a burst with our method allowed us to rigorously characterize the initiation dynamics of bursts and show how it depends on the mean connectivity length. Although presented with simulations, the methodology can be applied to other forms of neuronal spatiotemporal data. As shown in a preliminary study with MEA recordings, it is not limited to in silico modeling.

Geometric graph model is suggested for the dynamical Casimir effect. The wave equation is considered at the graph edges and the Kirchhoff condition at the internal vertex. It is assumed that the edge lengths depend on time. Photon generation is considered in the framework of the Dodonov–Klimov model.

Ultra-dense network (UDN) is a promising solution to meet the huge data requirements of future 5G wireless communication systems. With many irregularly deployed small cell base stations (SBSs), it is very difficult to accurately measure network energy efficiency (EE) in UDN. Considering the necessity of saving energy in modern-day networks, in this paper, I present the EE evaluation of UDN based on the random spatial network model. In this considered system, the SBSs and the macro cell users (MUEs) are modeled as a homogeneous Poisson point process (PPP). Unlike the existing literature, I derive the simple closed-form expressions for the successful transmission probabilities of MUEs and small cells by Laplace transformation. Then, based on the obtained successful transmission probabilities, I derive the closed form expression for EE of the small cells in both uplink and downlink under some practical constraints. Further, to obtain the optimal SBS density in UDN, I propose a joint uplink and downlink power allocation (JUDPA) algorithm. The JUDPA algorithm obtains the maximum EE in small cells by iteratively optimizing the uplink and downlink powers. Our theoretical analysis and simulated results demonstrate the accuracy of the proposed model with better power allocation and less complexity than conventional solutions.

The complete twisted graph of order n, denoted by $$T_n$$ , is a complete simple topological graph with vertices $$u_1, u_2, \ldots , u_n$$ such that two edges $$u_iu_j$$ and $$u_{i'}u_{j'}$$ cross if and only if $$ i

We propose a general framework of opening and closing shops in group competitive environment, i.e., shops in the same group work cooperatively and those in different groups competitively, based on stochastic utility which is given by a function of shop distance and attractiveness with an explicit traveling time-bound imposed. The framework allows to derive a specific prediction model by choosing a specific function form of utility, including the one we propose, its variants and the conventional state-of-the-art gravity model which we chose as a reference. We compute a marginal gain of the market share which is derived from the utility function and the consumers buying power as a measure to rank the candidate location. Using the real dataset of three convenience store groups in four cities in Japan, we analyzed how the derived models behave with respect to the time-bound and the other parameters and how each model compare with others. We confirm that, despite the simplification we made in the model, inferred rankings of the shops newly opened in the real data are shown to be high implying that our prediction model and other variants are reasonable. We show that our model gives much more realistic results than the gravity model, which indicates that our group competitive mechanism with the time-bounded stochastic utility is vital and promising. Inclusion of the time-bound constraint is crucially important. Analyses of the dynamics of opening and closing shops indicate that competition indeed affects the market share of each group over time, and the total share eventually increases although small, and the difference of the share within each group gradually becomes smaller, revealing that the spatial distribution of the shops in each group becomes more uniform.

Purpose of Review We synthesize recent methodological and conceptual advances in the field of riverscape ecology, emphasizing areas of synergy with current research in landscape ecology. Recent Findings Recent advances in riverscape ecology highlight the need for spatially explicit examinations of how network structure influences ecological pattern and process, instead of the simple linear (upstream-downstream) view. Developments in GIS, remote sensing, and computer technologies already offer powerful tools for the application of patch- and gradient-based models for characterizing abiotic and biotic heterogeneity across a range of spatial and temporal scales. Along with graph-based analyses and spatial statistical stream network models (i.e., geostatistical modelling), these approaches offer improved capabilities for quantifying spatial and temporal heterogeneity and connectivity relationships, thereby allowing for rigorous and high-resolution analyses of pattern, process, and scale relationships. Summary Spatially explicit network approaches are able to quantify and predict biogeochemical, hydromorphological, and ecological patterns and processes more precisely than models based on longitudinal or lateral riverine gradients alone. Currently, local habitat characteristics appear to be more important than spatial effects in determining population and community dynamics, but this conclusion may change with direct quantification of the movement of materials, energy, and organisms along channels and across ecosystem boundaries—a key to improving riverscape ecology. Coupling spatially explicit riverscape models with optimization approaches will improve land protection and water management efforts, and help to resolve the land sharing vs. land sparing debate.

A key technical issue for human intention prediction from observed human actions is how to discover and utilize the spatio-temporal patterns behind those actions. Inspired by the well-known two-stream architecture for action recognition, this paper proposes an approach for human intention prediction based on a two-stream architecture using RGB images and optical flow. Firstly, the action-start frame of each trial of a human action is determined by calculating the L2 distance of the positions of the human joints between frames of the skeleton data. Secondly, a spatial network and a temporal network are trained separately to predict human intentions using RGB images and optical flow, respectively. Both early concatenation fusion methods in the spatial network and sampling methods in the temporal network are optimized based on experiments. Finally, average fusion is used to fuse the prediction results from the spatial network and the temporal network. To verify the effectiveness of the proposed approach, a new dataset of human intentions behind human actions is introduced. This dataset contains RGB images, RGB-D images, and skeleton data of human actions of pitching a ball. Experiments show that the proposed approach can predict human intentions behind human actions with a prediction accuracy of 74% on the proposed dataset. The proposed approach is further evaluated on the Intention from Motion (IfM) dataset, a dataset of human intentions behind human actions of grasping a bottle. The proposed approach achieves a prediction accuracy of 77% on the IfM dataset. The proposed approach is effective in predicting human intentions behind human actions in different applications.

Complex network theory is a multidisciplinary research direction of complexity science which has experienced a rapid surge of interest over the last two decades. Its applications in land-based urban traffic network studies have been fruitful, but have suffered from the lack of a systematic cognitive and integration framework. This paper reviews complex network theory related knowledge and discusses its applications in urban traffic network studies in several directions. This includes network representation methods, topological and geographical related studies, network communities mining, network robustness and vulnerability, big-data-based research, network optimization, co-evolution research and multilayer network theory related studies. Finally, new research directions are pointed out. With these efforts, this physics-based concept will be more easily and widely accepted by urban traffic network planners, designers, and other related scholars.

The spatial distribution of population affects disease transmission, especially when shelter in place orders restrict mobility for a large fraction of the population. The spatial network structure of settlements therefore imposes a fundamental constraint on the spatial distribution of the population through which a communicable disease can spread. In this analysis we use the spatial network structure of lighted development as a proxy for the distribution of ambient population to compare the spatiotemporal evolution of COVID-19 confirmed cases in the USA and China. The Visible Infrared Imaging Radiometer Suite (VIIRS) Day/Night Band sensor on the NASA/NOAA Suomi satellite has been imaging night light at ~ 700 m resolution globally since 2012. Comparisons with sub-kilometer resolution census observations in different countries across different levels of development indicate that night light luminance scales with population density over ~ 3 orders of magnitude. However, VIIRS’ constant ~ 700 m resolution can provide a more detailed representation of population distribution in peri-urban and rural areas where aggregated census blocks lack comparable spatial detail. By varying the low luminance threshold of VIIRS-derived night light, we depict spatial networks of lighted development of varying degrees of connectivity within which populations are distributed. The resulting size distributions of spatial network components (connected clusters of nodes) vary with degree of connectivity, but maintain consistent scaling over a wide range (5 × to 10 × in area & number) of network sizes. At continental scales, spatial network rank-size distributions obtained from VIIRS night light brightness are well-described by power laws with exponents near −2 (slopes near −1) for a wide range of low luminance thresholds. The largest components (104to 105km2) represent spatially contiguous agglomerations of urban, suburban and periurban development, while the smallest components represent isolated rural settlements. Projecting county and city-level numbers of confirmed cases of COVID-19 for the USA and China (respectively) onto the corresponding spatial networks of lighted development allows the spatiotemporal evolution of the epidemic (infection and detection) to be quantified as propagation within networks of varying connectivity. Results for China show rapid nucleation and diffusion in January 2020 followed by rapid decreases in new cases in February. While most of the largest cities in China showed new confirmed cases approaching zero before the end of February, most of these cities also showed distinct second waves of cases in March or April. Whereas new cases in Wuhan did not approach zero until mid-March, as of December 2020 it has not yet experienced a second wave of cases. In contrast, the results for the USA show a wide range of trajectories, with an abrupt transition from slow increases in confirmed cases in a small number of network components in January and February, to rapid geographic dispersion to a larger number of components shortly before mobility reductions occurred in March. Results indicate that while most of the upper tail of the network had been exposed by the end of March, the lower tail of the component size distribution has only shown steep increases since mid-June.

Space Syntax and the theory of natural movement demonstrated that spatial morphology is a primary factor influencing movement. This paper investigates to what extent spatial morphology at different scales (node, community and global network) influences the use of public space by micromobility. An axial map and corresponding network for Lisbon’s walkable and open public space, and data from e-scooters parking locations, is used as case study. Relevant metrics and their correlations (intelligibility, accessibility, permeability and local dimension) for the quantitative characterization of spatial morphology properties are described and computed for Lisbon’s axial map. Communities are identified based on the network topological structure in order to investigate how these properties are affected at different scales in the case study. The resulting axial line clustering is compared via the variation of information metric with the clustering obtained from e-scooters’ proximity. The results obtained enable to conclude that the space syntax properties are scale dependent in Lisbon’s pedestrian network. On the other hand both the correlation between these properties, the number of scooters and the variation of information between clusters indicate that the spatial morphology is not the only factor influencing micromobility. Through the comparative analysis between the main properties of the public space network of Lisbon and data collected from e-scooters locations in a timeframe, centrality becomes a dynamic concept, relying not only on the static topological properties of the urban network, but also on other quantitative and qualitative factors, since the flows’ operating on the network will operate several transformations on the spatial network properties through time, uncovering spatiotemporal dynamics.

In this study, we propose novel centrality measures considering multiple perspectives of nodes or node groups based on the facility location problem on a spatial network. The conventional centrality exclusively quantifies the global properties of each node in a network such as closeness and betweenness, and extracts nodes with high scores as important nodes. In the context of facility placement on a network, it is desirable to place facilities at nodes with high accessibility from residents, that is, nodes with a high score in closeness centrality. It is natural to think that such a property of a node changes when the situation changes. For example, in a situation where there are no existing facilities, it is expected that the demand of residents will be satisfied by opening a new facility at the node with the highest accessibility, however, in a situation where there exist some facilities, it is necessary to open a new facility some distance from the existing facilities. Furthermore, it is natural to consider that the concept of closeness differs depending on the relationship with existing facilities, cooperative relationships and competitive relationships. Therefore, we extend a concept of centrality so as to considers the situation where one or more nodes have already been selected belonging to one of some groups. In this study, we propose two measures based on closeness centrality and betweenness centrality as behavior models of people on a spatial network. From our experimental evaluations using actual urban street network data, we confirm that the proposed method, which introduces the viewpoints of each group, shows that there is a difference in the important nodes of each group viewpoint, and that the new store location can be predicted more accurately.

In order to effectively evaluate personnel performance, a distributed data mining algorithm for spatial networks based on BP neural wireless network is proposed. In the cloud computing environment, an excavator is used to construct multiple input multiple output spatial network data, analyze the data structure, and perform redundant data compression of massive data through time-frequency feature extraction. Combined with adaptive matching filtering method, the characteristics of the data are matched. The spatial frequency feature extraction method is used to locate the features of the multiple-input multiple-output spatial network data. In order to improve the accuracy of data mining, the BP neural network is used to classify and identify the extracted data features to achieve the optimization of data mining. A wireless sensor network is a wireless network composed of a large number of stationary or moving sensors in a self-organizing and multi-hop manner. It cooperatively senses, collects, processes, and transmits the information of the perceived objects in the geographical area covered by the network, and finally puts these The information is sent to the owner of the network. This algorithm improves the accuracy of personnel performance evaluation, and simultaneously establishes a hierarchical analysis and quantitative evaluation model for the performance of government managers, and adjusts the results of hierarchical statistical analysis on government administrators as needed. The performance evaluation and optimization of government administrators were introduced. The empirical analysis results show that the method has higher accuracy for government managers' performance evaluation, higher efficiency of big data processing and better integration.

We investigate diffusive search on planar networks, motivated by tubular organelle networks in cell biology that contain molecules searching for reaction partners and binding sites. Exact calculation of the diffusive mean first-passage time on a spatial network is used to characterize the typical search time as a function of network connectivity. We find that global structural properties --- the total edge length and number of loops --- are sufficient to largely determine network exploration times for a variety of both synthetic planar networks and organelle morphologies extracted from living cells. For synthetic networks on a lattice, we predict the search time dependence on these global structural parameters by connecting with percolation theory, providing a bridge from irregular real-world networks to a simpler physical model. The dependence of search time on global network structural properties suggests that network architecture can be designed for efficient search without controlling the precise arrangement of connections. Specifically, increasing the number of loops substantially decreases search times, pointing to a potential physical mechanism for regulating reaction rates within organelle network structures., 13 pages, 4 figures. Accepted for publication in Scientific Reports

We consider a point cloud $$X_n := \{ {\mathbf {x}}_1, \ldots , {\mathbf {x}}_n \}$$ uniformly distributed on the flat torus $${\mathbb {T}}^d : = \mathbb {R}^d / \mathbb {Z}^d $$, and construct a geometric graph on the cloud by connecting points that are within distance $$\varepsilon $$ of each other. We let $${\mathcal {P}}(X_n)$$ be the space of probability measures on $$X_n$$ and endow it with a discrete Wasserstein distance $$W_n$$ as introduced independently in Chow et al. (Arch Ration Mech Anal 203:969–1008, 2012), Maas (J Funct Anal 261:2250–2292, 2011) and Mielke (Nonlinearity 24:1329–1346, 2011) for general finite Markov chains. We show that as long as $$\varepsilon = \varepsilon _n$$ decays towards zero slower than an explicit rate depending on the level of uniformity of $$X_n$$, then the space $$({\mathcal {P}}(X_n), W_n)$$ converges in the Gromov–Hausdorff sense towards the space of probability measures on $${\mathbb {T}}^d$$ endowed with the Wasserstein distance. The analysis presented in this paper is a first step in the study of stability of evolution equations defined over random point clouds as the number of points grows to infinity.

We study the problem of computing Euclidean minimum weight matching which investigates the minimum weight perfect matching in a complete geometric graph on a set of 2n points in the plane. We propose a simple randomized approximation algorithm based on the geometrical aspect of the problem with O(n) expected time. The proposed algorithm computes a matching within at most 3 factors of the optimal solution. We also do some experimental tests to evaluate the performance of the proposed algorithm which indicate the efficiency of the proposed algorithm in finding the approximate matching in the practice.

The relationship between cross-regional cultural landscapes does not currently receive enough attention in cultural landscape conservation. Cultural landscapes in China are faced with the crisis of fragmentation and islanding, which makes it necessary to strengthen the idea of integrated conservation. The Great Wall cultural belt in Beijing is a cross-regional linear cultural landscape in the northwest mountainous area of Beijing. With the Great Wall as a link connecting the surrounding natural, social, and cultural resources to form a banded structure, it has the typical and practical significance of integrated conservation. Based on the theory of the cultural landscape security pattern and its ‘node – setting – connection’ model, this research studies the spatial structure and shaping mechanism of the Great Wall cultural belt in Beijing from the perspective of tourist flow, using Flickr geo-tagged photos and Wikiloc tracks. The results identify the core nodes and intermediate nodes of the Great Wall cultural belt in Beijing and show that it has a multi-core, multi-group hierarchical nesting structure differing from the geographic space, which has groups following the evolution orbit of ‘linear string – circumnuclear star – complete network.’ To explain the differences between the cultural association network (CAN) and the geospatial network (GSN), we find that the cultural associations between nodes rely on geophysical channels, including heritage corridors and traffic passages, as physical carriers, but the nodes’ attraction and their setting elements, containing natural geography environments, settlements, administrative divisions, etc., change the channel resistance, so CAN and GSN present different characteristics. From the perspective of systematic and spatial network thoughts, this study has made an attempt to adopt new analysis and research methods to achieve the integrated conservation and inheritance of linear cultural landscapes in mountainous areas.

Focusing on the peculiarities of urban construction resulting from specific mountain terrains, the purpose of this study is to find out a suitable method based on a Spatial Network Comprehensive Model (SNCM) to reasonably plan and distribute primary schools in low-income mountain cities. The construction principles and advantages of the SNCM method are proposed and the method tested in Wanyuan city of Qinba Mountain area (Southwest China) to verify its feasibility and optimization. Taking account of the mountain terrain and its influence on user behavior, we used the SNCM method to build a comprehensive model which integrates the road slope and the walking speed of pupils into the basic spatial model. The model is used to calculate a reasonable layout of the primary schools and to validate the rationale. The results show that the SNCM method can be effectively applied in low-income mountainous cities. It can not only improve the accessibility and service efficiency of primary schools using as little capital-investment as possible, but also help the city grow in an intensive and efficient way.

Let G be a complete convex geometric graph on 2m vertices, and let F be a family of subgraphs of G. A blocker for F is a set of edges, of smallest possible size, that meets every element of F. In [C. Keller and M. A. Perles, On the smallest sets blocking simple perfect matchings in a convex geometric graph, Israel J. Math. 187 (2012), pp. 465-484], we gave an explicit description of all blockers for the family of simple perfect matchings (SPMs) of G. In this paper we show that the family of simple Hamiltonian paths (SHPs) in G has exactly the same blockers as the family of SPMs. Our argument is rather short, and provides a much simpler proof of the result of [KP12]., Comment: 7 pages, 4 figures

We define and study Euclidean and spatial network variants of a new path finding problem: given a set of safe or preferred zones with zero or low cost, find paths that minimize the cost of travel from an origin to a destination. In this problem, the entire space is passable, with preference given to safe or preferred zones. Existing algorithms for problems that involve unsafe regions to be avoided strictly are not effective for this new problem. To solve the Euclidean variant, we devise a transformation of the continuous data space with safe zones into a discrete graph upon which shortest path algorithms apply. A naive transformation yields a large graph that is expensive to search. In contrast, our transformation exploits properties of hyperbolas in Euclidean space to safely eliminate graph edges, thus improving performance without affecting correctness. To solve the spatial network variant, we propose a different graph-to-graph transformation that identifies critical points that serve the same purpose as do the hyperbolas, thus also avoiding the extraneous edges. Having solved the problem for safe zones with zero costs, we extend the transformations to the weighted version of the problem, where travel in preferred zones has nonzero costs. Experiments on both real and synthetic data show that our approaches outperform baseline approaches by more than an order of magnitude in graph construction time, storage space, and query response time.

The efficient visualization of dynamic network structures has become a dominant problem in many big data applications, such as large network analytics, traffic management, resource allocation graphs, logistics, social networks, and large document repositories. In this paper, we present a large-graph visualization system called ModuleGraph. ModuleGraph is a scalable representation of graph structures by treating a graph as a set of modules. The main objectives are: (1) to detect graph patterns in the visualization of large-graph data, and (2) to emphasize the interconnecting structures to detect potential interactions between local modules. Our first contribution is a hybrid modularity measure. This measure partitions the cohesion of the graph at various levels of details. We aggregate clusters of nodes and edges into several modules to reduce the overlap between graph components on a 2D display. Our second contribution is a k-clustering method that can flexibly detect the local patterns or substructures in modules. Patterns of modules are preserved by the ModuleGraph system to avoid information loss, while sub-graphs are clustered as a single node. Our experiments show that this method can efficiently support large-scale social and spatial network visualization. Graphical Abstract text

An efficient and service-oriented transportation network is a necessary resource for successful less-than-truckload operations. The design and evaluation of transportation networks are mainly driven by quantitative particularly cost-oriented measures, such as transport and transshipment costs. This type of measurement, however, simply cannot represent the manifold performance of a transportation network. In particular, incorporating network concentration into network design decisions overcomes the shortcomings of purely cost-oriented decisions because spatial network concentration is at the root of many aspects of network performance (e.g., congestion and network vulnerability). This paper suggests modifications to the network concentration index and the hubbing concentration index from the passenger airline context for less-than-truckload road transportation. The modified indices enable information to be conveyed by network concentration into less-than-truckload network design decisions and provide a suitable perspective to include service-oriented aspects into network design.

A well-known result of Kupitz from 1982 asserts that the maximal number of edges in a convex geometric graph (CGG) on n vertices that does not contain $$k+1$$k+1 pairwise disjoint edges is kn (provided $$n>2k$$n>2k). For $$k=1$$k=1 and $$k=n/2-1$$k=n/2-1, the extremal examples are completely characterized. For all other values of k, the structure of the extremal examples is far from known: their total number is unknown, and only a few classes of examples were presented, that are almost symmetric, consisting roughly of the kn "longest possible" edges of CK(n), the complete CGG of order n. In order to understand further the structure of the extremal examples, we present a class of extremal examples that lie at the other end of the spectrum. Namely, we break the symmetry by requiring that, in addition, the graph admit an independent set that consists of q consecutive vertices on the boundary of the convex hull. We show that such graphs exist as long as $$q \le n-2k$$q≤n-2k and that this value of q is optimal. We generalize our discussion to the following question: what is the maximal possible number f(n, k, q) of edges in a CGG on n vertices that does not contain $$k+1$$k+1 pairwise disjoint edges, and, in addition, admits an independent set that consists of q consecutive vertices on the boundary of the convex hull? We provide a complete answer to this question, determining f(n, k, q) for all relevant values of n, k and q.

Dividing a geographical region into some subregions with common characteristics is an important research topic, and has been studied in many research fields such as urban planning and transportation planning. In this paper, by network analysis approach, we attempt to extract functionally similar regions, each of which consists of functionally similar nodes of a road network. For this purpose, we previously proposed the Functional Cluster Extraction method, which takes a large amount of computation time to output clustering results because it treats too many high-dimensional vectors. To overcome this difficulty, we also previously proposed a transfer learning-based clustering method that selects approximate medoids from the target network using the K medoids of a previously clustered network and divides all the nodes into K clusters. If we select an appropriate network with similar structural characteristics, this method produces highly accurate clustering results. However it is difficult to preliminarily know which network is appropriate. In this paper, we extend this method to ensure accuracy using the K medoids of multiple networks rather than a specific network. Using actual urban streets, we evaluate our proposed method from the viewpoint of the improvement degree of clustering accuracy and computation time.

The use of outsourcing/privatization in the public sector has been steadily increasing for the past several decades. The trend is evident in all levels of governments around the world, and the U.S. is no exception. Although scholars from numerous disciplines have searched for causes of this trend, no consensus has been reached in the literature. This paper advances these efforts by identifying determinants of outsourcing in U.S. municipalities using spatial network analysis. We incorporate a spatial aspect to explore outsourcing decisions, which is a different approach from much of the literature. Empirical results indicate that a local government’s outsourcing decision is affected by nearby local jurisdictions. Additional findings indicate that external stakeholders’ involvement contributes to the use of outsourcing, whereas having a limited supply of service providers impedes it.

This paper presents a novel algorithm for joint routing and scheduling in TDM wireless mesh networks. We introduce a new construct, called a "space---time graph," which incorporates the spatial and temporal aspects of routing in one structure by replicating a spatial network connectivity graph in layers along the time dimension. The power of the space---time graph lies in the fact that a path from one node to another in it specifies both a physical route in space as well as a schedule in time for a message. Hence the complicated and intractable problem of routing and scheduling reduces to the relatively simpler problem of determining shortest paths in a graph. Through simulations we show that a simply greedy algorithm on the space---time graph outperforms two state-of-the-art methods in terms of time taken to successfully transmit a set of messages from their sources to their destinations.

We study the parameterized complexity of Geometric Graph Isomorphism (Known as the Point Set Congruence problem in computational geometry): given two sets of n points A and B with rational coordinates in k-dimensional euclidean space, with k as the fixed parameter, the problem is to decide if there is a bijection $$\pi :A \rightarrow B$$ź:AźB such that for all $$x,y \in A$$x,yźA, $$\Vert x-y\Vert = \Vert \pi (x)-\pi (y)\Vert $$źx-yź=źź(x)-ź(y)ź, where $$\Vert \cdot \Vert $$ź·ź is the euclidean norm. Our main result is the following: We give a $$O^*(k^{O(k)})$$Oź(kO(k)) time (The $$O^*(\cdot )$$Oź(·) notation here, as usual, suppresses polynomial factors) FPT algorithm for Geometric Isomorphism. This is substantially faster than the previous best time bound of $$O^*(2^{O(k^4)})$$Oź(2O(k4)) for the problem (Evdokimov and Ponomarenko in Pure Appl Algebra 117---118:253---276, 1997). In fact, we show the stronger result that even canonical forms for finite point sets with rational coordinates can also be computed in $$O^*(k^{O(k)})$$Oź(kO(k)) time. We also briefly discuss the isomorphism problem for other $$l_p$$lp metrics. Specifically, we describe a deterministic polynomial-time algorithm for finite point sets in $$\mathbb {Q}^2$$Q2.

We study the impact of metric constraints on the realizability of planar graphs. Let G be a subgraph of a planar graph H (where H is the "host" of G). The graph G is free in H if for every choice of positive lengths for the edges of G, the host H has a planar straight-line embedding that realizes these lengths; and G is extrinsically free in H if all constraints on the edge lengths of G depend on G only, irrespective of additional edges of the host H. We characterize the planar graphs G that are free in every host H, $$G\subseteq H$$G⊆H, and all the planar graphs G that are extrinsically free in every host H, $$G\subseteq H$$G⊆H. The case of cycles $$G=C_k$$G=Ck provides a new version of the celebrated carpenter's rule problem. Even though cycles $$C_k$$Ck, $$k\ge 4$$k?4, are not extrinsically free in all triangulations, it turns out that "nondegenerate" edge lengths are always realizable, where the edge lengths are considered degenerate if the cycle can be flattened (into a line) in two different ways. Separating triangles, and separating cycles in general, play an important role in our arguments. We show that every star is free in a 4-connected triangulation (which has no separating triangle).

Eco-routing is a simple yet effective approach to substantially reducing the environmental impact, e.g., fuel consumption and greenhouse gas (GHG) emissions, of vehicular transportation. Eco-routing relies on the ability to reliably quantify the environmental impact of vehicles as they travel in a spatial network. The procedure of quantifying such vehicular impact for road segments of a spatial network is called eco-weight assignment. EcoMark 2.0 proposes a general framework for eco-weight assignment to enable eco-routing. It studies the abilities of six instantaneous and five aggregated models to estimating vehicular environmental impact. In doing so, it utilizes travel information derived from GPS trajectories (i.e., velocities and accelerations) and actual fuel consumption data obtained from vehicles. The framework covers analyses of actual fuel consumption, impact model calibration, and experiments for assessing the utility of the impact models in assigning eco-weights. The application of EcoMark 2.0 indicates that the instantaneous model EMIT and the aggregated model SIDRA-Running are suitable for assigning eco-weights under varying circumstances. In contrast, other instantaneous models should not be used for assigning eco-weights, and other aggregated models can be used for assigning eco-weights under certain circumstances.

Many applications require understanding how event occurrences at one geographical region affect or influence event occurrences at another region, e.g. spread of disease and forest fires. Existing works typically impose a grid to partition the spatial space and utilize spatial autocorrelation property to model the spatial dependency among the grid cells. However, they are often highly sensitive to the granularity of the grid size and they do not incorporate the temporal dynamics of the event occurrences among regions. This paper utilizes the notion of a spatial network with temporal dependency to capture the dynamics of event occurrences among regions. This network is modeled as a directed graph where each node is a group of spatially nearby events and each directed edge represents the influence of events from a source node to a destination node. We design an algorithm called LinkNet to generate this network from spatio-temporal event databases. LinkNet utilizes minimum description length based information---theoretic approach to automatically adjust the number of regions and the temporal relationships among regions. Two optimizations are devised to reduce the computational complexity of LinkNet. We also demonstrate how the proposed network can be used for hotspot prediction. Experiment results on both synthetic and real world datasets demonstrate the efficiency of LinkNet and the effectiveness of the network in predicting the next hotspots.

Given a set S of sites and a set O of weighted objects, an optimal location query finds the location(s) where introducing a new site maximizes the total weight of the objects that are closer to the new site than to any other site. With such a query, for instance, a franchise corporation (e.g., McDonald's) can find a location to open a new store such that the number of potential store customers (i.e., people living close to the store) is maximized. Optimal location queries are computationally complex to compute and require efficient solutions that scale with large datasets. Previously, two specific approaches have been proposed for efficient computation of optimal location queries. However, they both assume p-norm distance (namely, L1 and L2/Euclidean); hence, they are not applicable where sites and objects are located on spatial networks. In this article, we focus on optimal network location (ONL) queries, i.e., optimal location queries in which objects and sites reside on a spatial network. We introduce two complementary approaches, namely EONL (short for Expansion-based ONL) and BONL (short for Bound-based ONL), which enable efficient computation of ONL queries with datasets of uniform and skewed distributions, respectively. Moreover, with an extensive experimental study we verify and compare the efficiency of our proposed approaches with real world datasets, and we demonstrate the importance of considering network distance (rather than p-norm distance) with ONL queries.

Suppose you have the possibility to choose to adopt one of a number of different behaviors or to choose to buy one of a number of different products, and suppose your choice is influenced by your individual perception of the average choices made by others. Economists Brock and Durlauf (in Am. Econ. Rev. 92(2):298, 2002; The Economy as an Evolving Complex System III. Oxford University Press, New York, 2006) have derived seminal theoretical results for the equilibrium behavior of the multinomial discrete choice model with social interactions, assuming homogeneous decision-makers, global interactions and laws of large of numbers. The research presented in this paper extends Brock and Durlauf's model to allow for unobserved preference heterogeneity between choice alternatives by studying the nested logit model. Next, by drawing on the computational possibilities permitted through social simulation of multi-agent systems (MAS), this paper relaxes the assumption of global interactions and considers instead local interactions within several hypothesized social and spatial network structures. Additional heterogeneity is thus hereby induced by the influence on a given decision-maker's choice by the particular network connections he or she has and the particular perceived percentages, for example, of the agent's neighbors or socio-economic peers making each choice. Discrete choice estimation results controlling these heterogeneous individual preferences are embedded in a multi-agent based simulation model in order to observe the evolution of choice behavior over time with socio-dynamic feedback due to the network effects. The MAS approach also gives us an additional advantage in the possibility to test size effects, and thus relax the assumption of large numbers, as well as test the effect of different initial conditions. Finally an extra benefit is gained via the MAS approach in that we are not confined to study only the equilibrium behavior, and have the possibility here to observe the time-varying trajectories of the choice behavior. This is important since smaller network sizes are revealed to be associated with higher volatility of the choice behavior in this model, and consequently stochastic cycling between equilibria. Averaged over time, the emergent behavior in such case yields a quite different picture than the theoretical results predicted by Brock and Durlauf. Furthermore being able to observe the emergent behavior allows us to see the subtle role of the unobserved heterogeneity in the nested logit model in breaking the symmetry of the multinomial logit model. We can see the temporal patterns by which theoretically predicted dominant equilibria emerge or not according to different social and spatial network scenarios. With an eye towards application in the context of transportation mode choice, we conclude highlighting limitations of our present study and recommendations for future work.

We are living in a world of various kinds of social information networks with small-world and scale-free characteristics. It is still an intriguing problem for researchers to explain how and why so many obviously different networks emerge and share common intrinsic characteristics such as short diameter, higher cluster and power-law degree distribution. Most previous works studied the topology formation and information navigation of complex networks in separated models. In this paper, we propose a metric based range intersection model to explore the topology evolution and information navigation in a synthetic way. We model the network as a set of nodes in a distance metric space where each node has an ID and a range of neighbor information around its ID in the metric space. The range of a node can be seen as the local knowledge or information that the node has around its position in the metric space. The topology is formed by setting up a link between two nodes that have intersected ranges. Information navigation over the network is modeled as a greedy routing process using neighbor links and the distance metric. Different from previous models, we do not assume that nodes join the network one by one and set up link according to the degree distribution of existing nodes or distances between nodes. Range of node is the key factor determining the topology and navigation properties of a network. Moreover, as the ranges of nodes grow, the network evolves from a set of totally isolated nodes to a connected network. Thus, we can easily model the network evolutions in terms of the network size and the individual node information range using the range intersection model. A set of experiments shows that networks constructed using the range intersection model have the scale-free degree distribution, high cluster, short diameter, and high navigability properties that are owned by the real networks.

Recently, Li and Pan defined the metric of the K-dimensional structure entropy of a structured noisy dataset G to be the information that controls the formation of the K-dimensional structure "Equation missing" of G that is evolved by the rules, order and laws of G, excluding the random variations that occur in G. Here, we propose the notion of resistance of networks based on the one- and two-dimensional structural information of graphs. Given a graph G, we define the resistance of G, written "Equation missing", as the greatest overall number of bits required to determine the code of the module that is accessible via random walks with stationary distribution in G, from which the random walks cannot escape. We show that the resistance of networks follows the resistance law of networks, that is, for a network G, the resistance of G is "Equation missing", where "Equation missing" and "Equation missing" are the one- and two-dimensional structure entropies of G, respectively. Based on the resistance law, we define the security index of a network G to be the normalised resistance of G, that is, "Equation missing". We show that the resistance and security index are both well-defined measures for the security of the networks.

Tourism is becoming a significant contributor to medium and long range travels in an increasingly globalized world. Leisure traveling has an important impact on the local and global economy as well as on the environment. The study of touristic trips is thus raising a considerable interest. In this work, we apply a method to assess the attractiveness of 20 of the most popular touristic sites worldwide using geolocated tweets as a proxy for human mobility. We first rank the touristic sites based on the spatial distribution of the visitors’ place of residence. The Taj Mahal, the Pisa Tower and the Eiffel Tower appear consistently in the top 5 in these rankings. We then pass to a coarser scale and classify the travelers by country of residence. Touristic site’s visiting figures are then studied by country of residence showing that the Eiffel Tower, Times Square and the London Tower welcome the majority of the visitors of each country. Finally, we build a network linking sites whenever a user has been detected in more than one site. This allow us to unveil relations between touristic sites and find which ones are more tightly interconnected., Partial financial support has been received from the Spanish Ministry of Economy (MINECO) and FEDER (EU) under project INTENSE@COSYP (FIS2012-30634), and from the EU Commission through project INSIGHT. The work of ML has been funded under the PD/004/2013 project, from the Conselleria de Educación, Cultura y Universidades of the Government of the Balearic Islands and from the European Social Fund through the Balearic Islands ESF operational program for 2013-2017. JJR acknowledges funding from the Ramón y Cajal program of MINECO. BG was partially supported by the French ANR project HarMS-flu (ANR-12-MONU-0018).

In this paper we study the extremal type problem arising from the question: What is the maximum number ET(S) of edges that a geometric graph G on a planar point set S can have such that it does not contain empty triangles? We prove: $${{n \choose 2} - O(n \log n) \leq ET(n) \leq {n \choose 2} - \left(n - 2 + \left\lfloor \frac{n}{8} \right\rfloor \right)}$$ .

Let P be a set of n points on the plane in general position, n ? 3. The edge rotation graph $${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$$ of P is the graph whose vertices are the plane geometric graphs on P with exactly k edges, two of which are adjacent if one can be obtained from the other by an edge rotation. In this paper we study some structural properties of $${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$$ , such as its connectivity and diameter. We show that if the vertices of $${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$$ are not triangulations of P, then it is connected and has diameter O(n 2). We also show that the chromatic number of $${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$$ is O(n), and show how to compute an implicit coloring of its vertices. We also study edge rotations in edge-labelled geometric graphs.

Spatial range query is one of the most common queries in spatial databases, where a user invokes a query to find all the surrounding interest objects. Most studies in range search consider Euclidean distances to retrieve the result in low cost, but with poor accuracy (i.e., Euclidean distance less than or equal network distance). Thus, researchers show that range search in network distance retrieves the results with high accuracy but with a vast amount of network distance computations. However, both of these techniques retrieve all objects in a given radius with a high number of false hits. Yet, in many situations, retrieving all objects is not necessary, especially when there are already enough objects closer to the query point. Also, when the radius of the search increases, a demotion in the performance will occur. Hence, approximate results are valuable just as the exact result, and approximate results can be obtained much faster than the exact result and are less costly. In this paper, we propose two approximate range search methods in spatial road network, namely approximate range Euclidean restriction and approximate range network expansion, to reduce the number of false hits and the number of network distance computations in a considerable manner. After the verification, these two methods are shown to be robust and accurate.

While much research in ecology has focused on spatially explicit modelling as well as on measures of biodiversity, the concept of spatial (or local) biodiversity has been discussed very little. This paper generalises existing measures of spatial biodiversity and introduces a family of spatial biodiversity measures by flexibly defining the notion of the individuals’ neighbourhood within the framework of graphs associated to a spatial point pattern. We consider two non-independent aspects of spatial biodiversity, scattering, i.e. the spatial arrangement of the individuals in the study area and exposure, the local diversity in an individual’s neighbourhood. A simulation study reveals that measures based on the most commonly used neigh-bourhood defined by the geometric graph do not distinguish well between scattering and exposure. This problem is much less pronounced when other graphs are used. In an analysis of the spatial diversity in a rainforest, the results based on the geometric graph have been shown to spuriously indicate a decrease in spatial biodiversity when no such trend was detected by the other types of neighbourhoods. We also show that the choice neighbourhood markedly impacts on the classification of species according to how strongly and in what way different species spatially structure species diversity. Clearly, in an analysis of spatial or local diversity an appropriate choice of local neighbourhood is crucial in particular in terms of the biological interpretation of the results. Due to its general definition, the approach discussed here offers the necessary flexibility that allows suitable and varying neighbourhood structures to be chosen. Postprint

A 2D topology-based digital image processing framework is presented here. This framework consists of the computation of a flexible geometric graph-based structure, starting from a raster representation of a digital image I. This structure is called Homological Spanning Forest (HSF for short), and it is built on a cell complex associated to I. The HSF framework allows an efficient and accurate topological analysis of regions of interest (ROIs) by using a four-level architecture. By topological analysis, we mean not only the computation of Euler characteristic, genus or Betti numbers, but also advanced computational algebraic topological information derived from homological classification of cycles. An initial HSF representation can be modified to obtain a different one, in which ROIs are almost isolated and ready to be topologically analyzed. The HSF framework is susceptible of being parallelized and generalized to higher dimensions.

In recent years, many information networks have become available for analysis, including social networks, road networks, sensor networks, biological networks, etc. Graph clustering has shown its effectiveness in analyzing and visualizing large networks. The goal of graph clustering is to partition vertices in a large graph into clusters based on various criteria such as vertex connectivity or neighborhood similarity. Many existing graph clustering methods mainly focus on the topological structures, but largely ignore the vertex properties which are often heterogeneous. Recently, a new graph clustering algorithm, SA-cluster, has been proposed which combines structural and attribute similarities through a unified distance measure. SA-Cluster performs matrix multiplication to calculate the random walk distances between graph vertices. As part of the clustering refinement, the graph edge weights are iteratively adjusted to balance the relative importance between structural and attribute similarities. As a consequence, matrix multiplication is repeated in each iteration of the clustering process to recalculate the random walk distances which are affected by the edge weight update. In order to improve the efficiency and scalability of SA-cluster, in this paper, we propose an efficient algorithm In-Cluster to incrementally update the random walk distances given the edge weight increments. Complexity analysis is provided to estimate how much runtime cost Inc-Cluster can save. We further design parallel matrix computation techniques on a multicore architecture. Experimental results demonstrate that Inc-Cluster achieves significant speedup over SA-Cluster on large graphs, while achieving exactly the same clustering quality in terms of intra-cluster structural cohesiveness and attribute value homogeneity.

A stochastic network model is developed which describes the 3D morphology of the pore space in fibre-based materials. It has the form of a random geometric graph, where the vertex set is modelled by random point processes and the edges are put using tools from graph theory and Markov chain Monte Carlo simulation. The model parameters are fitted to real image data gained by X-ray synchrotron tomography. In particular, they are specified in such a way that the distributions of vertex degrees and edge lengths, respectively, coincide to a large extent for real and simulated data. Furthermore, the network model is used to introduce a morphology-based notion of pores and their sizes. The model is validated by considering physical characteristics which are relevant for transport processes in the pore space, like geometric tortuosity, i.e., the distribution of shortest path lengths through the material relative to its thickness.

Spatial graphs in landscape ecology and conservation have emerged recently as a powerful methodology to model patterns in the topology and connectivity of habitat patches (structural connectivity) and the movement of genes, individuals or populations among these patches (potential functional connectivity). Most spatial graph’s applications to date have been in the terrestrial realm, whereas the use of spatially explicit graph-based methods in the freshwater sciences has lagged far behind. Although at first patch-based spatial graphs were not considered suitable for representing the branching network of riverine landscapes, here we argue that the application of graphs can be a useful tool for quantifying habitat connectivity of freshwater ecosystems. In this review we provide an overview of the potential of patch-based spatial graphs in freshwater ecology and conservation, and present a conceptual framework for the topological analysis of stream networks (i.e., riverscape graphs) from a hierarchical patch-based context. By highlighting the potential application of graph theory in freshwater sciences we hope to illustrate the generality of spatial network analyses in landscape ecology and conservation.

Skyline queries are used with data extensive applications, such as mobile location-based services, to support multi-criteria decision-making and to prune the data space by returning the most "interesting" data points. Most interesting data points are the points, which are not dominated by any other point. Spatial network skyline query is a subset of the skyline query problem where data points are nodes in a road network and the attributes of the data points are network distance relative to a set of query points. Spatial network skyline query's problem is the need to calculate the attributes with an expensive distance calculation operation. Previous works (Deng et al. Proceedings of the 23th international conference on data engineering, 796---805, 2007), Sharifzadeh et al. Proceedings of the 32nd international conference on very large databases, 751---762, 2009) that addressed this problem involved extensive network distance calculation between the query points and data points. A new algorithm that requires a remarkably less number of network distance calculations is proposed in this work. Our approach uses a progressive nearest neighbor algorithm to minimize the set of candidates then evaluates those candidates by only comparing them to a subset of discovered skyline points. Experiments showed the effectiveness of our algorithm compared to previous works.

Moving queries over mobile objects are an important type of query in moving object database systems. In recent years, there have been quite a few works in this area. Due to the high frequency in location updates and the expensive cost of continuous query processing, server computation capacity and wireless communication bandwidth are the two limiting factors for large-scale deployment of moving object database systems. Many techniques have been proposed to address the server bottleneck including one using distributed servers. To address both scalability factors, distributed query processing techniques have been considered. These schemes enable moving objects to participate in query processing to substantially reduce the demand on server computation, and wireless communications associated with location updates. Most of these techniques, however, assume an open-space environment. Since Euclidean distance is different from network distance, techniques designed specifically for an open space cannot be easily adapted for a spatial network. In this paper, we present a distributed framework which can answer moving query over moving objects in a spatial network. To illustrate the effectiveness of the proposed framework, we study two representative moving queries, namely, moving range queries and moving k-nearest-neighbor queries. Detailed algorithms and communication mechanisms are presented. The simulation studies indicate that the proposed technique can significantly reduce server workload and wireless communication cost.