Search

Trajectory similarity computation is an essential operation in many applications of spatial data analysis. In this paper, we study the problem of trajectory similarity computation over spatial network, where the real distances between objects are reflected by the network distance. Unlike previous studies which learn the representation of trajectories in Euclidean space, it requires to capture not only the sequence information of the trajectory but also the structure of spatial network. To this end, we propose GTS, a brand new framework that can jointly learn both factors so as to accurately compute the similarity. It first learns the representation of each point-of-interest (POI) in the road network along with the trajectory information. This is realized by incorporating the distances between POIs and trajectory in the random walk over the spatial network as well as the loss function. Then the trajectory representation is learned by a Graph Neural Network model to identify neighboring POIs within the same trajectory, together with an LSTM model to capture the sequence information in the trajectory. We conduct comprehensive evaluation on several real world datasets. The experimental results demonstrate that our model substantially outperforms all existing approaches.

Determining a protein's 3D from its sequences is one of the most challenging problems in biology. Recently, geometric deep learning has achieved great success on non-Euclidean domains including social networks, chemistry, and computer graphics. Although it is natural to present protein structures as 3D graphs, existing research has rarely studied protein structures as graphs directly. The present research explores the geometry deep learning of three-dimensional graphs on protein structures and proposes a graph neural network architecture to address these challenges. The proposed Protein Geometric Graph Neural Network (PG-GNN) models both distance geometric graph representation and dihedral geometric graph representation by geometric graph convolutions. This research shed new light on protein 3D structure studies. We investigated the effectiveness of graph neural networks over five real datasets. Our results demonstrate the potential of GNNs for 3D structure prediction.

This article presents a combined algorithm of pulmonary artery-vein (A/V) separation considering both global and local information, including: the transformation of geometric graph, sub-tree separation, and A/V classification. During the process, geometric graphs are firstly built based on the centerlines; A separation of the adhesion points is performed by applying the information stored in the data structure of the nodes and links in the geometric graphs; Sub-trees are then combined according to the local and global information; The combined sub-trees are growing into vascular trees using 2D area growth method; And finally, classification of the arterial and venous vascular trees based on the knowledge of anatomy. An average accuracy of 85% has been achieved of the overall process with a processing time range between 40 s to 50 s, which indicates good performance and stability of this algorithm.

Given a collection of multi-attribute trajectories, an event definition, and a spatial network, the Significant Lagrangian Linear Hotspot Discovery (SLLHD) problem finds the paths where records in the trajectories tend to be events in the Lagrangian perspective. The SLLHD problem is of significant societal importance because of its applications in transportation planning, vehicle design, and environmental protection. Its main challenges include the potentially large number of candidate hotspots caused by the tremendous volume of trajectories as well as the non-monotonicity of the statistic measuring event concentration. The related work on the linear hotspot discovery problem is designed in the Eulerian perspective and focuses on point datasets, which ignores the dependence of event occurrence on trajectories and the paths where trajectories are. To solve this problem, we introduce an algorithm in the Lagrangian perspective, as well as five refinements that improve its computational scalability. Two case studies on real-world datasets and experiments on synthetic data show that the proposed approach finds hotspots which are not detectable by existing techniques. Cost analysis and experimental results on synthetic data show that the proposed approach yields substantial computational savings.

Given two vertices of interest (POIs) s and t on a spatial network, a distance (path) query returns the shortest network distance (shortest path) from s to t. This query has a variety of applications in practice and is a fundamental operation for many database and data mining algorithms. In this paper, we propose an efficient distance and path oracle on dynamic road networks using the randomization technique. Our oracle has a good performance in practice and remarkably, and at the same time, it has a favorable theoretical bound. Specifically, it has O(n log2 n) (resp. O(n log2n)) preprocessing time (resp. space) and O(log4n log log n) (resp. O(log4n log log n+l)) distance query time (resp. shortest path query time) as well as O(log3n) update time with high probability (w.h.p.), where n is the number of vertices in the spatial network and l is the number of edges on the shortest path. Our experiments show that the existing oracles suffer from a huge updating time that renders them impractical and our oracle enjoys a negligible updating time and meanwhile has comparable query time and indexing cost with the best existing oracle. Ministry of Education (MOE) Nanyang Technological University Accepted version The research of Cheng Long is supported by the Nanyang Technological University Start-UP Grant from the College of Engineering under Grant M4082302 and by the Ministry of Education, Singapore, under its Academic Research Fund Tier 1 (RG20/19 (S)).

Recent years have witnessed the effective of attention network based on two-stream for video action recognition. However, most methods adopt the same structure on spatial stream and temporal stream, which produce amount redundant information and often ignore the relevance among channels. In this paper, we propose a channel-wise spatial attention with spatiotemporal heterogeneous framework, a new approach to action recognition. First, we employ two different network structures for spatial stream and temporal stream to improve the performance of action recognition. Then, we design a channel-wise network and spatial network inspired by self-attention mechanism to obtain the fine-grained and salient information of the video. Finally, the feature of video for action recognition is generated by end-to-end training. Experimental results on the datasets HMDB51 and UCF101 shows our method can effectively recognize the actions in the video.

