Analyzing the effectiveness of graph metrics for anomaly detection in online social networks

Online social networks can be modelled as graphs; in this paper, we analyze the use of graph metrics for identifying users with anomalous relationships to other users. A framework is proposed for analyzing the effectiveness of various graph theoretic properties such as the number of neighbouring nodes and edges, betweenness centrality, and community cohesiveness in detecting anomalous users. Experimental results on real-world data collected from online social networks show that the majority of users typically have friends who are friends themselves, whereas anomalous users’ graphs typically do not follow this common rule. Empirical analysis also shows that the relationship between average betweenness centrality and edges identifies anomalies more accurately than other approaches.

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.

Reconnection : a contemporary development in cultural landscape theory contributing to rehabilitation strategies for Australian open-cut coal mining landscapes

A value-shift began to influence global political thinking in the late 20th century, characterised by recognition of the need for environmentally, socially and culturally sustainable resource development. This shift entailed a move away from thinking of ‘nature’ and ‘culture’ as separate entities – the former existing to serve the latter – toward the possibility of embracing the intrinsic worth of the nonhuman world. Cultural landscape theory recognises ‘nature’ as at once both ‘natural’, and a ‘cultural’ construct. As such, it may offer a framework through which to progress in the quest for ‘sustainable development’. This study makes a contribution to this quest by asking whether contemporary developments in cultural landscape theory can contribute to rehabilitation strategies for Australian open-cut coal mining landscapes. The answer is ‘yes’. To answer the research question, a flexible, ‘emergent’ methodological approach has been used, resulting in the following outcomes. A thematic historical overview of landscape values and resource development in Australia post-1788, and a review of cultural landscape theory literature, contribute to the formation of a new theoretical framework: Reconnecting the Interrupted Landscape. This framework establishes a positive answer to the research question. It also suggests a method of application within the Australian open-cut coal mining landscape, a highly visible exemplar of the resource development landscape. This method is speculatively tested against the rehabilitation strategy of an operating open-cut coal mine, concluding with positive recommendations to the industry, and to government.

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 dynamic approach for evaluating earthwork hauls in construction

A graph theoretic approach is developed for accurately computing haulage costs in earthwork projects. This is vital as haulage is a predominant factor in the real cost of earthworks. A variety of metrics can be used in our approach, but a fuel consumption proxy is recommended. This approach is novel as it considers the constantly changing terrain that results from cutting and filling activities and replaces inaccurate “static” calculations that have been used previously. The approach is also capable of efficiently correcting the violation of top down cutting and bottom up filling conditions that can be found in existing earthwork assignments and sequences. This approach assumes that the project site is partitioned into uniform blocks. A directed graph is then utilised to describe the terrain surface. This digraph is altered after each cut and fill, in order to reflect the true state of the terrain. A shortest path algorithm is successively applied to calculate the cost of each haul and these costs are summed to provide a total cost of haulage

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.

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.

Why 'down under' is a cut above: a comparison of rates of and reasons for caesarean section in England and Australia

Background Most studies examining determinants of rising rates of caesarean section have examined patterns in documented reasons for caesarean over time in a single location. Further insights could be gleaned from cross-cultural research that examines practice patterns in locations with disparate rates of caesarean section at a single time point. Methods We compared both rates of and main reason for pre-labour and intrapartum caesarean between England and Queensland, Australia, using data from retrospective cross-sectional surveys of women who had recently given birth in England (n = 5,250) and Queensland (n = 3,467). Results Women in Queensland were more likely to have had a caesarean birth (36.2%) than women in England (25.1% of births; OR = 1.44, 95% CI = 1.28-1.61), after adjustment for obstetric characteristics. Between-country differences were found for rates of pre-labour caesarean (21.2% vs. 12.2%) but not for intrapartum caesarean or assisted vaginal birth. Compared to women in England, women in Queensland with a history of caesarean were more likely to have had a pre-labour caesarean and more likely to have had an intrapartum caesarean, due only to a previous caesarean. Among women with no previous caesarean, Queensland women were more likely than women in England to have had a caesarean due to suspected disproportion and failure to progress in labour. Conclusions The higher rates of caesarean birth in Queensland are largely attributable to higher rates of caesarean for women with a previous caesarean, and for the main reason of having had a previous caesarean. Variation between countries may be accounted for by the absence of a single, comprehensive clinical guideline for caesarean section in Queensland. Keywords: Caesarean section; Childbirth; Pregnancy; Cross-cultural comparison; Vaginal birth after caesarean; Previous caesarean section; Patient-reported data; Quality improvement

