Search

One of the main steps in the data lifecycle is to publish it for data analysts to discover hidden patterns. But, data publishing may lead to unwanted disclosure of personal information and cause privacy problems. Data anonymization techniques preserve privacy models to prevent the disclosure of individuals’ private information in published data. In this paper, a distributed in-memory method is proposed on the Apache Spark framework to preserve the l-diversity privacy model. This method anonymizes large-scale data in a three-phase process, which includes, seed selection, data clustering for $$\ell$$ -diversity, and finalizing phase. In this method, a hierarchical kmeans-based data clustering algorithm has been designed for data anonymization. One of the major challenges of anonymization methods is to establish a better trade-off between data utility and privacy. Therefore, for calculating the distance between records and forming more cohesive ldiverse-clusters, the authors have designed two Manhattan-based and Euclidean-based distance functions to satisfy the requirements of the l-diversity model. Given the 100-fold speed of the Spark compared to MapReduce, the proposed method is presented using in-memory RDD programming in Apache Spark, to address the runtime, scalability, and performance in large-scale data anonymization as it exists in the previous MapReduce-based algorithms. Our method provides general knowledge to use parallel in-memory computation of Spark in big data anonymization. In experiments, this method has obtained lower information loss and loses about 1% to 2% accuracy and FMeasure criteria; therefore, it establishes a better trade-off than the state-of-the-art MapReduce-based Mondrian methods

Mobile devices collect a large amount of visual data that are useful for many applications. Searching for an object of interest over a network of mobile devices can aid human analysts in a variety of situations. However, processing the information on these devices is a challenge owing to the high computational complexity of the state-of-the-art computer vision algorithms that primarily rely on Convolutional Neural Networks (CNNs). Thus, this paper builds PicSys, a system that enables answering visual search queries on a mobile network. The objective of the system is to minimize the maximum completion time over all devices while taking into account the energy consumption of mobile devices as well. First, PicSys carefully divides the computation into multiple filtering stages, such that only a small percentage of images need to run the entire CNN pipeline. Splitting such CNN computation into multiple stages requires understanding the intermediate CNN features and systematically trading off accuracy for the computation speed. Second, PicSys determines where to run each of the stages of the multi-stage pipeline to fully utilize the available resources. Finally, through extensive experimentation, system implementation, and simulation, we show that PicSys performance is close to optimal and significantly outperforms other standard algorithms.

Mobile edge computing provides the opportunity for wireless users to exploit the power of cloud computing without a large communication delay. To serve data-intensive applications (e.g., video analytics, machine learning tasks) from the edge, we need, in addition to computation resources, storage resources for storing server code and data as well as network bandwidth for receiving user-provided data. Moreover, due to time-varying demands, the code and data placement needs to be adjusted over time, which raises concerns of system stability and operation cost. In this paper, we address these issues by proposing a two-time-scale framework that jointly optimizes service (code and data) placement and request scheduling, while considering storage, communication, computation, and budget constraints. First, by analyzing the hardness of various cases, we completely characterize the complexity of our problem. Next, we develop a polynomial-time service placement algorithm by formulating our problem as a set function optimization, which attains a constant-factor approximation under certain conditions. Furthermore, we develop a polynomial-time request scheduling algorithm by computing the maximum flow in a carefully constructed auxiliary graph, which satisfies hard resource constraints and is provably optimal in the special case where requests have homogeneous resource demands. Extensive synthetic and trace-driven simulations show that the proposed algorithms achieve 90% of the optimal performance.

Cascading phenomena have been studied extensively in various networks. Particularly, it has been shown that the community structures in networks impact their cascade processes. However, the role of community structures in cascading failures in power grids have not been studied heretofore. In this paper, cascading failures in power grids are studied using interaction graphs. Key evidence has been provided that the community structures in interaction graphs bear critical information about the cascade process and the role of system components in cascading failures in power grids. Furthermore, a centrality measure based on the community structures is proposed to identify critical components of the system, which their protection can help in containing failures within a community and prevent the propagation of failures to large sections of the power grid. Various criticality evaluation techniques, including data driven, epidemic simulation based, power system simulation based, and graph based, have been used to verify the importance of the identified critical components in the cascade process and compare them with those identified by traditional centrality measures. Moreover, it has been shown that the loading level of the power grid impacts the interaction graph and consequently, the community structure and criticality of the components in the cascade process.