Spatial hotspot discovery aims at discovering regions with statistically significant concentration of activities. It has shown great value in many important societal applications such as transportation engineering, public health, and public safety. This paper formulates the problem of Linear Hotspot Detection on All Simple Paths (LHDA) which identifies hotspots from the complete set of simple paths enumerated from a given spatial network. LHDA overcomes the limitations of existing methods which miss hotspots that naturally occur along linear simple paths on a road network. To address the computational challenges, we propose a novel algorithm named bidirectional fragment-multi-graph traversal (ASP_FMGT) and two path reduction approaches ASP_NR and ASP_HD. Experimental analyses show that ASP_FMGT has substantially improved performance over state-of-the-art approach (ASP_Base) while keeping the solution complete and correct. Moreover, a case study on real-world datasets showed that ASP_FMGT outperforms existing approaches.

Traditional navigation systems compute the quantitatively shortest or fastest route between two locations in a spatial network. In practice, a problem resulting from all drivers using the shortest path is the congregation of individuals on routes having a high in-betweenness. To this end, several works have proposed methods for proposing alternative routes. In this work, we test solutions for traffic load-balancing by computing diversified routes proposing variants of the penalty method using the road network of the Washington DC metropolitan area as a case study. Our experimental evaluation shows that the tested Penalty-based approaches allow to significantly balance the load of a spatial network, compared to existing k-shortest path algorithms, and compared to a naive baseline that randomly changes the weights of the network at each shortest-path computation.

The trajectory-aware lowest-cost path selection problem aims to find the lowest-cost path using trajectory data. Trajectory data is valuable since it carries information about travel cost along paths, and also reflects travelers' routing preference. Path-centric travel cost estimation models using trajectory data grows popular recently, which considers the auto-correlation of the energy consumption on different segments of a path. However, path-centric models are more computationally expensive than edge-centric models. The main challenge of this problem is that the travel cost of every candidate path explored during the process of searching for the lowest-cost path need to be estimated, resulting in high computational cost. The current path selection algorithms that use path-centric cost estimation models still follow the pattern of "path + edge" when exploring candidate paths, which may result in redundant computation. We introduce a trajectory-aware graph model in which each node is a maximal trajectory-aware path. Two nodes in the trajectory-aware graph are linked by an edge if their union forms a trajectory-union path. We then propose a path selection algorithm to find a path in the proposed trajectory-aware graph which corresponds to the lowest-cost path in the input spatial network. We prove theoretically the proposed algorithm is correct and complete. Moreover, we prove theoretically that the proposed path selection algorithm cost much less computational time than the algorithm used in the related work, and validate it through experiments using real-world trajectory data.

Location-based social networks (LBSNs) have been studied extensively in recent years. However, utilizing real-world LBSN datasets in such studies has severe weaknesses: sparse and small datasets, privacy concerns, and a lack of authoritative ground-truth. Our vision is to create a large scale geo-simulation framework to simulate human behavior and to create synthetic but realistic LBSN data that captures the location of users over time as well as social interactions of users in a social network. While existing LBSN datasets are trivially small, such a framework would provide the first source of massive LBSN benchmark data which would closely mimic the real world, containing high-fidelity information of location, and social connections of millions of simulated agents over several years of simulated time. Therefore, it would serve the research community by revitalizing and reshaping research on LBSNs by allowing researchers to see the (simulated) world through the lens of an omniscient entity having perfect data. These evaluations will guide future research enabling us to develop solutions to improve LBSN applications such as user-location recommendation, friend recommendation, location prediction, and location privacy.

This paper describes the use of graph analysis for spatial networks. The use of community detection algorithms for detecting communities- groups of similar objects within networks of land cover objects to determine the land use is evaluated. Land cover to land use transformation requires some knowledge to merge land cover objects. Community detection algorithms merge objects of the formed spatial network into communities. Community detection algorithms are efficient analysis tool for spatial graphs and can identify land use communities but with different characteristics, although spatial networks with topological relationships between objects can cause some problems.

Due to the recent popularization of the Geographic Information System (GIS), spatial network environments that can display the changes of spatial axes on mobile phones are receiving great attention. In spatial network environments, since a query object that seeks location information selects several candidate target objects based on the search conditions, we often use a k-nearest neighbor (kNN) search, which seeks several target objects near the query object. However, since a kNN search needs to find the kNN by calculating the distance from the query to all the objects, the computational complexity might become too large, depending on the number of objects. To reduce this computation time in a kNN search, many researchers have proposed a search method that divides regions using a Voronoi diagram. In this method, we reduce the computational complexity by generating Voronoi regions for each object based on the positional relationships between two objects. In addition, a search method was proposed to reduce the processing time by generating Voronoi diagrams using a contact zone. However, since conventional methods generate Voronoi diagrams for objects in order, the computational complexity might become too large, depending on the number of objects. In this paper, we propose a generation method of the Voronoi diagram to the reduce processing time by parallelizing the generation of Voronoi regions using a contact zone. In our evaluation, we confirmed that the processing time under the proposed method was reduced about 15.9% more than conventional methods that are not parallelized.

