Brief announcement: Maintaining large dense subgraphs on dynamic networks

In distributed networks, some groups of nodes may have more inter-connections, perhaps due to their larger bandwidth availability or communication requirements. In many scenarios, it may be useful for the nodes to know if they form part of a dense subgraph, e.g., such a dense subgraph could form a high bandwidth backbone for the network. In this work, we address the problem of self-awareness of nodes in a dynamic network with regards to graph density, i.e., we give distributed algorithms for maintaining dense subgraphs (subgraphs that the member nodes are aware of). The only knowledge that the nodes need is that of the dynamic diameter D, i.e., the maximum number of rounds it takes for a message to traverse the dynamic network. For our work, we consider a model where the number of nodes are fixed, but a powerful adversary can add or remove a limited number of edges from the network at each time step. The communication is by broadcast only and follows the CONGEST model in the sense that only messages of O(log n) size are permitted, where n is the number of nodes in the network. Our algorithms are continuously executed on the network, and at any time (after some initialization) each node will be aware if it is part (or not) of a particular dense subgraph. We give algorithms that approximate both the densest subgraph, i.e., the subgraph of the highest density in the network, and the at-least-k-densest subgraph (for a given parameter k), i.e., the densest subgraph of size at least k. We give a (2 + e)-approximation algorithm for the densest subgraph problem. The at-least-k-densest subgraph is known to be NP-hard for the general case in the centralized setting and the best known algorithm gives a 2-approximation. We present an algorithm that maintains a (3+e)-approximation in our distributed, dynamic setting. Our algorithms run in O(Dlog n) time. © 2012 Authors.

Channel Time Allocation PSO for Gigabit Multimedia Wireless Networks

This article introduces a resource allocation solution capable of handling mixed media applications within the constraints of a 60 GHz wireless network. The challenges of multimedia wireless transmission include high bandwidth requirements, delay intolerance and wireless channel availability. A new Channel Time Allocation Particle Swarm Optimization (CTA-PSO) is proposed to solve the network utility maximization (NUM) resource allocation problem. CTA-PSO optimizes the time allocated to each device in the network in order to maximize the Quality of Service (QoS) experienced by each user. CTA-PSO introduces network-linked swarm size, an increased diversity function and a learning method based on the personal best, Pbest, results of the swarm. These additional developments to the PSO produce improved convergence speed with respect to Adaptive PSO while maintaining the QoS improvement of the NUM. Specifically, CTA-PSO supports applications described by both convex and non-convex utility functions. The multimedia resource allocation solution presented in this article provides a practical solution for real-time wireless networks.

Multiuser Cognitive Relay Networks in the Presence of Direct Links

In this paper, we investigate a multiuser cognitive relay network with direct source-destination links and multiple primary destinations. In this network, multiple secondary users compete to communicate with a secondary destination assisted by an amplify-and-forward (AF) relay. We take into account the availability of direct links from the secondary users to the primary and secondary destinations. For the considered system, we select one best secondary user to maximize the received signal-to-noise ratio (SNR) at the secondary destination. We first derive an accurate lower bound of the outage probability, and then provide an asymptotic expression of outage probability in high SNR region. From the lower bound and the asymptotic expressions, we obtain several insights into the system design. Numerical and simulation results are finally demonstrated to verify the proposed studies.

Two-Way Relaying Networks with Wireless Power Transfer: Policies Design and Throughput Analysis

This paper exploits an amplify-and-forward (AF) two-way relaying network (TWRN), where an energy constrained relay node harvests energy with wireless power transfer. Two bidirectional protocols, multiple access broadcast (MABC) protocol and time division broadcast (TDBC) protocol, are considered. Three wireless power transfer policies, namely, 1) dual-source (DS) power transfer; 2) single-fixed-source (SFS) power transfer; and 3) single-best-source (SBS) power transfer are proposed and well-designed based on time switching receiver architecture. We derive analytical expressions to determine the throughput both for delay-limited transmission and delay-tolerant transmission. Numerical results corroborate our analysis and show that MABC protocol achieves a higher throughput than TDBC protocol. An important observation is that SBS policy offers a good tradeoff between throughput and power.

Secure Multiuser Multiple Amplify-and-Forward Relay Networks in Presence of Multiple Eavesdroppers

In this paper, we study the information-theoretical security of a downlink multiuser cooperative relaying network with multiple intermediate amplify-and-forward (AF) relays, where there exist multiple eavesdroppers which can overhear the message. To prevent the wiretap and strength the network security, we select one best relay and user pair, so that the selected user can receive the message from the base station assisted by the selected relay. The relay and user selection is performed by maximizing the ratio of the received signal-to-noise ratio (SNR) at the user to the eavesdroppers, which is based on both the main and eavesdropper links. For the considered system, we derive the closed-form expression of the secrecy outage probability, and provide the asymptotic expression in high main-to-eavesdropper ratio (MER) region. From the asymptotic analysis, we can find that the system diversity order is equivalent to the number of relays regardless of the number of users and eavesdroppers.

