Most of today's infrastructure systems can be efficiently operated thanks to the intelligent power supply of the smart grids. However, smart grids are highly vulnerable to malicious attacks, that is, because of the interplay between the components in the smart grids, the failure of some critical components may result in the cascading failure and breakdown of the whole system. Therefore, the question of how to identify the most critical components to protect the smart grid system is the first challenge to operators. To enable the system's robustness, there has been a lot of effort aimed at the system analysis, designing new architectures, and proposing new algorithms. However, these works mainly introduce different ranking methods for link (transmission line) or node (station) identification and directly select most the highest degree nodes or common links as the critical ones. These methods fail to address the problem of interdependencies between components nor consider the role of users that is one of critical factors impacting on the smart grid vulnerability assessment. This motivates us to study a more general and practical problem in terms of smart grid vulnerability assessment, namely the Maximum-Impact through Critical-Line with Limited Budget (MICLLB) problem. The objective of this research is to provide an efficient method to identify critical components in the system by considering a realistic attack scenario.

Opportunistic networks enable mobile devices to communicate with each other through routes that are built dynamically, while messages are en route between the sender and the destination(s). The social structure and interaction of users of such devices dictate the performance of routing protocols in those networks. Community structures, commonly exhibited by social networks, is also observed in the encounter patterns in opportunistic networks and has an astounding impact in designing forwarding algorithms for such types of networks. In this paper, we explore the structural vulnerability of social-based forwarding and routing methods in opportunistic networks. In particular, we introduce Community Vulnerability Assessment (CVA), a new problem on assessing the performance reliability of opportunistic routing strategies in Delay Tolerant Networks (DTN) from a community structure point of view. Given a positive number k, CVA aims to find out the k most vulnerable devices in the network whose non-participation (due to out-of-service or permanent out-of-range) transforms the current network community structure to a totally different one. As the first study in this direction, we analyze and provide key insights into the separation of network communities, evaluated via the Normalized Mutual Information (NMI). Based on these findings, we suggest an approximation algorithm for the special case when k 1/4 1, and a heuristic, genEdge, for the general case. To certify the effectiveness of our proposed approaches, we first test them on synthesized data with known community structures, and then we show the impact of node removal on community structures in real social networks. Finally we evaluate the performance via different forwarding and routing strategies in multiple real-world DTN traces. Our results indicate that, in many forwarding and routing methods, the nonparticipation of only some important devices is significant enough to degrade the entire network's performance.

In this paper, we develop Targeted Dot Product Representation (TarDPR), a DPR-based feature selection and combination framework for friend recommendation in online social networks (OSNs). Our approach modifies conventional DPR techniques and makes itself applicable to OSNs by focusing on computing a consistent representation while minimizing unnecessary suggestions made outside these interested regions. A notable property of TarDPR is its ability to effectively incorporate different types of social features and produce new meaningful features that help competitive approaches to significantly improve their recommendation quality. We derive an iterative algorithm for TarDPR that is supported by mathematical analysis, and is efficient on large social traces. To certify the usability of our approach, we conduct empirical experiments on real social traces including Facebook and Foursquare social networks. The competitive experimental results show that TarDPR achieves up to 15% improvement in comparison with other competitive methods. These results consequently confirm the efficacy of our suggested framework.

The analysis of climate data as a complex network has shown a great deal of promise over the last decade. Because of the massive size of the resulting network structure, much of the literature in this area has focused on the analysis of a single network snapshot generalized for a single period of time. Therefore, existing analysis methods typically focus on network properties instead of structural nature of the network to find interesting patterns. Data analysis and mining in complex climate networks at a higher temporal granularity, as a result, creates a challenging yet computationally prohibitive big data problem. In this paper, we extend the analysis of complex climate networks by studying their underlying community structures, an important property that is commonly exhibited in most complex networks. In particular, we first propose a new two-layer network model that captures community structures at both generalized and hierarchical levels where sub-communities are contained within the resulting generalized communities. Our two-layer network significantly reduces the complexity of modeling climate networks, and therefore reduces the computational complexity associated with analyzing big climate data. To mine meaningful climate patterns, we further extend this approach and suggest algorithms to find persistent communities that are stable over a long period of time. Our methods were tested on global air temperature data and we found signature communities that are verified by well known global temperature patterns. The results also produced some interesting discoveries related to known climate events such as the 1997/1997 El Niño and the eruption of Mt. Pinatubo in 1991.