This paper presents a solution to the problem posed in the ACM SIGSPATIAL GIS Cup 2018, namely to identify all upstream features---nodes and edges existing on simple paths between starting points and controllers---in a given spatial network. Our approach is based primarily on a two-sweep depth-first search which decomposes a graph into its biconnected components prior to collecting the upstream features. Our algorithm runs in linear time in the size of the graph and, in practice, is able to solve large instances with millions of features within seconds on an ordinary personal laptop, identifying features if and only if they are upstream.

Almost all spatial systems can be modelled as networks. Typically, networks representations of real systems are static, useful for generating descriptive network measures. However, recent interest lies in the representation and analysis of evolving spatial networks that can facilitate the examination of the close coupling between network structure and network dynamics. Therefore, this study proposes a novel spatial modelling framework, Geographic Network Automata (GNA), to represent evolving spatial networks as a function of iteratively applied transition rules. The framework is demonstrated using an adapted and spatially explicit version of Conway's Game of Life. The simulated spatial network structures are quantified using network measures. The presented GNA model framework is general and flexible so that different types of geospatial phenomena can be modelled, providing valuable insights into the link between network structure, dynamics, and evolution.

We consider an agent-based distributed algorithm with exponentially distributed waiting times in which agents with binary states interact locally over a geometric graph, and based on this interaction and on the value of a common intolerance threshold τ, decide whether to change their states. This model is equivalent to an Asynchronous Cellular Automaton (ACA) with extended Moore neighborhoods, a zero-temperature Ising model with Glauber dynamics, or a Schelling model of self-organized segregation in an open system, and has applications in the analysis of social and biological networks, and spin glasses systems. We prove a shape theorem for the spread of the “affected” nodes during the process dynamics and show that in the steady state, for τ ∈ (τ*,1−τ*) ∖ {1/2}, where τ* ≈ 0.488, the size of the “mono-chromatic region” at the end of the process is at least exponential in the size of the local neighborhood of interaction with probability approaching one as N grows. Combined with previous results on the expected size of the monochromatic region that provide a matching upper bound, this implies that in the steady state the size of the monochromatic region of any agent is exponential with high probability for the mentioned interval of τ. The shape theorem is based on a novel concentration inequality for the spreading time, and provides a precise geometrical description of the process dynamics. The result on the size of the monochromatic region considerably extends our understanding of the steady state. Showing convergence with high probability, it rules out the possibility that only a small fraction of the nodes are eventually contained in large monochromatic regions, which was left open by previous works.

Nowadays, large-scale graph data is being generated in a variety of real-world applications, from social networks to co-authorship networks, from protein-protein interaction networks to road traffic networks. Many existing works on graph mining focus on the vertices and edges, with the first-order Markov chain as the underlying model. They fail to explore the high-order network structures, which are of key importance in many high impact domains. For example, in bank customer personally identifiable information (PII) networks, the star structures often correspond to a set of synthetic identities; in financial transaction networks, the loop structures may indicate the existence of money laundering. In this paper, we focus on mining user-specified high-order network structures and aim to find a structure-rich subgraph which does not break many such structures by separating the subgraph from the rest. A key challenge associated with finding a structure-rich subgraph is the prohibitive computational cost. To address this problem, inspired by the family of local graph clustering algorithms for efficiently identifying a low-conductance cut without exploring the entire graph, we propose to generalize the key idea to model high-order network structures. In particular, we start with a generic definition of high-order conductance, and define the high-order diffusion core, which is based on a high-order random walk induced by user-specified high-order network structure. Then we propose a novel High-Order Structure-Preserving LOcal Cut (HOSPLOC) algorithm, which runs in polylogarithmic time with respect to the number of edges in the graph. It starts with a seed vertex and iteratively explores its neighborhood until a subgraph with a small high-order conductance is found. Furthermore, we analyze its performance in terms of both effectiveness and efficiency. The experimental results on both synthetic graphs and real graphs demonstrate the effectiveness and efficiency of our proposed HOSPLOC algorithm.

Finding communities in networks has become very important because various social and physical complex systems are represented as networks. Because of their ability to address large networks, local community detection methods that start from a seed node have become the focus of many research endeavours in recent times. In this paper, a derivative-based local community detection method, inspired by active contours, is proposed for finding a community surrounding an initial seed. The method is based on the concepts of curvature and gradient of the current communitys boundary. Curvature and gradient comprise the velocity function used to determine whether the boundary should move to include a candidate node in its vicinity. Unlike Euclidean space, networks have non-uniform space with fluctuations of dimensionality, given by the fluctuation in degrees of nodes, which complicates the calculation of derivatives used to define the curvature and gradient of boundary nodes. In this research, with some intuitive imagination, a framework for approximating derivatives in network space is proposed. Benchmarking this community detection method against three contemporary methods shows that it is capable of building communities with equal or better conductance.