Comparison of intensity-based cut-points for the RT3 accelerometer in youth

OBJECTIVES: To compare the classification accuracy of previously published RT3 accelerometer cut-points for youth using energy expenditure, measured via portable indirect calorimetry, as a criterion measure. DESIGN: Cross-sectional cross-validation study. METHODS: 100 children (mean age 11.2±2.8 years, 61% male) completed 12 standardized activities trials (3 sedentary, 5 lifestyle and 4 ambulatory) while wearing an RT3 accelerometer. V˙O2 was measured concurrently using the Oxycon Mobile portable calorimeter. Cut-points by Vanhelst (VH), Rowlands (RW), Chu (CH), Kavouras (KV) and the RT3 manufacturer (RT3M) were used to classify PA intensity as sedentary (SED), light (LPA), moderate (MPA) or vigorous (VPA). Classification accuracy was evaluated using the area under the Receiver Operating Characteristic curve (ROC-AUC) and weighted Kappa (κ). RESULTS: For moderate-to-vigorous PA (MVPA), VH, KV and RW exhibited excellent accuracy classification (ROC-AUC≥0.90), while the CH and RT3M exhibited good classification accuracy (ROC-AUC>0.80). Classification accuracy for LPA was fair to poor (ROC-AUC<0.76). For SED, VH exhibited excellent classification accuracy (ROC-AUC>0.90), while RW, CH, and RT3M exhibited good classification accuracy (ROC-AUC>0.80). Kappa statistics ranged from 0.67 (VH) to 0.55 (CH). CONCLUSIONS: All cut-points provided acceptable classification accuracy for SED and MVPA, but limited accuracy for LPA. On the basis of classification accuracy over all four levels of intensity, the use of the VH cut-points is recommended.

Identification and Validity of Accelerometer Cut-Points for Toddlers

The purpose of this study was to derive ActiGraph cut-points for sedentary (SED), light-intensity physical activity (LPA), and moderate-to-vigorous physical activity (MVPA) in toddlers and evaluate their validity in an independent sample. The predictive validity of established preschool cut-points were also evaluated and compared. Twenty-two toddlers (mean age = 2.1 years ± 0.4 years) wore an ActiGraph accelerometer during a videotaped 20-min play period. Videos were subsequently coded for physical activity (PA) intensity using the modified Children's Activity Rating Scale (CARS). Receiver operating characteristic (ROC) curve analyses were conducted to determine cut-points. Predictive validity was assessed in an independent sample of 18 toddlers (mean age = 2.3 ± 0.4 years). From the ROC curve analyses, the 15-s count ranges corresponding to SED, LPA, and MVPA were 0–48, 49–418, and >418 counts/15 s, respectively. Classification accuracy was fair for the SED threshold (ROC-AUC = 0.74, 95% confidence interval = 0.71–0.76) and excellent for MVPA threshold (ROC-AUC = 0.90, 95% confidence interval = 0.88–0.92). In the cross-validation sample, the toddler cut-point and established preschool cut-points significantly overestimated time spent in SED and underestimated time in spent in LPA. For MVPA, mean differences between observed and predicted values for the toddler and Pate cut-points were not significantly different from zero. In summary, the ActiGraph accelerometer can provide useful group-level estimates of MVPA in toddlers. The results support the use of the Pate cut-point of 420 counts/15 s for MVPA.

Comparison of accelerometer cut points for predicting activity intensity in youth

