Web-based ranking problems involve ordering different kinds of items in a list or grid to be displayed in mediums like a website or a mobile app. In most cases, there are multiple objectives or metrics like clicks, viral actions, job applications, advertising revenue and others that we want to balance. Constructing a serving algorithm that achieves the desired tradeoff among multiple objectives is challenging, especially for more than two objectives. In addition, it is often not possible to estimate such a serving scheme using offline data alone for non-stationary systems with frequent online interventions. We consider a large-scale online application where metrics for multiple objectives are continuously available and can be controlled in a desired fashion by changing certain control parameters in the ranking model. We assume that the desired balance of metrics is known from business considerations. Our approach models the balance criteria as a composite utility function via a Gaussian process over the space of control parameters. We show that obtaining a solution can be equated to finding the maximum of the Gaussian process, practically obtainable via Bayesian optimization. However, implementing such a scheme for large-scale applications is challenging. We provide a novel framework to do so and illustrate its efficacy in the context of LinkedIn Feed. In particular, we show the effectiveness of our method by using both offline simulations as well as promising online A/B testing results. At the time of writing this paper, the method described was fully deployed on the LinkedIn Feed.

This paper presents a system, System U, which automatically derives people's personality traits from social media and recommends people for different tasks. The system leverages linguistic signals appearing in a person's social media activities to compute the personality portraits including Big Five personality, fundamental needs and basic human values. This system and technology can be used in a wide variety of personalized applications, such as recommending people to answer questions.

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.

Society relies heavily on its networked physical infrastructure and information systems. Accurately assessing the vulnerability of these systems against disruptive events is vital for planning and risk management. Existing approaches to vulnerability assessments of large-scale systems mainly focus on investigating inhomogeneous properties of the underlying graph elements. These measures and the associated heuristic solutions are limited in evaluating the vulnerability of large-scale network topologies. Furthermore, these approaches often fail to provide performance guarantees of the proposed solutions. In this paper, we propose a vulnerability measure, pairwise connectivity, and use it to formulate network vulnerability assessment as a graph-theoretical optimization problem, referred to as -disruptor. The objective is to identify the minimum set of critical network elements, namely nodes and edges, whose removal results in a specific degradation of the network global pairwise connectivity. We prove the NP-completeness and inapproximability of this problem and propose an pseudo-approximation algorithm to computing the set of critical nodes and an pseudo-approximation algorithm for computing the set of critical edges. The results of an extensive simulation-based experiment show the feasibility of our proposed vulnerability assessment framework and the efficiency of the proposed approximation algorithms in comparison to other approaches.

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.

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.

Assessing network vulnerability before potential disruptive events such as natural disasters or malicious attacks is vital for network planning and risk management. It enables us to seek and safeguard against most destructive scenarios in which the overall network connectivity falls dramatically. Existing vulnerability assessments mainly focus on investigating the inhomogeneous properties of graph elements, node degree for example, however, these measures and the corresponding heuristic solutions can provide neither an accurate evaluation over general network topologies, nor performance guarantees to large scale networks. To this end, in this paper, we investigate a measure called pairwise connectivity and formulate this vulnerability assessment problem as a new graph-theoretical optimization problem called ß-disruptor, which aims to discover the set of critical node/edges, whose removal results in the maximum decline of the global pairwise connectivity. Our results consist of the NP-Completeness and inapproximability proof of this problem, an O(log n log log n) pseudo-approximation algorithm for detecting the set of critical nodes and an O(log1.5n) pseudo-approximation algorithm for detecting the set of critical edges. In addition, we devise an efficient heuristic algorithm and validate the performance of the our model and algorithms through extensive simulations.

Application DoS attack, which aims at disrupting application service rather than depleting the network resource, has emerged as a larger threat to network services, compared to the classic DoS attack. Owing to its high similarity to legitimate traffic and much lower launching overhead than classic DDoS attack, this new assault type cannot be efficiently detected or prevented by existing detection solutions. To identify application DoS attack, we propose a novel group testing (GT)-based approach deployed on back-end servers, which not only offers a theoretical method to obtain short detection delay and low false positive/negative rate, but also provides an underlying framework against general network attacks. More specifically, we first extend classic GT model with size constraints for practice purposes, then redistribute the client service requests to multiple virtual servers embedded within each back-end server machine, according to specific testing matrices. Based on this framework, we propose a two-mode detection mechanism using some dynamic thresholds to efficiently identify the attackers. The focus of this work lies in the detection algorithms proposed and the corresponding theoretical complexity analysis. We also provide preliminary simulation results regarding the efficiency and practicability of this new scheme. Further discussions over implementation issues and performance enhancements are also appended to show its great potentials.

Many communication networks such as Mobile Ad Hoc Networks (MANETs) involve in human interactions and exhibit properties of social networks. Hence, it is interesting to see how knowledge from social networks can be used to enhance the communication processes. We focus on the use of identifying modular structure in social networks to improve the efficiency of routing strategies. Since nodes mobility in a network often alters its modular structure and requires recomputing of modules from scratch, updating the modules is the main bottleneck in current social-aware routing strategies where nodes often have limited processing speed. Towards real-time routing strategies, we develop an adaptive method to efficiently update modules in a dynamic network in which a novel compact representation of the network is used to significantly reduces the network size while preserving essential network structure.

Among existing countermeasures against Reactive Jamming Attacks in Wireless Sensor Networks, the detection of trigger nodes whose transmissions invoke the jammer nodes has been proposed and developed as an efficient jamming-resistent routing scheme in unreliable WSN environments. Sequential group testing techniques were adopted in our previous work to alleviate the overhead of trigger detection in terms of time and communication complexity. In this paper, we further improve the detection procedure by leveraging the classic models of randomized non-adaptive group testing and clique-independent set, which dramatically decreases the time complexity compared to our previous solution.

Despite decades of research, there have not been developed concrete defense solutions for most of current attacks to Internet services, let alone new attack types. An essential problem to overcome is that malicious traffic can be similar to legitimate ones. Thus a more fundamental model which should be based on the overall performance of servers/subnets without inspecting each traffic must be remedied. Based on this observation, we propose a novel system framework, called detection of malicious users (DMU) which attempts to solve various attack types. Motivated by DMU, we introduce a new theoretical model, called size constraint group testing (SCGT). Several algorithms based on SCGT for various networking scenarios are proposed. We also provide several fundamental results on SCGT, revealing some necessary conditions to obtain an O(1) detection time algorithm.