This work studies centralized slow-timescale spectrum management in metropolitan area networks with a very large number of access points (APs) and user equipments (UEs). The joint spectrum allocation and user association problem is first formulated as a convex optimization problem with an exponential number of variables in the network size. A scalable reformulation is obtained by exploiting the geometric graph nature of the network and provable sparsity of the optimal solution. A pattern pursuit algorithm with low complexity is proposed to solve the reformulated problem with guaranteed gap to the global optimum. Efficient algorithms are developed to obtain near-optimal allocations for a network with up to 1000 APs and 2500 active users. Numerical results show that the proposed solution achieves significant gains in terms of delay and throughput over existing schemes and is within 7% to the global optimum in a typical scenario.

Due to the recent popularization of Geographic Information System (GIS), spatial network environments that can display the changes of spatial axes in mobile phones have received much attention. Many searching methods have proposed reverse k-nearest neighbor (RkNN) searching methods that consider the inverse direction with the position between the query and target objects. In this paper, we propose and evaluate a searching method for a bichromatic reverse k-nearest neighbor (BRkNN) that has objects and queries in spatial networks. In our proposed method, we search for the BRkNN of the query using an influence zone for each object with a Network Voronoi Diagram.

Networks are a fundamental tool for understanding and modeling complex systems in physics, biology, neuroscience, engineering, and social science. Many networks are known to exhibit rich, lower-order connectivity patterns that can be captured at the level of individual nodes and edges. However, higher-order organization of complex networks -- at the level of small network subgraphs -- remains largely unknown. Here, we develop a generalized framework for clustering networks on the basis of higher-order connectivity patterns. This framework provides mathematical guarantees on the optimality of obtained clusters and scales to networks with billions of edges. The framework reveals higher-order organization in a number of networks, including information propagation units in neuronal networks and hub structure in transportation networks. Results show that networks exhibit rich higher-order organizational structures that are exposed by clustering based on higher-order connectivity patterns.Prediction tasks over nodes and edges in networks require careful effort in engineering features used by learning algorithms. Recent research in the broader field of representation learning has led to significant progress in automating prediction by learning the features themselves. However, present feature learning approaches are not expressive enough to capture the diversity of connectivity patterns observed in networks. Here we propose node2vec, an algorithmic framework for learning continuous feature representations for nodes in networks. In node2vec, we learn a mapping of nodes to a low-dimensional space of features that maximizes the likelihood of preserving network neighborhoods of nodes. We define a flexible notion of a node's network neighborhood and design a biased random walk procedure, which efficiently explores diverse neighborhoods. Our algorithm generalizes prior work which is based on rigid notions of network neighborhoods, and we argue that the added flexibility in exploring neighborhoods is the key to learning richer representations. We demonstrate the efficacy of node2vec over existing state-of-the-art techniques on multi-label classification and link prediction in several real-world networks from diverse domains. Taken together, our work represents a new way for efficiently learning state-of-the-art task-independent representations in complex networks.

Traditional route planning problems mainly focus on finding the shortest path considering the travel distance or time. In this paper, we aim to find the most scenic path that offers the most beautiful sceneries on the arcs of a path while the total travel cost (distance or time) is within a user-specified budget. This is a challenging problem as the optimization objective is to maximize the value of the path (i.e., its scenic value) instead of minimizing its cost (distance or time). The problem can be formulated as a variant of the Arc Orienteering Problem (AOP), which is a well-known NP-hard combinatorial optimization problem. Due to the fast response-time requirements of interactive mobile and online applications (e.g., within 300 milliseconds) and the large scale of real-world road networks, existing heuristic algorithms for AOP fail to solve the most scenic road problem. Therefore, unlike the existing approaches for AOP where they treat the road network as a traditional graph in which all-pair distances are pre-computed a priori, in this work, we treat the road network as a spatial network, utilizing the techniques from the field of spatial database: ellipse pruning and spatial indexing. Experiments on two real-world datasets demonstrate the efficiency and accuracy of our proposed algorithms, which can achieve over 95% accuracy within 300 milliseconds on large-scale datasets (over 100K network nodes).

Online social networks have become ubiquitous to today's society and the study of data from these networks has improved our understanding of the processes by which relationships form. Research in statistical relational learning focuses on methods to exploit correlations among the attributes of linked nodes to predict user characteristics with greater accuracy. Concurrently, research on generative graph models has primarily focused on modeling network structure without attributes, producing several models that are able to replicate structural characteristics of networks such as power law degree distributions or community structure. However, there has been little work on how to generate networks with real-world structural properties and correlated attributes. In this work, we present the Attributed Graph Model (AGM) framework to jointly model network structure and vertex attributes. Our framework learns the attribute correlations in the observed network and exploits a generative graph model, such as the Kronecker Product Graph Model (KPGM) and Chung Lu Graph Model (CL), to compute structural edge probabilities. AGM then combines the attribute correlations with the structural probabilities to sample networks conditioned on attribute values, while keeping the expected edge probabilities and degrees of the input graph model. We outline an efficient method for estimating the parameters of AGM, as well as a sampling method based on Accept-Reject sampling to generate edges with correlated attributes. We demonstrate the efficiency and accuracy of our AGM framework on two large real-world networks, showing that AGM scales to networks with hundreds of thousands of vertices, as well as having high attribute correlation.

