Data requirements and graph data structures for a multi-modal, multi-objective trip planner

Traffic congestion has a significant impact on the economy and environment. Encouraging the use of multimodal transport (public transport, bicycle, park’n’ride, etc.) has been identified by traffic operators as a good strategy to tackle congestion issues and its detrimental environmental impacts. A multi-modal and multi-objective trip planner provides users with various multi-modal options optimised on objectives that they prefer (cheapest, fastest, safest, etc) and has a potential to reduce congestion on both a temporal and spatial scale. The computation of multi-modal and multi-objective trips is a complicated mathematical problem, as it must integrate and utilize a diverse range of large data sets, including both road network information and public transport schedules, as well as optimising for a number of competing objectives, where fully optimising for one objective, such as travel time, can adversely affect other objectives, such as cost. The relationship between these objectives can also be quite subjective, as their priorities will vary from user to user. This paper will first outline the various data requirements and formats that are needed for the multi-modal multi-objective trip planner to operate, including static information about the physical infrastructure within Brisbane as well as real-time and historical data to predict traffic flow on the road network and the status of public transport. It will then present information on the graph data structures representing the road and public transport networks within Brisbane that are used in the trip planner to calculate optimal routes. This will allow for an investigation into the various shortest path algorithms that have been researched over the last few decades, and provide a foundation for the construction of the Multi-modal Multi-objective Trip Planner by the development of innovative new algorithms that can operate the large diverse data sets and competing objectives.

A semi-supervised graph-based algorithm for detecting outliers in online-social-networks

In this paper, we propose a semi-supervised approach of anomaly detection in Online Social Networks. The social network is modeled as a graph and its features are extracted to detect anomaly. A clustering algorithm is then used to group users based on these features and fuzzy logic is applied to assign degree of anomalous behavior to the users of these clusters. Empirical analysis shows effectiveness of this method.

A people-to-people matching system using graph mining techniques

A people-to-people matching system (or a match-making system) refers to a system in which users join with the objective of meeting other users with the common need. Some real-world examples of these systems are employer-employee (in job search networks), mentor-student (in university social networks), consume-to-consumer (in marketplaces) and male-female (in an online dating network). The network underlying in these systems consists of two groups of users, and the relationships between users need to be captured for developing an efficient match-making system. Most of the existing studies utilize information either about each of the users in isolation or their interaction separately, and develop recommender systems using the one form of information only. It is imperative to understand the linkages among the users in the network and use them in developing a match-making system. This study utilizes several social network analysis methods such as graph theory, small world phenomenon, centrality analysis, density analysis to gain insight into the entities and their relationships present in this network. This paper also proposes a new type of graph called “attributed bipartite graph”. By using these analyses and the proposed type of graph, an efficient hybrid recommender system is developed which generates recommendation for new users as well as shows improvement in accuracy over the baseline methods.

Brisbane Macroscopic Fundamental Diagram : empirical findings on network partitioning and incident detection

The Macroscopic Fundamental Diagram (MFD) relates space-mean density and flow, and the existence with dynamic features was confirmed in congested urban network in downtown Yokohama with real data set. Since the MFD represents the area-wide network traffic performances, studies on perimeter control strategies and an area traffic state estimation utilizing the MFD concept has been reported. However, limited works have been reported on real world example from signalised arterial network. This paper fuses data from multiple sources (Bluetooth, Loops and Signals) and develops a framework for the development of the MFD for Brisbane, Australia. Existence of the MFD in Brisbane arterial network is confirmed. Different MFDs (from whole network and several sub regions) are evaluated to discover the spatial partitioning in network performance representation. The findings confirmed the usefulness of appropriate network partitioning for traffic monitoring and incident detections. The discussion addressed future research directions

Graph coloring applied to secure computation in non-Abelian groups

We study the natural problem of secure n-party computation (in the computationally unbounded attack model) of circuits over an arbitrary finite non-Abelian group (G,⋅), which we call G-circuits. Besides its intrinsic interest, this problem is also motivating by a completeness result of Barrington, stating that such protocols can be applied for general secure computation of arbitrary functions. For flexibility, we are interested in protocols which only require black-box access to the group G (i.e. the only computations performed by players in the protocol are a group operation, a group inverse, or sampling a uniformly random group element). Our investigations focus on the passive adversarial model, where up to t of the n participating parties are corrupted.

