Advances in Network Analysis and its Applications

Since the onset of the financial crisis in 2007, more than 370 of the almost 8,000 US banks insured by the Federal Deposit Insurance Corporation have failed. By comparison, between 2000 and 2004 there were around 30 failures and no failures occurred between 2005 and the beginning of 2007.

An analytical approach to calculating the expected size of contagion events in models of banking networks is presented. The method is applicable to networks with arbitrary degree distributions, permits cascades to be initiated by the default of one or more banks, and includes liquidity risk effects. Theoretical results are validated by comparison with Monte Carlo simulations, and may be used to assess the stability of a given banking network topology.

Mathematicians delight in pointing out how much the sciences owe to mathematics, but it is only fair to record the converse: mathematics owes just as much to the sciences. Indeed, many mathematicians regard the sciences as subjects which, though useful in themselves, are mainly there to provide interesting new mathematical problems.

Trust Management (TM) systems are infrastructures that support efficient and secure access to resources in large decentralized systems. They provide a language for expressing authorizations and access control policies as well as a trust management engine that processes requests, to automatically address access requests. Traditionally, the enforcement of Trust Management decisions is static and involves the use of appropriate cryptographic mechanisms. However, recently two TM systems were proposed for which the enforcement is dynamic. Dynamic TM systems expand, (i) the expressibility of a system language to capture anomaly-triggered access control policies, and (ii) the enforcement capabilities via graduated response mechanisms such as Rollback Access control. These mechanisms are proactively triggered under the perceived potential of an attack: they selectively disrupt the TM-granted access to a resource temporarily, to mitigate the system threat. In this Chapter we discuss the use of real-time stochastic analyzers and graduated response security mechanisms to detect/prevent anomalies in TM systems, and propose an architecture for dynamic Trust Management that tolerates 0-day attacks and insider attacks.

In link state routing networks, every node has to construct a topological map through the generation and exchange of routing information. Nevertheless, if a node misbehaves then the connectivity in the network is compromised. The proactive Optimized Link State Routing (OLSR) protocol has been designed exclusively for Mobile Ad Hoc Networks (MANETs). The core of the protocol is the selection of Multipoint Relays (MPRs) as an improved flooding mechanism for distributing link state information. This mechanism limits the size and number of control traffic messages. As for several other routing protocols for MANETs, OLSR does not include security measures in its original design. Besides, OLSR has been extended to address a number of problems in MANETs. For example, Hierarchical OLSR (HOLSR) has been proposed to address scalability and Multipath OLSR (MP-OLSR) to address fault tolerance. However, these OLSR extensions can be affected either by inheriting or adding new security threats. In this chapter, we present a review of security issues and countermeasures in link state routing protocols for MANETs.

TCHo is a public-key cryptosystem based on the hardness of finding a multiple polynomial with low weight and on the hardness of distinguishing between the output of an LFSR with noise and some random source. An early version was proposed in 2006 by Finiasz and Vaudenay with non-polynomial (though practical) decryption time. The latest version came in 2007 with more co-authors. It reached competitive (heuristic) polynomial complexity and IND-CPA security. Since then, a key-recovery chosen ciphertext attack was published by Herrmann and Leander in 2009. In this paper we review the state of the art on this cryptosystem, together with some latest improvements regarding implementation and selection of parameters. We provide also more formal results regarding correctness and we update the key generation algorithm.

Neighborhood discovery is a critical part of wireless sensor networks, yet little work has been done on formal verification of the protocols in presence of both intruder nodes and mobility. We present a formal trace-based model to verify protocols doing neighborhood discovery, and we provide a formal definition of (1)-neighborhood and (k)-neighborhood. We also analyze a protocol from the literature, and show some conditions needed for its correctness. Finally, we present the groundwork for a protocol which discovers (k)-neighborhood based on (1)-neighborhood data under some assumptions, and prove that it remains secure even if an intruder interferes.