While ethnic segregation plays an important role in determining the development trajectories of many countries, empirical measures of the dynamics of segregation remain rudimentary. In this paper, we develop a new computational framework to model and measure fine-grained patterns of segregation from novel sources of large-scale digital data. This framework improves upon prior work by providing a method for decomposing segregation into two types that previous work has been unable to separate: social segregation, as observed in interactions between people, and spatial segregation, as determined by the co-presence of individuals in physical locations. Our primary contribution is thus to develop a set of computational and quantitative methods that can be used to study segregation using generic spatial network data. A secondary contribution is to discuss in detail the strengths, weaknesses, and implications of this approach for studying segregation in developing countries, where ethnic divisions are common but data on segregation is often plagued by issues of bias and error. Finally, to demonstrate how this framework can be used in practice, and to illustrate the differences between social and spatial segregation, we run a series of diagnostic tests using data from a single city in a large developing country in South Asia. The case study we develop is based on anonymized data from a mobile phone network, but the framework can generalize easily to a broad class of spatial network data from sources such as Twitter, social media, and networked sensors.

This paper introduces a graph-based and structural model for the representation of land spaces. We develop a spatial model that integrates three complementary abstractions (i.e., parcels, buildings, roads) that provide a spatial and structural representation. The modeling approach retains different categories of topological relations between parcels, buildings and roads, thus generating different graphs whose properties are evaluated and computed using graph-based operators. The union of these graphs generates a connected spatial graph where buildings are closely associated to parcels and the road network, then providing many opportunities for structural analysis.

What do large networks look like? Can we visually tell the topological difference between networks such as the Web graph and Facebook network? Due to the huge size of the network, the overall structure will not be discernible if all the nodes and edges are plotted regardless of the graph layout. We reduce the number of nodes and edges by producing a representative subgraph. The nodes are sampled with probability proportional to their degrees, so that large nodes with more connections have a higher probability of being sampled. The edges are reduced further using uniform random spanning tree. The efficacy of the method is demonstrated to preserve the community structure that is characterized by the Network Community Profile (NCP). The result is supported by six real-world large networks, and demonstrated on Twitter user network which contains 4.1 × 107 nodes.

Let C=C1,...,Cn} be a set of n pairwise-disjoint convex s-gons, for some constant s, and let p be a probability density function (pdf) over the non-negative reals. For each i, let Ki be the Minkowski sum of Ci with a disk of radius ri, where each ri is a random non-negative number drawn independently from the distribution determined by π. We show that the expected complexity of the union of K1,..,Kn is O(n log n), for any pdf p; the constant of proportionality depends on s, but not on the pdf. Next, we consider the following problem that arises in analyzing the vulnerability of a network under a physical attack. Let G=(V,E) be a planar geometric graph where E is a set of n line segments with pairwise-disjoint relative interiors. Let f: R -> [0,1] be an edge failure probability function, where a physical attack at a location x causes an edge e of E at distance r from x to fail with probability f(r); we assume that f is of the form f(x)=1-P(x), where P is a cumulative distribution function on the non-negative reals. The goal is to compute the most vulnerable location for G, i.e., the location of the attack that maximizes the expected number of failing edges of G. Using our bound on the complexity of the union of random Minkowski sums, we present a near-linear Monte-Carlo algorithm for computing a location that is an approximately most vulnerable location of attack for G.

Data about moving objects is being collected in many different application domains with the help of sensor networks, and GPS-enabled devices. In most cases, the moving objects are not free to move, they are usually restricted by some spatial constraints such as Spatial Networks. Spatial networks are ubiquitous and have been widely used in transportation, traffic planning, navigation as well as in Geographical Information System (GIS) applications. In most scenarios, moving objects such as vehicles move along predefined spatial networks like transportation networks. Unfortunately, the concepts for modeling and querying objects in unconstrained spaces like an outdoor space cannot be transferred to constrained spaces like a road network due to the different features of the environments in which the spatial objects move. Further, modern positioning devices as well as mobile and sensor technology have led to large volumes of moving objects in spatial networks. Therefore, we need a database-friendly data model to explicitly model spatial networks and, more importantly, describe relative movements in these networks. In this paper, we propose a new two-layered data model called MONET (Moving Objects in NETworks) model. The lower layer is a data model for spatial networks. This data model is the prerequisite for the upper model that represents moving objects in these networks. This layered model fits well to formulate relationships between moving objects and a network in queries. A query language, called MONET QL (MONET Query Language), allows a clear description of and access to moving objects in spatial networks and to provides high-level operations on them.

The explosive growth of social networks has created numerous exciting research opportunities. A central concept in the analysis of social networks is a proximity measure, which captures the closeness or similarity between nodes in the network. Despite much research on proximity measures, there is a lack of techniques to efficiently and accurately compute proximity measures for large-scale social networks. In this paper, we embed the original massive social graph into a much smaller graph, using a novel dimensionality reduction technique termed Clustered Spectral Graph Embedding. We show that the embedded graph captures the essential clustering and spectral structure of the original graph and allow a wide range of analysis to be performed on massive social graphs. Applying the clustered embedding to proximity measurement of social networks, we develop accurate, scalable, and flexible solutions to three important social network analysis tasks: proximity estimation, missing link inference, and link prediction. We demonstrate the effectiveness of our solutions to the tasks in the context of large real-world social network datasets: Flickr, LiveJournal, and MySpace with up to 2 million nodes and 90 million links.