We introduce Community structure Vulnerability Assessment (CVA) problem to assess the network vulnerability under a community structure point of view. Given a positive number k, CVA aims to find out the k most vulnerable nodes whose removals maximally transform the current network community structure to a different one. As the first attempt, we suggest an approximation algorithm for the special case k = 1, and propose multiple greedy algorithms for CVA problem. To certify the effectiveness of suggested approaches, we test them on not only synthesized networks with known community structures but also on real-world social traces.

We introduce A3CS, an adaptive framework with approximation guarantees for quickly identifying community structure in dynamic networks via maximizing Modularity Q. Our framework explores the advantages of power-law distribution property, is scalable for very large networks, and more excitingly, possesses approximation factors to ensure the quality of its detected community structure. To the best of our knowledge, this is the first framework that achieves approximation guarantees for the NP-hard modularity maximization problem, especially on dynamic networks. To certify our approach, we conduct extensive experiments in comparison with other adaptive methods on both synthesized networks with known community structures and real-world traces including ArXiv e-print citation and Facebook social networks. Excellent empirical results not only confirm our theoretical results but also promise the practical applicability of A3CS in a wide range of dynamic networks.

Link failure localization has been an important and challenging problem for all-optical networks. The most general monitoring structure, called m-trail, is a light-path into which optical signals are launched and monitored. How to minimize the number of required m-trails is critical to the expense of this technique. Existing solutions are limited to localizing single link failure or handling only small networks. Moreover, some practical constraints, like lacking of knowledge of the failure quantity, are ignored. To overcome these limitations is prospective but quite challenging. To this end, we provide novel theoretical solution frameworks toward the multi-failure localization problem. On one hand, for small dense networks, we provide a tree-decomposition based algorithm; on the other hand, a random walk based localized algorithm for large scale sparse networks is proposed. In addition, we further adapt these two algorithms to cope with three practical constraints. Theoretical analysis and simulation results are included to prove the correctness and efficiency of the proposed schemes.

The assessment of network vulnerability is of great importance in the presence of unexpected disruptive events or adversarial attacks targeting on critical network links and nodes. In this paper, we study Critical Link Disruptor (CLD) and Critical Node Disruptor (CND) optimization problems to identify critical links and nodes in a network whose removals maximally destroy the network's functions. We provide a comprehensive complexity analysis of CLD and CND on general graphs and show that they still remain NP-complete even on unit disk graphs and power-law graphs. Furthermore, the CND problem is shown NP-hard to be approximated within Ω([(n-k)/(nε)] ) on general graphs withnvertices andkcritical nodes. Despite the intractability of these problems, we propose HILPR, a novel LP-based rounding algorithm, for efficiently solving CLD and CND problems in a timely manner. The effectiveness of our solutions is validated on various synthetic and real-world networks.

During the last decade, Reactive Jamming Attack has emerged as a great security threat to wireless sensor networks, due to its mass destruction to legitimate sensor communications and difficulty to be disclosed and defended. Considering the specific characteristics of reactive jammer nodes, a new scheme to deactivate them by efficiently identifying all trigger nodes, whose transmissions invoke the jammer nodes, has been proposed and developed. Such a trigger-identification procedure can work as an application-layer service and benefit many existing reactive-jamming defending schemes. In this paper, on the one hand, we leverage several optimization problems to provide a complete trigger-identification service framework for unreliable wireless sensor networks. On the other hand, we provide an improved algorithm with regard to two sophisticated jamming models, in order to enhance its robustness for various network scenarios. Theoretical analysis and simulation results are included to validate the performance of this framework.