Decomposition construction for secret sharing schemes with graph access structures in polynomial time

The purpose of this paper is to describe a new decomposition construction for perfect secret sharing schemes with graph access structures. The previous decomposition construction proposed by Stinson is a recursive method that uses small secret sharing schemes as building blocks in the construction of larger schemes. When the Stinson method is applied to the graph access structures, the number of such “small” schemes is typically exponential in the number of the participants, resulting in an exponential algorithm. Our method has the same flavor as the Stinson decomposition construction; however, the linear programming problem involved in the construction is formulated in such a way that the number of “small” schemes is polynomial in the size of the participants, which in turn gives rise to a polynomial time construction. We also show that if we apply the Stinson construction to the “small” schemes arising from our new construction, both have the same information rate.

Flexible process graph : a prologue

Businesses document their operational processes as process models. The common practice is to represent process models as directed graphs. The nodes of a process graph represent activities and directed edges constitute activity ordering constraints. A flexible process graph modeling approach proposes to generalize process graph structure to a hypergraph. Obtained process structure aims at formalization of ad-hoc process control flow. In this paper we discuss aspects relevant to concurrent execution of process activities in a collaborative manner organized as a flexible process graph. We provide a real world flexible process scenario to illustrate the approach.

Macroscopic fundamental diagram for Brisbane, Australia: empirical findings on network partitioning and incident detection

The Macroscopic Fundamental Diagram (MFD) relates space-mean density and flow, and the existence with dynamic features was confirmed in congested urban network in downtown Yokohama with real data set. Since the MFD represents the area-wide network traffic performances, studies on perimeter control strategies and an area traffic state estimation utilizing the MFD concept has been reported. However, limited works have been reported on real world example from signalised arterial network. This paper fuses data from multiple sources (Bluetooth, Loops and Signals) and presents a framework for the development of the MFD for Brisbane, Australia. Existence of the MFD in Brisbane arterial network is confirmed. Different MFDs (from whole network and several sub regions) are evaluated to discover the spatial partitioning for network performance representation. The findings confirmed the usefulness of appropriate network partitioning for traffic monitoring and incident detections. The discussion addressed future research directions.

Partitioning of dioxins (PCDDs/Fs) in ambient air at urban residential locations

In this work, 17-polychlorinated dibenzo-pdioxin/furan (PCDD/Fs) isomers were measured in ambient air at four urban sites in Seoul, Korea (from February to June 2009). The concentrations of their summed values RPCDD/Fs) across all four sites ranged from 1,947 (271 WHO05 TEQ) (Jong Ro) to 2,600 (349 WHO05 TEQ) fg/m3 (Yang Jae) with a mean of 2,125 ± 317) fg/m3 (292 WHO05 TEQ fg/m3). The sum values for the two isomer groups of RPCDD and RPCDF were 527 (30 WHO05 TEQ) and 1,598 (263 WHO05 TEQ) fg/m3, respectively. The concentration profile of individual species was dominated by the 2,3,4,7,8-PeCDF isomer, which contributed approximately 36 % of the RPCDD/Fs value. The observed temporal trends in PCDD/F concentrations were characterized by relative enhancement in the winter and spring. The relative contribution of different sources, when assessed by principal component analysis, is explained by the dominance of vehicular emissions along with coal (or gas) burning as the key source of ambient PCDD/Fs in the residential areas studied.

Partitioning the variation in stream fish assemblages within a spatio-temporal hierarchy