Boolean network tomography is a powerful tool to infer the state (working/failed) of individual nodes from path-level measurements obtained by edge-nodes. We consider the problem of optimizing the capability of identifying network failures through the design of monitoring schemes. Finding an optimal solution is NP-hard and a large body of work has been devoted to heuristic approaches providing lower bounds. Unlike previous works, we provide upper bounds on the maximum number of identifiable nodes, given the number of monitoring paths and different constraints on the network topology, the routing scheme, and the maximum path length. These upper bounds represent a fundamental limit on identifiability of failures via Boolean network tomography. Our analysis provides insights on how to design topologies and related monitoring schemes to achieve the maximum identifiability under various network settings. Through analysis and experiments we demonstrate the tightness of the bounds and efficacy of the design insights for engineered as well as real networks.

Influence spread in multi-layer interdependent networks (M-IDN) has been studied in the last few years; however, prior works mostly focused on the spread that is initiated in a single layer of an M-IDN. In real world scenarios, influence spread can happen concurrently among many or all components making up the topology of an M-IDN. This paper investigates the effectiveness of different influence spread strategies in M-IDNs by providing a comprehensive analysis of the time evolution of influence propagation given different initial spreader strategies. For this study we consider a two-layer interdependent network and a general probabilistic threshold influence spread model to evaluate the evolution of influence spread over time. For a given coupling scenario, we tested multiple interdependent topologies, composed of layers A and B, against four cases of initial spreader selection: (1) random initial spreaders in A, (2) random initial spreaders in both A and B, (3) targeted initial spreaders using degree centrality in A, and (4) targeted initial spreaders using degree centrality in both A and B. Our results indicate that the effectiveness of influence spread highly depends on network topologies, the way they are coupled, and our knowledge of the network structure — thus an initial spread starting in only A can be as effective as initial spread starting in both A and B concurrently. Similarly, random initial spread in multiple layers of an interdependent system can be more severe than a comparable initial spread in a single layer. Our results can be easily extended to different types of event propagation in multi-layer interdependent networks such as information/misinformation propagation in online social networks, disease propagation in offline social networks, and failure/attack propagation in cyber-physical systems.

The interdependence of multiple networks makes today's infrastructures more vulnerable to failures. Prior works mainly focused on robust network design and recovery strategies after failures, given complete knowledge of failure location. Nevertheless, in real-world scenarios, the location of failures might be unknown or only partially known. In this paper, we focus on cascading failures involving the power grid and its communication network with imprecision in failure assessment. We consider a model where functionality of the power grid and its failure assessment rely on the operation of a monitoring system and vice versa. We address ongoing cascading failures with a twofold approach: first, once a cascading failure is detected, we limit further propagation by redispatching generation and shedding loads; and second, we formulate a recovery plan to maximize the total amount of load served during the recovery intervention. We performed extensive simulations on real network topologies showing the effectiveness of the proposed approach in terms of number of disrupted power lines and total served load.

Network recovery after large-scale failures has tremendous cost implications. While numerous approaches have been proposed to restore critical services after large-scale failures, they mostly assume having full knowledge of failure location, which cannot be achieved in real failure scenarios. Making restoration decisions under uncertainty is often further complicated in a large-scale failure. This paper addresses progressive network recovery under the uncertain knowledge of damages. We formulate the problem as a mixed integer linear programming and show that it is NP-hard. We propose an iterative stochastic recovery algorithm (ISR) to recover the network in a progressive manner to satisfy the critical services. At each optimization step, we make a decision to repair a part of the network and gather more information iteratively, until critical services are completely restored. We propose three different approaches: 1) an iterative shortest path algorithm; 2) an approximate branch and bound (ISR-BB); and 3) an iterative multicommodity LP relaxation (ISR-MULT). Further, we compared our approach with the state-of-the-art centrality-based damage assessment and recovery (CeDAR) and iterative split and prune (ISP) algorithms. Our results show that ISR-BB and ISR-MULT outperform the state-of-the-art ISP and CeDAR algorithms while we can configure our choice of tradeoff between the execution time, the number of repairs (cost), and the demand loss. We show that our recovery algorithm, on average, can reduce the total number of repairs by a factor of about 3 with respect to ISP, while satisfying all critical demands.