Social networks exhibit a very special property: community structure. Understanding the network community structure is of great advantages. It not only provides helpful information in developing more social-aware strategies for social network problems but also promises a wide range of applications enabled by mobile networking, such as routings in Mobile Ad Hoc Networks (MANETs) and worm containments in cellular networks. Unfortunately, understanding this structure is very challenging, especially in dynamic social networks where social activities and interactions are evolving rapidly. Can we quickly and efficiently identify the network community structure? Can we adaptively update the network structure based on previously known information instead of recomputing from scratch? In this paper, we present Quick Community Adaptation (QCA), an adaptive modularity-based method for identifying and tracing community structure of dynamic online social networks. Our approach has not only the power of quickly and efficiently updating network communities, through a series of changes, by only using the structures identified from previous network snapshots, but also the ability of tracing the evolution of community structure over time. To illustrate the effectiveness of our algorithm, we extensively test QCA on real-world dynamic social networks including ENRON email network, arXiv e-print citation network and Facebook network. Finally, we demonstrate the bright applicability of our algorithm via a realistic application on routing strategies in MANETs. The comparative results reveal that social-aware routing strategies employing QCA as a community detection core outperform current available methods.

Network coverage is one of the most decisive factors for determining the efficiency of a wireless sensor network. However, in dangerous or hostile environments such as battle fields or active volcano areas, we can neither deterministically or purposely deploy sensors as desired, thus the emergence of coverage holes (the unmonitored areas) is unavoidable. In addition, the introduction of new coverage holes during network operation due to sensor failures due to energy depletion shall significantly reduce coverage efficacy. Therefore, we need to either remotely control or set up a protocol to heal them as soon as possible in an automated fashion. In this paper, we focus on how to schedule mobile sensors in order to cope with coverage hole issues in a hybrid sensor network containing both static and mobile sensors. To this end, we introduce a new metric, namely to maximize the minimum remaining energy of all moved sensor since the more energy remains, the longer the network can operate. Based on this metric, we propose an efficient coverage healing algorithm that always determines an optimal location for each mobile sensor in order to heal all coverage holes, after all mobile sensors locations and coverage holes are located. Simulation results confirm the efficiency and utilization of our proposed method.

Many practical problems on Mobile networking, such as routing strategies in MANETs, sensor reprogramming in WSNs and worm containment in online social networks (OSNs) share an ubiquitous, yet interesting feature in their organizations: community structure. Knowledge of this structure provides us not only crucial information about the network principles, but also key insights into designing more effective algorithms for practical problems enabled by Mobile networking. However, understanding this interesting feature is extremely challenging on dynamic networks where changes to their topologies are frequently introduced, and especially when network communities in reality usually overlap with each other. We focus on the following questions (1) Can we effectively detect the overlapping community structure in a dynamic network? (2) Can we quickly and adaptively update the network structure only based on its history without recomputing from scratch? (3) How does the detection of network communities help mobile applications? We propose AFOCS, a two-phase framework for not only detecting quickly but also tracing effectively the evolution of overlapped network communities in dynamic mobile networks. With the great advantages of the overlapping community structure, AFOCS significantly helps in reducing up to 7 times the infection rates in worm containment on OSNs, and up to 11 times overhead while maintaining good delivery time and ratio in forwarding strategies in MANETs.

How to assess the topology vulnerability of a network has attracted more and more attentions recently. Due to the rapid growing number of real- time internet applications developed since the last decade, the discovery of topology weakness related to its quality of service (QoS) is of more interest. In this paper, we provide a novel QoS-aware measurement for assessing the vulnerability of general network topologies. Specifically, we evaluate the vulnerability by detecting the minimum number of link failures that decrease the satisfactory level of the QoS-Optimal source- destination path to a given value, which means a topology with a smaller amount of such link failures is more vulnerable. We formulate this process as a graph optimization problem called QoSCE and provide several exact and heuristic algorithms for various QoS constraint amounts. To our best knowledge, this is the first graph-theoretical framework to evaluate QoS-aware topology vulnerability. Through extensive simulations, the performance of the proposed algorithms are validated in terms of assessment accuracy and time complexity.

