Handbook of Optimization in Complex Networks

The concept of vulnerability in the context of complex networks quantifies the capacity of a network to maintain its functional performance under random damages, malicious attacks, or malfunctions of any kind. Different types of networks and different applications suggest different approaches to the concept of networks structural vulnerability depending on the aspect we focus upon. In this introductory chapter, we discuss some different approaches and relationships amongst them.

Complex networks need resilience to cascades – to prevent the failure of a single node from causing a far-reaching domino effect. Such resilience can be achieved actively or topologically. In active resilience schemes, sensors detect the cascade and trigger responses that protect the network against further damage. In topological resilience schemes, the network’s connectivity alone provides resilience by dissipating nascent cascades. Designing topologically resilient networks is a multi-objective discrete optimization problem, where the objectives include resisting cascades and efficiently performing a mission. Remarkably, terrorist networks and other “dark networks” have already discovered how to design such networks. While topological resilience is more robust than active resilience, it should not always be pursued because in some situations it requires excessive loss of network efficiency.

Complex biological, social, and technological systems can be often modeled by weighted networks. The network topology, together with the distribution of available link or node capacity (represented by weights) and subject to cost constraints, strongly affect the dynamics or performance of the networks. Here, we investigate optimization in fundamental synchronization and flow problems where the weights are proportional to (k _i k _j )^β with k _i and k _j being the degrees of the nodes connected by the edge. In the context of synchronization, these weights represent the allocation of limited resources (coupling strength), while in the associated random walk and current flow problems, they control the extent of hub avoidance, relevant in routing and search. In this chapter, we review fundamental connections between stochastic synchronization, random walks, and current flow, and we discuss optimization problems for these processes in the above weighted networks.

In this chapter, we are concerned with robustness design in complex communication networks and power grids. We define robustness as the ability of a network to adapt to environmental variations such as traffic fluctuations, topology modifications, and changes in the source (sink) of external traffic. We present a network theory approach to the joint optimization of resources and routes in a communication network to provide robust network operation. Our main metrics are the well-known point-to-point resistance distance and network criticality (average resistance distance) of a graph. We show that some of the key performance metrics in a communication network, such as average link betweenness sensitivity or average network utilization, can be expressed as a weighted combination of point-to-point resistance distances. A case of particular interest is when the external demand is specified by a traffic matrix. We extend the notion of network criticality to be a traffic-aware metric. Traffic-aware network criticality is then a weighted linear combination of point-to-point resistance distances of the graph. For this reason, in this chapter, we focus on a weighted linear sum of resistance distances (which is a convex function of link weights) as the main metric and we discuss a variety of optimization problems to jointly assign routes and flows in a network. We provide a complete mathematical analysis of the network planning problem (optimal weight assignment), where we assume that a routing algorithm is already in place and governs the distribution of network flows. Then, we extend the analysis to a more general case involving the simultaneous optimization of resources and flows (routes) in a network. Furthermore, we briefly discuss the problems of finding the best set of demands that can be matched to a given network topology (joint optimization of resources, flows, and demands) subject to the condition that the weighted linear sum of all point-to-point resistance distances of the network should remain below a certain threshold. We discuss applications of the proposed optimization methods to the design of virtual networks. Moreover, we show how our techniques can be used in the design of robust communication networks and robust sparse power grids.

Clique relaxation models that were originally introduced in the literature on social network analysis are not only gaining increasing popularity in a wide spectrum of complex network applications, but also keep garnering attention of mathematicians, computer scientists, and operations researchers as a promising avenue for fruitful theoretical investigations. This chapter describes the origins of clique relaxation concepts and provides a brief overview of mathematical programming formulations for the corresponding optimization problems, algorithms proposed to solve these problems, and selected real-life applications of the models of interest.

Understanding and analyzing traffic characteristics are fundamental to the design, development and implementation of networks. The traditional emphasis of network traffic analysis has been on the statistical properties of traffic, leading to the important discoveries such as heavy-tails and long range dependence. As networking technologies continue to mature and evolve, and more sophisticated network applications are invented and deployed, operating, managing and securing networks have become increasingly challenging tasks, and require us to understand, analyze and model the behavioral characteristics of network traffic, such as communication patterns, interaction structures and trends of applications, users and other entities in the networks.