White-box cryptography concerns the design and analysis of implementations of cryptographic algorithms engineered to execute on untrusted platforms. Such implementations are said to operate in a white-box attack context. This is an attack model where all details of the implementation are completely visible to an attacker: not only do they see input and output, they see every intermediate computation that happens along the way. The goal of a white-box attacker when targeting an implementation of a cipher is typically to extract the cryptographic key; thus, white-box implementations have been designed to thwart this goal (i.e., to make key extraction difficult/infeasible). The academic study of white-box cryptography was initiated in 2002 in the seminal work of Chow et al. (White-box cryptography and an AES implementation. In: Selected areas in cryptography: 9th annual international workshop, SAC 2002. Lecture notes in computer science, vol 2595, pp 250–270, 2003). Here, we review the first white-box AES implementation proposed by Chow et al. and give detailed information on how to construct it. We provide a number of diagrams that summarize the flow of data through the various look-up tables in the implementation, which helps clarify the overall design. We then briefly review the impressive 2004 cryptanalysis by Billet et al. (Cryptanalysis of a white box AES implementation. In: Selected areas in cryptography: 11th international workshop, SAC 2004. Lecture notes in computer science, vol 3357, pp 227–240, 2005). The BGE attack can used to extract an AES key from Chow et al.’s original white-box AES implementation with a work factor of about 2³⁰, and this fact has motivated subsequent work on improved AES implementations.

In the Secure Message Transmission (SMT) problem, a sender \(\mathcal{S}\) wants to send a message m to a receiver \(\mathcal{R}\) in a private and reliable way. \(\mathcal{S}\) and \(\mathcal{R}\) are connected by nwires, t of which controlled by the adversary. The n wires represent n node disjoint communication paths between the sender and the receiver. The adversary is assumed to have unlimited computational power. An Almost Perfectly Secure Message Transmission (APSMT, for short) provides perfect privacy for the transmitted message, and the probability that the received message is different from the sent one is bounded by δ and, δ = 0 corresponds to perfect SMT. It has been shown that APSMT is possible if n ≥ 2t + 1 and for 1-round perfect SMT, n ≥ 3t + 1. SMT protocols and techniques have found applications in practice, including key distribution and key strengthening in wireless sensor networks. In this paper we show two general methods of constructing 1-round APSMT protocols for different levels of network connectivity. We consider two cases: \(n = (2 + c)t,c > \frac{1} {t}\) where a fraction of wires are corrupted, and \(n = 2t + k,k \geq 1\) where a constant number of extra wires (over the required minimum) exists. The proposed methods use the whole, or part of, the previously constructed protocols to construct new protocols with flexible connectivity, whose privacy, reliability and efficiency can be derived from the component parts. The new protocols are efficient and in some cases have optimal transmission rates. The flexibility that is provided by these constructions facilitate application of APSMT in practical applications.

Millions of street-involved-youth worldwide are vulnerable to using and trading illicit drugs, which also place this group at high risk of drug-related criminality and health problems. It is often the case that drug users begin trafficking under the social influences within the drug culture to generate income for supporting their drug habits. The relative merits of behavioural (primary) or law enforcement (secondary) interventions for controlling the spread of drug use are widely debated. In this paper, we develop a network model to evaluate the effectiveness of modelling strategies. A network model with traffickers, current drug users and potential users is constructed. Traffickers exert social influence on current users to deal drugs and on potential users to initiate drug use. Primary intervention prevents potential users from initiating drug use while secondary intervention acts to reduce initiation into trafficking. To accomplish this, we vary the hypothetical social influence parameters in the model. Next, we analyze the properties of this system using dynamical system methods including mean field approximation (MFA), fixed point theory and bifurcation analysis. Furthermore, to evaluate the relative effectiveness of the two interventions, we study the properties of the phase transition between a drug-free and a drug-endemic state at equilibrium mathematically. Drug-free and drug-endemic states are separated by a curved phase transition. Via the shape of the phase transition curve we obtain the optimal intervention. Our findings confirm that a combination of primary and secondary interventions is the optimal intervention strategy. The optimal mixture of the two strategies depends on the relative numbers of drug users and traffickers.