navigation systems, allow users to record their location history. The location history data can be analyzed to generate life patterns|patterns that associate people to places they frequently visit. Accordingly, an SSN is a graph that consists of (1) a social network, (2) a spatial network, and (3) life patterns that connect the users of the social network to locations, i.e., to geographical entities in the spatial network. In this paper we present a system that stores SNN in a graph-based database management system and provides a novel query language, namely SSNQL, for querying the integrated data. The system includes a Web-based graphical user interface that allows presenting the social network, presenting the spatial network and posing SSNQL queries over the integrated data. The user interface also depicts the structure of queries for the purpose of debugging and optimization. Our demonstration presents the management of the integrated data as an SSN and it illustrates the query evaluation process in SSNQL.

With the recent advances in information networks, the problem of community detection has attracted much attention in the last decade. While network community detection has been ubiquitous, the task of collecting complete network data remains challenging in many real-world applications. Usually the collected network is incomplete with most of the edges missing. Commonly, in such networks, all nodes with attributes are available while only the edges within a few local regions of the network can be observed. In this paper, we study the problem of detecting communities in incomplete information networks with missing edges. We first learn a distance metric to reproduce the link-based distance between nodes from the observed edges in the local information regions. We then use the learned distance metric to estimate the distance between any pair of nodes in the network. A hierarchical clustering approach is proposed to detect communities within the incomplete information networks. Empirical studies on real-world information networks demonstrate that our proposed method can effectively detect community structures within incomplete information networks.

Cellular phones and GPS-based navigation systems allow recording the location history of users, to find places the users frequently visit and routes along which the users frequently travel. This provides associations between users and geographic entities. Considering these associations as edges that connect users of a social network to geographical entities on a spatial network yields an integrated socio-spatial network. Queries over a socio-spatial network glean information on users, in correspondence with their location history, and retrieve geographical entities in association with the users who frequently visit these entities.In this paper we present a graph model for socio-spatial networks that store information on frequently traveled routes. We present a query language that consists of graph traversal operations, aiming at facilitating the formulation of queries, and we show how queries over the network can be evaluated efficiently. We also show how social-based route recommendation can be implemented using our query language. We describe an implementation of the suggested model over a graph-based database system and provide an experimental evaluation, to illustrate the effectiveness of our model.

Wireless networks are usually modeled as spatial objects, and more specifically with random processes generating the locations of individual nodes. This is in stark contrast to the fixed networks case, in which graph models are typically used. While expressive, spatial models are usually more difficult to analyze than graph based ones, which has resulted in adoption of oversimplified models in wireless networks research. In this paper we show how wireless networks can be modeled as graphs without losing the accuracy of spatial models. We argue based on measurements of wireless network performance that in a number of cases distance-dependent interactions between wireless nodes can be discretized with only small approximation error. This discretization immediately yields an approximation of a spatial wireless network model as a graph with multiple edge types. We study the structure of the arising graph models, and show that the choice of accurate underlying spatial model remains important. For accurate spatial models, the corresponding graph approximations have a relatively simple neighborhood structure, indicating that they can be used very effectively in performance evaluation and optimization applications.

While it is important to design anonymity systems to be robust against attacks, it is also important to provide good performance to users. We explore ways to improve the security and performance of anonymity systems by building both security and performance properties into the network topology. In particular, we study an expander graph based network topology and apply link-based performance metrics in order to build the topology graph. Such a network can be constructed to have enhanced performance and similar security properties to restricted route topologies with random links. Results show that a sparse, D-regular expander graph topology provides nearly the same security, as measured by the likelihood of an incoming stream exiting through any node in the network, as with a fully-connected graph. Further, when the expander graph is constructed with a bias towards faster links, there is a considerable gain in performance without much loss of security.

We prove that for every even set of $n$ pairwise disjoint line segments in the plane in general position, there is another set of n segments such that the 2n segments form pairwise disjoint simple polygons in the plane. This settles in the affirmative the Disjoint Compatible Matching Conjecture by Aichholzer et al. [ABD08]. The key tool in our proof is a novel subdivision of the free space around n disjoint line segments into at most n+1 convex cells such that the dual graph of the subdivision contains two edge-disjoint spanning trees.

Given two vertices s, t in a graph, let P be the shortest path (SP) from s to t, and P* a subset of the vertices in P. P* is a k-skip shortest path from s to t, if it includes at least a vertex out of every k consecutive vertices in P. In general, P* succinctly describes P by sampling the vertices in P with a rate of at least 1/k. This makes P* a natural substitute in scenarios where reporting every single vertex of P is unnecessary or even undesired.This paper studies k-skip SP computation in the context of spatial network databases (SNDB). Our technique has two properties crucial for real-time query processing in SNDB. First, our solution is able to answer k-skip queries significantly faster than finding the original SPs in their entirety. Second, the previous objective is achieved with a structure that occupies less space than storing the underlying road network. The proposed algorithms are the outcome of a careful theoretical analysis that reveals valuable insight into the characteristics of the k-skip SP problem. Their efficiency has been confirmed by extensive experiments with real data.