This paper describes the relative influence of: (i) landscape scale environmental and hydrological factors; (ii) local scale environmental conditions including recent flow history, and; (iii) spatial effects (proximity of sites to one another) on the spatial and temporal variation in local freshwater fish assemblages in the Mary River, south-eastern Queensland, Australia. Using canonical correspondence analysis, each of the three sets of variables explained similar amounts of variation in fish assemblages (ranging from 44 to 52%). Variation in fish assemblages was partitioned into eight unique components: pure environmental, pure spatial, pure temporal, spatially structured environmental variation, temporally structured environmental variation, spatially structured temporal variation, the combined spatial/temporal component of environmental variation and unexplained variation. The total variation explained by these components was 65%. The combined spatial/temporal/environmental component explained the largest component (30%) of the total variation in fish assemblages, whereas pure environmental (6%), temporal (9%) and spatial (2%) effects were relatively unimportant. The high degree of intercorrelation between the three different groups of explanatory variables indicates that our understanding of the importance to fish assemblages of hydrological variation (often highlighted as the major structuring force in river systems) is dependent on the environmental context in which this role is examined.

Graph theory based representation of building information models for access control applications

Building information models are increasingly being utilised for facility management of large facilities such as critical infrastructures. In such environments, it is valuable to utilise the vast amount of data contained within the building information models to improve access control administration. The use of building information models in access control scenarios can provide 3D visualisation of buildings as well as many other advantages such as automation of essential tasks including path finding, consistency detection, and accessibility verification. However, there is no mathematical model for building information models that can be used to describe and compute these functions. In this paper, we show how graph theory can be utilised as a representation language of building information models and the proposed security related functions. This graph-theoretic representation allows for mathematically representing building information models and performing computations using these functions.

Split leverage : attacking the confidentiality of linked databases by partitioning

This article considers the risk of disclosure in linked databases when statistical analysis of micro-data is permitted. The risk of disclosure needs to be balanced against the utility of the linked data. The current work specifically considers the disclosure risks in permitting regression analysis to be performed on linked data. A new attack based on partitioning of the database is presented.

A communication model and partitioning algorithm for streaming applications for an embedded MPSoC

Energy efficient embedded computing enables new application scenarios in mobile devices like software-defined radio and video processing. The hierarchical multiprocessor considered in this work may contain dozens or hundreds of resource efficient VLIW CPUs. Programming this number of CPU cores is a complex task requiring compiler support. The stream programming paradigm provides beneficial properties that help to support automatic partitioning. This work describes a compiler for streaming applications targeting the self-build hierarchical CoreVA-MPSoC multiprocessor platform. The compiler is supported by a programming model that is tailored to fit the streaming programming paradigm. We present a novel simulated-annealing (SA) based partitioning algorithm, called Smart SA. The overall speedup of Smart SA is 12.84 for an MPSoC with 16 CPU cores compared to a single CPU implementation. Comparison with a state of the art partitioning algorithm shows an average performance improvement of 34.07%.

A subexponential construction of graph coloring for multiparty computation

We show the first deterministic construction of an unconditionally secure multiparty computation (MPC) protocol in the passive adversarial model over black-box non-Abelian groups which is both optimal (secure against an adversary who possesses any tgraphs. More specifically, following the result of Desmedt et al. (2012) that the problem of MPC over non-Abelian groups can be reduced to finding a t-reliable n-coloring of planar graphs, we show the construction of such a graph which allows a path from the input nodes to the output nodes when any t-party subset is in the possession of the adversary. Unlike the deterministic constructions from Desmedt et al. (2012) our construction has subexponential complexity and is optimal at the same time, i.e., it is secure for any t

Test-retest reliability of graph theory measures of structural brain connectivity

The human connectome has recently become a popular research topic in neuroscience, and many new algorithms have been applied to analyze brain networks. In particular, network topology measures from graph theory have been adapted to analyze network efficiency and 'small-world' properties. While there has been a surge in the number of papers examining connectivity through graph theory, questions remain about its test-retest reliability (TRT). In particular, the reproducibility of structural connectivity measures has not been assessed. We examined the TRT of global connectivity measures generated from graph theory analyses of 17 young adults who underwent two high-angular resolution diffusion (HARDI) scans approximately 3 months apart. Of the measures assessed, modularity had the highest TRT, and it was stable across a range of sparsities (a thresholding parameter used to define which network edges are retained). These reliability measures underline the need to develop network descriptors that are robust to acquisition parameters.