Most of today's critical infrastructure are in the form of interdependent networks with new vulnerabilities attributed to their interdependencies. Security and reliability attacks, which can trigger failures within and across these networks, will have different forms and impacts on interdependent networks. In this paper, we focus on random attacks in a twolayer interdependent network and quantify its vulnerability under two different types of such attacks: 1) single layer attack, 2) concurrent two-layer attack. We compare the vulnerability of the network given the two attack scenarios, to answer the question of whether one single attack in one layer of an interdependent network can be as severe as concurrent multi-layer attack? We define two quantitative metrics to evaluate the vulnerability of the interdependent network under a given attack, namely, long-term effect and critical times. The long-term effect represents the total number of affected nodes during a finite time window, while critical times capture the evolution of failure propagation over time. The impact of different types of network topologies, including Erdos-Renyi, Scale-Free, and Small-World, and different coupling scenarios between the layers, namely high and low intensity and random and designed coupling on the vulnerability of the network is studied. Our results show that two-layer attacks are more severe in most cases while a single attack in one layer can be more severe for certain scenarios of coupling and network topologies. This suggests that in interdependent networks severe attacks can be triggered using access to only one layer of the network if the network structure is vulnerable.

Offloading tasks to the edge or the Cloud has the potential to improve accuracy of classification and detection tasks as more powerful hardware and machine learning models can be used. The downside is the added delay introduced for sending the data to the Edge/Cloud. In delay-sensitive applications, it is usually necessary to strike a balance between accuracy and latency. However, the state of the art typically considers offloading all-or-nothing decisions, e.g., process locally or send all available data to the Edge (Cloud). Our goal is to expand the options in the accuracy-latency trade-off by allowing the source to send a fraction of the total data for processing. We evaluate the performance of image classifiers when faced with images that have been purposely reduced in quality in order to reduce traffic costs. Using three common models (SqueezeNet, GoogleNet, ResNet) and two data sets (Caltech101, ImageNet) we show that the Gompertz function provides a good approximation to determine the accuracy of a model given the fraction of the data of the image that is actually conveyed to the model. We formulate the offloading decision process using this new flexibility and show that a better overall accuracy-latency tradeoff is attained: 58% traffic reduction, 25% latency reduction, as well as 12% accuracy improvement.

With the increasing demand for computationally intensive services like deep learning tasks, emerging distributed computing platforms such as edge computing (EC) systems are becoming more popular. Edge computing systems have shown promising results in terms of latency reduction compared to the traditional cloud systems. However, their limited processing capacity imposes a trade-off between the potential latency reduction and the achieved accuracy in computationally-intensive services such as deep learning-based services. In this paper, we focus on finding the optimal accuracy-time trade-off for running deep learning services in a three-tier EC platform where several deep learning models with different accuracy levels are available. Specifically, we cast the problem as an Integer Linear Program, where optimal task scheduling decisions are made to maximize overall user satisfaction in terms of accuracy-time trade-off. We prove that our problem is NP-hard and then provide a polynomial constant-time greedy algorithm, called GUS, that is shown to attain near-optimal results. Finally, upon vetting our algorithmic solution through numerical experiments and comparison with a set of heuristics, we deploy it on a test-bed implemented to measure for real-world results. The results of both numerical analysis and real-world implementation show that GUS can outperform the baseline heuristics in terms of the average percentage of satisfied users by a factor of at least 50%.

The emergence of modern monitoring, communication, computation, and control equipment into power systems has made them evolve into smart grids that can be thought of as the electric grid of things. This evolution has enhanced the efficiency of the power systems through the availability of a large volume of system data that can help with system functions nevertheless, it has intensified the communication and computation burden on these systems. While many such computations were traditionally deployed in central servers, new technologies such as edge computing can provide unique opportunities to address some of the computational challenges and improve the responsiveness of the system by processing data locally. In this paper, an edge enabled smart grid architecture is presented. The edge layer for the smart grid is designed through various optimization formulations to identify the placement of edge servers and their connectivity structure to the Phasor Measurement Units in the system. Various factors affecting the design, such as the geographical and resource constraints as well as the communication technology considerations have been incorporated in the formulations and evaluated using the IEEE 118 bus system.