Secure Multiuser Communications in Multiple Amplify-and-Forward Relay Networks

This paper proposes relay selection in order to increase the physical layer security in multiuser cooperative relay networks with multiple amplify-and-forward (AF) relays, in the presence of multiple eavesdroppers. To strengthen the network security against eavesdropping attack, we present three criteria to select the best relay and user pair. Specifically, criterion I and II study the received signal-to-noise ratio (SNR) at the receivers, and perform the selection by maximizing the SNR ratio of the user to the eavesdroppers. To this end, criterion I relies on both the main and eavesdropper links, while criterion II relies on the main links only. Criterion III is the standard max-min selection criterion,
which maximizes the minimum of the dual-hop channel gains of main links. For the three selection criteria, we examine the system secrecy performance by deriving the analytical expressions for the secrecy outage probability. We also derive the asymptotic analysis for the secrecy outage probability with high main-to eavesdropper ratio (MER). From the asymptotic analysis, an interesting observation is reached: for each criterion, the system diversity order is equivalent to the number of relays regardless of the number of users and eavesdroppers.

Interference Investigation for Cognitive Spectrum Sharing Networks with Reactive DF Relay Selection

Cognitive radio (CR) with spectrum-sharing has been envisioned as emerging technology for the next generation of mobile and wireless networks by allowing the unlicensed customers simultaneously utilize the licensed radio frequency spectrums. However, the CR has faced some practical challenges due to its deduced system performance as compared to non spectrum-sharing counterpart. In this paper, we therefore consider the potential of incorporating the cooperative communications into CR by introducing the concept of reactive multiple decode-and-forward (DF) relays. In particular, we derive new results for exact and asymptotic expressions for the performance of cognitive relay networks with K-th best relay selection. Our novel results have exhibited the significance of using relay networks to enhance the system performance of CR.

Connectivity and Physical Activity: Using Footpath Networks to Measure the Walkability of Built Environments

There is now a strong body of research that suggests that the form of the built environment can influence levels of physical activity, leading to an increasing interest in incorporating health objectives into spatial planning and regeneration policies and projects. There have been a number of strands to this research, one of which has sought to develop “objective” measurements of the built environment using Geographic Information Science (GIS) involving measures of connectivity and proximity to compare the relative “walkability” of different neighbourhoods. The development of the “walkability index” (e.g. Leslie et al 2007, Frank et al 2010) has become a popular indicator of spatial distribution of those features of the built environment that are considered to have the greatest positive influence on levels of physical activity. The success of this measure is built on its ability to succinctly capture built environment correlates of physical activity using routinely available spatial data, which includes using road centre lines as a basis of a proxy for connectivity.

This paper discusses two key aspects of the walkability index. First, it follows the suggestion of Chin et al (2008) that the use of a footpath network (where available), rather than road centre lines, may be far more effective in evaluating walkability. This may be particularly important for assessing changes in walkability arising from pedestrian-focused infrastructure projects, such as greenways. Second, the paper explores the implication of this for how connectivity can be measured. The paper takes six different measures of connectivity and first analyses the relationships between them and then tests their correlation with actual levels of physical activity of local residents in Belfast, Northern Ireland. The analysis finds that the best measurements appear to be intersection density and metric reach and uses this finding to discuss the implications of this for developing tools that may better support decision-making in spatial planning.

Secure D2D Communication in Large-Scale Cognitive Cellular Networks with Wireless Power Transfer

In this paper, we investigate secure device-to-device (D2D) communication in energy harvesting large-scale cognitive cellular networks. The energy constrained D2D transmitter harvests energy from multi-antenna equipped power beacons (PBs), and communicates with the corresponding receiver using the spectrum of the cellular base stations (BSs). We introduce a power transfer model and an information signal model to enable wireless energy harvesting and secure information transmission. In the power transfer model, we propose a new power transfer policy, namely, best power beacon (BPB) power transfer. To characterize the power transfer reliability of the proposed policy, we derive new closed-form expressions for the exact power outage probability and the asymptotic power outage probability with large antenna arrays at PBs. In the information signal model, we present a new comparative framework with two receiver selection schemes: 1) best receiver selection (BRS), and 2) nearest receiver selection (NRS). To assess the secrecy performance, we derive new expressions for the secrecy throughput considering the two receiver selection schemes using the BPB power transfer policies. We show that secrecy performance improves with increasing densities of PBs and D2D receivers because of a larger multiuser diversity gain. A pivotal conclusion is reached that BRS achieves better secrecy performance than NRS but demands more instantaneous feedback and overhead.

Generalized Selection Combining for Cognitive Relay Networks over Nakagami-m Fading