The most common type of queries in online social networks are news feeds of friends' recent activities. These queries involve the retrieval of multiple small records generated by different users in the network, and the results are time dependent. Hash-based horizontal partitioning of data results in accesses at multiple servers, which significantly affects throughput and response time. Partitioning of social network data is difficult because of the power-law degree distribution of the friendship graph, and the time dependency of queries and user activities. The power-law degree distribution results in a tremendous amount of extra storage for replication-based partitions, and the time dependency makes query-driven partitioning ineffective. We propose to partition not only the spatial network of social relations, but also in the time dimension so that users who have communicated in a given period are grouped together. We build an activity prediction graph to capture relationships with strong activity and serve as the basis for partitioning. New nodes occurring in the current period are added greedily. We test the partitioning results with emulation of Facebook page downloads, and show that our algorithm achieves 10 times better data locality than hash-based horizontal partitioning algorithms. We show the quality of activity prediction by observing that the algorithm with prediction achieves 80% data locality of that with perfect knowledge of the current period.

Spatial networks like transportation, power, and pipeline networks are a ubiquitous spatial concept in everyday life and play an important role for navigational and routing purposes. Database support for large spatial networks in order to represent, store, query, and manipulate them is rare. Our paper aims to provide the beginning of a conceptual, abstract, and formal model of spatial networks, called Spatial Network Algebra (SNA), that includes types and operations and is supposed to serve as a specification for their later implementation in spatial database systems and GIS. Finally, we show how our spatial network concepts can be embedded into an SQL-like query language.

Query processing for trajectory data is very important to spatio-temporal databases. Most of the research work in this field is based on the Euclidean space. However, in many applications, the spatio-temporal trajectories of moving objects are distributed in spatial network environment intensively, and the movements of moving objects are constrained by given network segments. Under such circumstances, existing Euclidean-based methods are ineffective. In this paper, we present a Network Voronoi Diagram (NVD) based method, to solve range query problem on a huge amount of spatio-temporal trajectories in spatial networks. The experiments demonstrated that our method is very efficient even when the trajectory datasets are huge.

Recording the location of people using location-acquisition technologies, such as GPS, allows generating life patterns, which associate people to places they frequently visit. Considering life patterns as edges that connect users of a social network to geographical entities on a spatial network, enriches the social network, providing an integrated socio-spatial graph. Queries over such graph extract information on users, in correspondence with their location history, and extract information on geographical entities in correspondence with users who frequently visit these entities.In this paper we present the concept of a socio-spatial graph that is based on life patterns, where users are connected to geographical entities using life-pattern edges. We provide a set of operators that form a query language suitable for the integrated data. We consider two implementations of a socio-spatial graph storage---one implementation uses a relational database system as the underline data storage, and the other employs a graph database system. The two implementations are compared, experimentally, for various queries and data. An important contribution of this work is in illustrating the usefulness and the feasibility of maintaining and querying integrated socio-spatial graphs.

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 paper, we focus on optimal network location (ONL) queries, i.e., optimal location queries with which objects and sites reside on a spatial network. We introduce an approach, namely EONL (short for Expansion-based ONL), which enables efficient computation of ONL queries. Moreover, with an extensive experimental study we verify and compare the efficiency of our proposed approach with real datasets, and we demonstrate the importance of considering network distance (rather than p-norm distance) with ONL queries.

In this paper, we investigate the role of power allocation in wireless ad hoc networks. First, by modeling the network with a random geometric graph, we propose a two-level power allocation scheme with the total power constraint which expands the min-cut of the underlying random geometric graph. Then, based on available information theoretic upper bounds on transport capacity of wireless networks, we find a new power allocation which improves such bound. As will be shown, the new bound is computed based on the largest eigenvalue of a structural matrix which depends on the random location of the nodes. Finally, it will be shown that both approaches (random geometric graph min-cut analysis and the information theoretic upper bound framework) reveal that it is a fundamental network design guideline that more power should be allocated to central nodes of the network.

Co-citation (number of nodes linking to both of a given pair of nodes) is often used heuristically to judge similarity between nodes in a complex network. We investigate the relation between node similarity and co-citation in the context of the Spatial Preferred Attachment (SPA) model. The SPA model is a spatial model, where nodes live in a metric space, and nodes that are close together in space are considered similar, and are more likely to link to one another.Theoretical analysis of the SPA model leads to a measure to estimate spatial distance from the link information, based on co-citation as well as the degrees of both nodes. Simulation results show this measure to be highly accurate in predicting the actual spatial distance.