The absence of comparative validity studies has prevented researchers from reaching consensus regarding the application of intensity-related accelerometer cut points for children and adolescents. PURPOSE This study aimed to evaluate the classification accuracy of five sets of independently developed ActiGraph cut points using energy expenditure, measured by indirect calorimetry, as a criterion reference standard. METHODS A total of 206 participants between the ages of 5 and 15 yr completed 12 standardized activity trials. Trials consisted of sedentary activities (lying down, writing, computer game), lifestyle activities (sweeping, laundry, throw and catch, aerobics, basketball), and ambulatory activities (comfortable walk, brisk walk, brisk treadmill walk, running). During each trial, participants wore an ActiGraph GT1M, and VO 2 was measured breath-by-breath using the Oxycon Mobile portable metabolic system. Physical activity intensity was estimated using five independently developed cut points: Freedson/Trost (FT), Puyau (PU), Treuth (TR), Mattocks (MT), and Evenson (EV). Classification accuracy was evaluated via weighted κ statistics and area under the receiver operating characteristic curve (ROC-AUC). RESULTS Across all four intensity levels, the EV (κ = 0.68) and FT (κ = 0.66) cut points exhibited significantly better agreement than TR (κ = 0.62), MT (κ = 0.54), and PU (κ = 0.36). The EV and FT cut points exhibited significantly better classification accuracy for moderate-to vigorous-intensity physical activity (ROC-AUC = 0.90) than TR, PU, or MT cut points (ROC-AUC = 0.77-0.85). Only the EV cut points provided acceptable classification accuracy for all four levels of physical activity intensity and performed well among children of all ages. The widely applied sedentary cut point of 100 counts per minute exhibited excellent classification accuracy (ROC-AUC = 0.90). CONCLUSIONS On the basis of these findings, we recommend that researchers use the EV ActiGraph cut points to estimate time spent in sedentary, light-, moderate-, and vigorous-intensity activity in children and adolescents. Copyright © 2011 by the American College of Sports Medicine.

Calibration and comparison of accelerometer cut points in preschool children

Objective The present study aimed to develop accelerometer cut points to classify physical activities (PA) by intensity in preschoolers and to investigate discrepancies in PA levels when applying various accelerometer cut points. Methods To calibrate the accelerometer, 18 preschoolers (5.8 +/- 0.4 years) performed eleven structured activities and one free play session while wearing a GT1M ActiGraph accelerometer using 15 s epochs. The structured activities were chosen based on the direct observation system Children's Activity Rating Scale (CARS) while the criterion measure of PA intensity during free play was provided using a second-by-second observation protocol (modified CARS). Receiver Operating Characteristic (ROC) curve analyses were used to determine the accelerometer cut points. To examine the classification differences, accelerometer data of four consecutive days from 114 preschoolers (5.5 +/- 0.3 years) were classified by intensity according to previously published and the newly developed accelerometer cut points. Differences in predicted PA levels were evaluated using repeated measures ANOVA and Chi Square test. Results Cut points were identified at 373 counts/15 s for light (sensitivity: 86%; specificity: 91%; Area under ROC curve: 0.95), 585 counts/15 s for moderate (87%; 82%; 0.91) and 881 counts/15 s for vigorous PA (88%; 91%; 0.94). Further, applying various accelerometer cut points to the same data resulted in statistically and biologically significant differences in PA. Conclusions Accelerometer cut points were developed with good discriminatory power for differentiating between PA levels in preschoolers and the choice of accelerometer cut points can result in large discrepancies.

Why we should not cut P.E.

Thinking of cutting physical education? Think again. Even as we bemoan children's sedentary lifestyles, we often sacrifice school-based physical education in the name of providing more time for academics. In 2006, only 3.8 percent of elementary schools, 7.9 percent of middle schools, and 2.1 percent of high schools offered students daily physical education or its equivalent for the entire school year (Lee, Burgeson, Fulton, & Spain, 2007). We believe this marked reduction in school-based physical activity risks students' health and can't be justified on educational or ethical grounds. We'll get to the educational grounds in a moment. As to ethical reasons for keeping physical activity part of our young people's school days, consider the fact that childhood obesity is now one of the most serious health issues facing U.S. children (Ogden et al., 2006). School-based physical education programs engage students in regular physical activity and help them acquire skills and habits necessary to pursue an active lifestyle. Such programs are directly relevant to preventing obesity. Yet they are increasingly on the chopping block.