We consider transmit antenna selection with receive generalized selection combining (TAS/GSC) for cognitive decodeand-forward (DF) relaying in Nakagami-m fading channels. In an effort to assess the performance, the probability density function and the cumulative distribution function of the endto-end SNR are derived using the moment generating function, from which new exact closed-form expressions for the outage probability and the symbol error rate are derived. We then derive a new closed-form expression for the ergodic capacity. More importantly, by deriving the asymptotic expressions for the outage probability and the symbol error rate, as well as the high SNR approximations of the ergodic capacity, we establish new design insights under the two distinct constraint scenarios: 1) proportional interference power constraint, and 2) fixed interference power constraint. Several pivotal conclusions are reached. For the first scenario, the full diversity order of the
outage probability and the symbol error rate is achieved, and the high SNR slope of the ergodic capacity is 1/2. For the second scenario, the diversity order of the outage probability and the symbol error rate is zero with error floors, and the high SNR slope of the ergodic capacity is zero with capacity ceiling.

Advances in Learning Bayesian Networks of Bounded Treewidth

This work presents novel algorithms for learning Bayesian networks of bounded treewidth. Both exact and approximate methods are developed. The exact method combines mixed integer linear programming formulations for structure learning and treewidth computation. The approximate method consists in sampling k-trees (maximal graphs of treewidth k), and subsequently selecting, exactly or approximately, the best structure whose moral graph is a subgraph of that k-tree. The approaches are empirically compared to each other and to state-of-the-art methods on a collection of public data sets with up to 100 variables.

Complexity of Inferences in Polytree-shaped Semi-Qualitative Probabilistic Networks

Semi-qualitative probabilistic networks (SQPNs) merge two important graphical model formalisms: Bayesian networks and qualitative probabilistic networks. They provide a very general modeling framework by allowing the combination of numeric and qualitative assessments over a discrete domain, and can be compactly encoded by exploiting the same factorization of joint probability distributions that are behind the Bayesian networks. This paper explores the computational complexity of semi-qualitative probabilistic networks, and takes the polytree-shaped networks as its main target. We show that the inference problem is coNP-Complete for binary polytrees with multiple observed nodes. We also show that inferences can be performed in linear time if there is a single observed node, which is a relevant practical case. Because our proof is constructive, we obtain an efficient linear time algorithm for SQPNs under such assumptions. To the best of our knowledge, this is the first exact polynomial-time algorithm for SQPNs. Together these results provide a clear picture of the inferential complexity in polytree-shaped SQPNs.

Autism and ABA: Best Practice in America and the Way Forward for Europe.

According to recent estimates, 1 in each 68 new-borns will be diagnosed with an Autism Spectrum Disorder (ASD) in the USA (Centers for Disease Control and Prevention, 2014), while 1 in every 29 children will be diagnosed with ASD in the UK (Dillenburger, Jordan, McKerr, & Keenan, 2015). Individuals diagnosed with ASD share a set of characteristics at varying levels of severity: impairments in social communication skills and presence of restricted interests and repetitive behaviours (American Psychiatric Association, 2013).Notwithstanding these figures, little effort has been placed in European countries’ policies for reaching an early diagnosis. This has a detrimental effect on future prognosis for children with ASD, since research has clearly shown that when evidence-based interventions are accessed early in life, they can lead to great improvements on the overall functioning of children with ASD, including significant gains in social communication and reduction of inappropriate behaviours (Dawson, Rogers, Munson, Smith, Winter, Greenson, Donaldson, & Varley, 2009).Additionally, when looking at the services available for children with ASD and their families in Europe, it seems that not much improvement has been made in the last decades. Traditional eclectic approaches and a wealth of non-scientific methods seem to be available and often recommended by public bodies, while state-funded evidence-based interventions are not offered as part of the education or health system. Given that there is a wealth of evidence on the effectiveness of interventions based on the science of ABA, it seems that specific action is required to correct the situation, respecting children’s right to effective treatment and inclusion.In the present paper, these issues are fully discussed and recommendations for best practice are offered.

Best friends and better coping: Facilitating psychological resilience through boys’ and girls’ closest friendships

This is a novel investigation of whether, and how, a single close supportive friendship may facilitate psychological resilience in socio-economically vulnerable British adolescents. A total of 409 adolescents (160 boys, 245 girls, four unknown), aged between 11 and 19 years, completed self-report measures of close friendship quality, psychological resilience, social support, and other resources. Findings revealed a significant positive association between perceived friendship quality and resilience. This relationship was facilitated through inter-related mechanisms of developing a constructive coping style (comprised of support-seeking and active coping), effort, a supportive friendship network, and reduced disengaged and externalising coping. While protective processes were encouragingly significantly present across genders, boys were more vulnerable to the deleterious effects of disengaged and externalizing coping than girls. We suggest that individual close friendships are an important potential protective mechanism accessible to most adolescents. We discuss implications of the resulting Adolescent Friendship and Resilience Model for resilience theories and integration into practice.