We give an overview of the properties and models for complex networks, with particular emphasis on models of on-line social networks.

Many North Americans now work in a global economy where corporations foster networked work – with employees participating in multiple teams and often for multiple purposes – and they do so in networked organizations – whose workers may be physically and organizationally dispersed. We analyze networked workers in one networked scholarly organization: the GRAND Network Centre of Excellence. Drawing on qualitative and social network data, we present our preliminary findings at the early stages of GRAND. Early discussions viewed networked organizations as the antithesis of traditional bureaucratic organizations and expected bureaucratic characteristics such as hierarchy, centralization and formalization to be absent and cross-boundary flows – the hallmark of networked organizations – to be prominent. Our research shows that reality is more complex than the early deductive expectations for networked organizations. The GRAND network is well positioned for cross-boundary flows but they are not yet extensive. In the distributed GRAND network, researchers communicate mostly via now-traditional email although in-person contact is almost as frequent. GRAND is designed with few formal hierarchical differences. Yet hierarchy matters when it comes to communication – researchers in higher positions have higher centrality in communication structures, both GRAND-wide and within projects, suggesting consistent advantages in their communication. Cross-disciplinary exchanges in GRAND are low at the network’s early stages, with little collaboration between Computer Science and Engineering, on the one hand, and Social Sciences and Humanities, on the other. Researchers in Arts and Technology emerge as the most active collaborators in the network both internally and externally. Work within provinces is still the norm.

Terrorist cells are modeled as finite partially ordered sets. This paper determines the structure of the terrorist cell most likely to remain intact if a subset of its members is captured at random, provided that the cell has a single leader and no member has more than two immediate subordinates.

This chapter presents the Appeal, Belonging, Commitment (ABC) conceptual framework, which describes how online social networks can be designed to motivate positive health behaviour change. The ABC Framework is based on the existing theoretical models that describe the determinants for motivating the use of online social networks and health behaviour change. Common themes are drawn from these theoretical models and combined to provide the determinants for the three emergent themes: Appeal (individual determinants), Belonging (social determinants) and Commitment (temporal determinants). Results from a questionnaire survey and interviews are presented to validate and iterate the ABC Framework. Based on these themes and their determinants, design suggestions are presented. A case study implementation of the ABC Framework is shown through the design of VivoSpace. The design strategies are interpreted to design the online social health system, VivoSpace, and the ABC Framework is used to evaluate the design. This case study shows that the ABC Framework provides the best methodology to design and evaluate an online social network that will lead to a committed user base and motivate health behaviour change.

The study attempts to better understand the evolution of the structure of a network using two snapshots of the developer-project affiliations in an Open Source Software (OSS) community. We use complex networks and social network theory to guide our analysis. We proceed by first extracting separate bipartite networks of projects in each of the five development stages – planning, pre-alpha, alpha, beta and production/stables stages. Then, by analyzing changes in the network using degree distributions, assortativity, component sizes, visualizations and p-star models, we try to infer the project-joining behavior of the OSS developers. Simulations are used to establish the significance of some findings. Highlights of our results are the higher levels of assortativity and networking in the Beta and Stable subnetworks, and a surprisingly higher level of connectivity of the Planning subnetwork. Significant clustering of projects is observed based on the programming language but not on other project attributes, including even licenses.

Social-networking sites are becoming increasingly popular with users of all ages. With much of our social activity happening online, these sites are now becoming the subject of scholarly study and research. Unfortunately, despite the fact that they collect similar content and support similar relations and activities, the current generation of these sites are hard to query programmatically, offering limited views of their data, effectively becoming disconnected islands of information. We describe SociQL, a high-level query language, and a corresponding service, to which social-networking sites can subscribe, that supports the integrated representation, querying and exploration of disparate social networks. Unlike generic web query languages, SociQL is designed specifically to support the integration of networks through a common information model for the purpose of examining sociological questions, motivated by social theories. The paper discusses the design and rationale for the SociQL language elements and syntax, as well as our experience using the SociQL service to query a variety of social-network sites.