Structurally Random Matrices (SRM) are first proposed in [1] as fast and highly efficient measurement operators for large scale compressed sensing applications. Motivated by the bridge between compressed sensing and the Johnson-Lindenstrauss lemma [2] , this paper introduces a related application of SRMs regarding to realizing a fast and highly efficient embedding. In particular, it shows that a SRM is also a promising dimensionality reduction transform that preserves all pairwise distances of high dimensional vectors within an arbitrarily small factor ∈, provided that the projection dimension is on the order of O(∈−2log3N), where N denotes the number of d-dimensional vectors. In other words, SRM can be viewed as the sub-optimal Johnson-Lindenstrauss embedding that, however, owns very low computational complexity O(d log d) and highly efficient implementation that uses only O(d) random bits, making it a promising candidate for practical, large scale applications where efficiency and speed of computation are highly critical.

Minimizing the rank of a matrix X over certain constraints arises in diverse areas such as machine learning, control system and is known to be computationally NP-hard. In this paper, a new simple and efficient algorithm for solving this rank minimization problem with linear constraints is proposed. By using gradient projection method to optimize S while consecutively updating matrices U and V (where X = USVT) in combination with the use of an approximation function for l0-norm of singular values, our algorithm is shown to run significantly faster with much lower computational complexity than general-purpose interior-point solvers, for instance, the SeDuMi package. In addition, the proposed algorithm can recover the matrix exactly with much fewer measurements and is also appropriate for large-scale applications.

This paper proposes a novel framework called Distributed Compressed Video Sensing (DISCOS) - a solution for Distributed Video Coding (DVC) based on the recently emerging Compressed Sensing theory. The DISCOS framework compressively samples each video frame independently at the encoder. However, it recovers video frames jointly at the decoder by exploiting an interframe sparsity model and by performing sparse recovery with side information. In particular, along with global frame-based measurements, the DISCOS encoder also acquires local block-based measurements for block prediction at the decoder. Our interframe sparsity model mimics state-of-the-art video codecs: the sparsest representation of a block is a linear combination of a few temporal neighboring blocks that are in previously reconstructed frames or in nearby key frames. This model enables a block to be optimally predicted from its local measurements by l1-minimization. The DISCOS decoder also employs a sparse recovery with side information to jointly reconstruct a frame from its global measurements and its local block-based prediction. Simulation results show that the proposed framework outperforms the baseline compressed sensing-based scheme of intraframe-coding and intraframe-decoding by 8 – 10dB. Finally, unlike conventional DVC schemes, our DISCOS framework can perform most encoding operations in the analog domain with very low-complexity, making it be a promising candidate for real-time, practical applications where the analog to digital conversion is expensive, e.g., in Terahertz imaging.

We propose a novel Layered Compressed Sensing (CS) approach for robust transmission of video signals over packet loss channels. In our proposed method, the encoder consists of a base layer and an enhancement layer. The base layer is a conventionally encoded bitstream and transmitted without any error protection. The additional enhancement layer is a stream of compressed measurements taken across slices of video signals for error-resilience. The decoder regards the corrupted base layer as the side information (SI) and employs a sparse recovery with SI to recover approximation of lost packets. By exploiting the SI at the decoder, the enhancement layer is required to transmit a minimal amount of compressed measurements for error protection that is only proportional to the amount of lost packets. Simulation results show that both compression efficiency and error-resilience capacity of the proposed scheme are competitive with those of other state-of-the-art robust transmission methods, in which Wyner-Ziv (WZ) coders often generate an enhancement layer. Thanks to the soft-decoding feature of sparse recovery algorithms, our CS-based scheme can avoid the cliff effect that often occurs with otherWyner-Ziv based schemes when the error rate is over the error correction capacity of the channel code. In addition, our result suggests that compressed sensing is actually closer to source coding with decoder side information than to conventional source coding.