Centrality is a concept often used in social network analysis (SNA) to study different properties of networks that are modeled as graphs. Bridging nodes are strategically important nodes in a network graph that are located in between highly-connected regions. We developed a new centrality metric called Localized Bridging Centrality (LBC) to allow a user to identify and rank bridging nodes. LBC is a distributed variant of the Bridging Centrality (BC) metric and both these metrics are used to identify and rank bridging nodes. LBC is capable of identifying bridging nodes with an accuracy comparable to that of the BC metric for most networks, but is an order of magnitude less computationally expensive. As the name suggests, we use only local information from surrounding nodes to compute the LBC metric. Thus, our LBC metric is more suitable for distributed or parallel computation than the BC metric. We applied our LBC metric on several examples, including a real wireless mesh network. Our results indicate that the LBC metric is as powerful as the BC metric at identifying bridging nodes. We recently designed a new SNA metric that is also suitable for use in wireless mesh networks: the Localized Load-aware Bridging Centrality (LLBC) metric. The LLBC metric improves upon LBC by detecting critical bridging nodes while taking into account the actual traffic flows present in a communications network. We developed the SNA Plugin (SNAP) for the Optimized Link State Routing (OLSR) protocol to study the potential use of LBC and LLBC in improving multicast communications and our initial results are promising. In this chapter we present an introduction to SNA centrality metrics with a focus on our contributed metrics: LBC and LLBC. We also present some initial results from applying our metrics in real and emulated wireless mesh networks.

Nonlinear optimization problems (if not convex) are NP-hard in general. One effective approach to develop efficient solutions for these problems is to apply the branch-and-bound (BB) framework. A key step in BB is to obtain a tight linear relaxation for each nonlinear term. In this chapter, we show how to apply a powerful technique, called Reformulation–Linearization Technique (RLT), for this purpose. We consider a throughput maximization problem for an ultra-wideband (UWB)-based sensor network. Given a set of source sensor nodes in the network with each node generating a certain data rate, we want to determine whether or not it is possible to relay all these rates successfully to the base station. We formulate an optimization problem, with joint consideration of physical layer power control, link layer scheduling, and network layer routing. We show how to solve this nonlinear optimization problem by applying RLT and BB. We also use numerical results to demonstrate the efficacy of the proposed solution.

This chapter applies the general complex network theory to study a parallel routing algorithm called Classified Traffic Routing (CTR) for traffic optimization. The parallel routing algorithm involves two routing tables when forwarding packets. For CTR, performance analysis is performed which focuses on loss, delay, and energy in a scale-free network. Its performance is also compared to those of single routing algorithms. For existing two main kinds of single routing algorithms - shortest path first and congestion avoidance first algorithms, we select one representative algorithm from each kind for comparison. The result shows that good loss or delay performance (but not both) can be obtained for each representative routing algorithm, namely Shortest Path First (SPF) algorithm and Optimal Routing (OR) algorithm. The chapter then discusses a study on energy performance of these two algorithms. The results show that the two algorithms have very different performance on average energy consumption and on distribution of energy consumption among all nodes. This chapter then argues that single routing algorithm could not meet the requirements of different types of traffic while could not balance the energy consumption. In order to provide good loss performance for loss-sensitive traffic and good delay performance for delay-sensitive traffic, and in consideration of energy consumption, forwarding packets with CTR is a good choice. Simulation results show that CTR can give a much more balanced performance on loss, delay, and energy than those of SPF and OR.

This chapter focuses on services networks. We review the important aspects of services (flow patterns, semantic issues, Quality of Service (QoS) and user preferences), as well as service composition techniques, network metrics and models. The Concept-Service (CS) network matrix is introduced. The CS network dynamics and optimization based service composition are the original contributions of this chapter based on our years of research on this topic.