The availability of indoor positioning renders it possible to deploy location-based services in indoor spaces. Many such services will benefit from the efficient support for k nearest neighbor (kNN) queries over large populations of indoor moving objects. However, existing kNN techniques fall short in indoor spaces because these differ from Euclidean and spatial network spaces and because of the limited capabilities of indoor positioning technologies.To contend with indoor settings, we propose the new concept of minimal indoor walking distance (MIWD) along with algorithms and data structures for distance computing and storage; and we differentiate the states of indoor moving objects based on a positioning device deployment graph, utilize these states in effective object indexing structures, and capture the uncertainty of object locations. On these foundations, we study the probabilistic threshold kNN (PTkNN) query. Given a query location q and a probability threshold T, this query returns all subsets of k objects that have probability larger than T of containing the kNN query result of q. We propose a combination of three techniques for processing this query. The first uses the MIWD metric to prune objects that are too far away. The second uses fast probability estimates to prune unqualified objects and candidate result subsets. The third uses efficient probability evaluation for computing the final result on the remaining candidate subsets. An empirical study using both synthetic and real data shows that the techniques are efficient.

A geometric graph is a graph embedded in the plane with vertices at points and edges drawn as curves (which are usually straight line segments) between those points. The average transversal complexity of a geometric graph is the number of edges of that graph that are crossed by random line or line segment. In this paper, we study the average transversal complexity of road networks. By viewing road networks as multiscale-dispersed graphs, we show that a random line will cross the edges of such a graph O(sqrt(n)) times on average. In addition, we provide by empirical evidence from experiments on the road networks of the fifty states of United States and the District of Columbia that this bound holds in practice and has a small constant factor. Combining this result with data structuring techniques from computational geometry, allows us to show that we can then do point location and ray-shooting navigational queries with respect to road networks in O(sqrt(n) log n) expected time. Finally, we provide empirical justification for this claim as well., Fuller version of paper appearing in ACM GIS '09

A spatiotemporal network is a spatial network (e.g., road network) along with the corresponding time-dependent weight (e.g., travel time) for each edge of the network. The design and analysis of policies and plans on spatiotemporal networks (e.g., path planning for location-based services) require realistic models that accurately represent the temporal behavior of such networks. In this paper, for the first time we propose a traffic modeling framework for road networks that enables 1) generating an accurate temporal model from archived temporal data collected from a spatiotemporal network (so as to be able to publish the temporal model of the spatiotemporal network without having to release the real data), and 2) augmenting any given spatial network model with a corresponding realistic temporal model custom-built for that specific spatial network (in order to be able to generate a spatiotemporal network model from a solely spatial network model). We validate the accuracy of our proposed modeling framework via experiments. We also used the proposed framework to generate the temporal model of the Los Angeles County freeway network and publish it for public use.

A quasi-unit disk graph has been used as a realistic model of an ad-hoc or a sensor wireless network. A wireless ad-hoc network is location aware if each node knows its geographic coordinates. Some network backbones proposed for data gathering in a wireless network are based on dominating sets of the network graph. The location awareness of ad-hoc networks corresponding to unit disk graph was used in [6] to obtain a local algorithm for a dominating set of a unit disk graph. In this paper we generalize this algorithm to location aware ad-hoc networks corresponding to quasi-unit graphs. The competitive ratio of the algorithm is determined for several ranges of the parameter r of an r--quasi-unit disk graph. For each range of r the competitive ratio is shown to be a constant value. An experimental evaluation of the algorithm is also carried out, which confirms very good performance of our algorithm.

We describe how to build a relative neighborhood graph on a real network without any positioning system. We base the computation of the RNG on a RSSI weight function and show how to adapt transmission power to the resulting graph.

Isochrones are defined as the set of all points from which a specific point of interest is reachable within a given time span. This demo paper presents a solution to compute isochrones in multi-modal, schedule-based transport networks. The system is implemented in Java on top of the Oracle Spatial Network Model and is deployed at the Municipality of Bolzano-Bozen as a planning instrument.

Modern applications requiring spatial network processing pose many interesting query optimization challenges. In many cases, query processing depends on the corresponding graph size (number of nodes and edges) and other graph parameters. In this paper, we present novel methods to estimate the number of nodes in regions of interest in spatial networks, towards predicting the space and time requirements of range queries. We examine all methods by using real-life and synthetic spatial networks. Experimental results show that the number of nodes can be estimated efficiently and accurately with small space requirements, thus providing useful information to the query optimizer.

Aggregate K Nearest Neighbor (AKNN) queries are problematic when performed within spatial networks. While simpler network queries may be solved by a single network traversal search, the AKNN requires a large number costly network distance computations to completely compute results. The M-Tree index, when used with Road Network Embedding, provides an efficient alternative which can return estimates of the AKNN results. The M-Tree index can then be used as a filter for AKNN results by quickly computing a superset of the query results. The final AKNN query results can be computed by sorting the results from the M-Tree. In comparison to Incremental Euclidean Restriction (IER), the M-Tree reduces the overall query processing time and the total number of necessary network distance computations required to complete a query. In addition, the M-Tree filtering method is tunable to allow increasing performance at the expense of accuracy, making it suitable for a wide variety of applications.