This paper considers the problem of service placement and task scheduling on a three-tiered edge-to-cloud platform when user requests must be met by a certain deadline. Time-sensitive applications (e.g., augmented reality, gaming, real-time video analysis) have tight constraints that must be met. With multiple possible computation centers, the “where” and when” of solving these requests becomes paramount when meeting user deadlines. We formulate the problem of meeting users’ deadlines while minimizing the total cost to the edge-to-cloud service provider as an Integer Linear Programming (ILP) problem. We show the NP-hardness of this problem, and propose two heuristics based on making decisions on a local vs global scale. We vary the user numbers, the QoS constraint, and the cost difference between a remote cloud and cloudlets(edge clouds), and run multiple Monte-Carlo runs for each case. Our simulation results show that the proposed heuristics are performing close to optimal while reducing complexity.

Online social networks (OSN) are an increasingly powerful force for information diffusion and opinion sharing in society. Thus, understanding and modeling their structure and behavior is critical. Researchers need vast databases of self-contained, appropriately-sized OSN topologies in order to test and train new algorithms and models to solve problems related to these platforms. In this paper, we present a flexible, robust, and novel model for generating synthetic networks which closely resemble real OSN network systems (e.g., Facebook and Twitter) that include community structures. We also present an automated parameter tuner which can match the model’s output to a given OSN topology. The model can then be used as a data factory to generate testbeds of synthetic topologies which closely resemble the given sample. We compare our model, tuned to match two large real-world OSN network samples, with the Barabasi-Albert model and the Lancichinetti-Fortunato-Radicchi benchmark used as baselines. We find that output of our proposed generative model more closely matches the target topologies, than either model, on a variety of important metrics — including clustering coefficient, modularity, assortativity, and average path length. Our model also organically generates robust, realistic communities, with non-trivial inter- and intra-community structure.

Edge computing provides an ideal platform to enable many critical and time-sensitive applications in monitoring and operation of critical cyber-physical systems, such as smart grids. In this paper, we consider one of the key operations for smart grid’s reliability, which is situational awareness and discuss the role that the edge computing can play to enhance this operation by providing distributed state estimation (DSE) locally at the edge nodes. We specifically focus on the network of the phasor measurement units (PMUs) as an example of the industrial internet of things in smart grids and discuss the edge-computing platform architecture to enable data analytics for DSE using the PMU time-series. We discuss that it is important to consider the physics of the smart grid in designing the edge-computing layer. As an example, we present a data-driven method for detecting power line trips using the PMU data and the designed physics-aware edge-computing platform.

Mobile edge computing allows wireless users to exploit the power of cloud computing without the large communication delay. To serve data-intensive applications (e.g., augmented reality, video analytics) from the edge, we need, in addition to CPU cycles and memory for computation, storage resource for storing server data and network bandwidth for receiving user-provided data. Moreover, the data placement needs to be adapted over time to serve time-varying demands, while considering system stability and operation cost. We address this problem by proposing a two-time-scale framework that jointly optimizes service (data & code) placement and request scheduling, under storage, communication, computation, and budget constraints. We fully characterize the complexity of our problem by analyzing the hardness of various cases. By casting our problem as a set function optimization, we develop a polynomial-time algorithm that achieves a constant-factor approximation under certain conditions. Extensive synthetic and trace-driven simulations show that the proposed algorithm achieves 90% of the optimal performance.

This paper investigates the effectiveness of standard centrality metrics for interdependent networks (IDN) in identifying important nodes in preventing catastrophic failure propagation. To show the need for designing specialized centrality metrics for IDNs, we compare the performance of these metrics in an IDN under two different scenarios: i) the nodes with highest centrality of networks composing an IDN are selected separately and ii) the nodes with highest centrality of the entire IDN represented as one single network are calculated. To investigate the resiliency of an IDN, a threshold-based failure propagation model is used to simulate the evolution of failure propagation over time. The nodes with highest centrality are chosen and are assumed to be resistant w.r.t failure. Extensive simulation is conducted to compare the usefulness of standard metrics to stop or slow down the failure propagation in an IDN. Finally a new metric of centrality tailored for interdependent networks is proposed and evaluated. Also, useful guidelines on designing new metrics are presented.