Community structure is a very special and interesting property of social networks. Knowledge of network community structure not only provides us key insights into 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 tend to come and go rapidly. Can we quickly and efficiently identify the network community structure? Can we adaptively update this structure based on its history instead of recomputing from scratch?In this chapter, we present two methods for detecting community structures on social networks. First, we introduce Quick Community Adaptation (QCA), an adaptive modularity-based method for identifying and tracing the discrete community structure of dynamic social networks. This approach has not only the power of quickly and efficiently updating the network structure by only using the identified structures, but also the ability of tracing the evolution of its communities over time. Next, we present DOCA, an quick method for revealing the overlapping network communities that can be implemented in a decentralized manner. To illustrate the effectiveness of our methods, we extensively test QCA and DOCA on not only synthesized but also 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 methods via two realistic applications on routing strategies in MANETs and worm containment on online social networks.

This is the online abstract make sure it is same as the abstract below!. TODO for the final version. dont bother changing beforehand

The proliferation of powerful portable devices has created a new environment for networking. In such environment, devices are able to communicate between “challenged” networks such as sensor networks, mobile ad-hoc networks, or opportunistic ad-hoc networks using a set of protocols designed to accommodate disconnection. In particular, forwarding in mobile opportunistic networks needs to deal with such disconnections, and limited resources. As opposed to conventional communication that relies on infrastructure, these devices can use hop-by-hop opportunistic data forwarding between each other. In this environment, a device should decide whether or not to transfer a message at the time it meets another one. How to optimally select the next hop towards the destination in a way to minimize delay and maximize success rate is so far unknown. In opportunistic networks, a device has to decide whether or not to forward data to an intermediate node that it encounters. In this chapter, we describe PeopleRank as systematic approach to the use of social interaction as a means to guide forwarding decisions in an opportunistic network. PeopleRank ranks nodes using a tunable weighted combination of social and contact information. It gives higher weight to the social information in cases where there is correlation between that information and the contact trace information. More specifically, PeopleRank is an opportunistic forwarding algorithm that ranks the “importance” of a node using a combination of social and contact-graph information.

Online social networks are increasingly being seen as a means of obtaining awareness of user preferences. Such awareness could be used to target goods and services at them. We consider a general user model, wherein users could buy different numbers of goods at a marked and at a discounted price. Our first objective is to learn which users would be interested in a particular good. Second, we would like to know how much to discount these users such that the entire demand is realized, but not so much that profits are decreased. We develop algorithms for multihop forwarding of discount coupons over an online social network, in which users forward such coupons to each other in return for a reward. Coupling this idea with the implicit learning associated with backpressure routing (originally developed for multihop wireless networks), we show how to realize optimal revenue. Using simulations, we illustrate its superior performance as compared to random coupon forwarding on different social network topologies. We then propose a simpler heuristic algorithm and using simulations, and show that its performance approaches that of backpressure routing.

Recently, Online Social Networks (OSNs) becomes one of the most remarkable technologies in the twenty-first century since it has been extraordinarily popular with over 200 million users. Security and privacy problems are the most important issues in OSNs. In this chapter, we introduced the optimization of security and privacy problems in OSNs. We characterized three existing works with different targets to give a view of this problem.

Recently, cellular phone networks have begun allowing third-party applications to run over certain open-API phone operating systems such as Windows Mobile, Iphone and Google’s Android platform. However, with this increased openness, the fear of rogue programs written to propagate from one phone to another becomes ever more real. This chapter proposes a counter-mechanism to contain the propagation of a mobile worm at the earliest stage by patching an optimal set of selected phones. The counter-mechanism continually extracts a social relationship graph between mobile phones via an analysis of the network traffic. As people are more likely to open and download content that they receive from friends, this social relationship graph is representative of the most likely propagation path of a mobile worm. The counter-mechanism partitions the social relationship graph via two different algorithms, balanced and clustered partitioning and selects an optimal set of phones to be patched first as those have the capability to infect the most number of other phones. The performance of these partitioning algorithms is compared against a benchmark random partitioning scheme. Through extensive trace-driven experiments using real IP packet traces from one of the largest cellular networks in the US, we demonstrate the efficacy of our proposed counter-mechanism in containing a mobile worm.