Epidemic theory has wide range of applications in computer networks, from spreading of malware to the information dissemination algorithms. Our society depends more strongly than ever on such computer networks. Many of these networks rely to a large extent on decentralization and self-organization. While decentralization removes obvious vulnerabilities related to single points of failure, it leads to a higher complexity of the system. A more complex type of vulnerability appears in such systems. For instance, computer viruses are imminent threats to all computer networks. We intend to study the interaction between malware spreading and strategies that are designed to cope with them. The main goals of this thesis are: 1. to analyze influence of network topology on infection spread 2. to determine how topology can be used for network protection 3. to formulate and study optimization of malware protection problem with respect to topology 4. to investigate non-cooperative game of security We used analytical tools from various fields to answer these questions. First of all, we have developed homogeneous and heterogeneous N-intertwined, susceptible - infected - susceptible (SIS) model for virus spread. This model is used to determine the influence of topology on the spreading process. For the N-intertwined model, we show that the largest eigenvalue of the adjacency matrix of the graph rigorously defines the epidemic threshold. The results of the model also predict the upper and lower bounds on epidemics as a function of nodal degree. The epidemic threshold is found to be a consequence of the mean field approximation. However, slow convergence to the steady-state justifies the application of the threshold concept. We used the exact 2N-state Markov chain model to explore the phase transition phenomenon for two contrasting cases, namely the line graph and the complete graph. The N-intertwined model assumes that the infection spreading over a link is a Poisson process. By introducing infection delay, we studied the influence of deviation from Poisson process assumption on epidemic threshold for the special case of a complete bi-partite graph. Due to the special structure of bi-partite graphs we were also able to derive approximate formula for the extinction probability in the first phase of the infection. In the case of SIS epidemic models, the effects of infection depend on the protection of individual nodes. We studied optimization of protection scheme for different networks. We use the results from heterogeneous N-intertwined model to determine the global optimum at the threshold. Above the threshold, the problem is a sum of ratios fractional programming problem, which is NP-complete. Therefore, we only determine the upper bound on the optimum. Contrary to the common sense, reducing the probability of infection for higher degree nodes pushes the network out of the global optimum. For the case of complete bi-partite graphs, we derive optimal threshold if only 2 fixed protection rates are available. Computer networks are generally distributed systems and protection cannot be globally optimized. The Internet is an extreme example: there is no global control center, and obtaining complete information on its global state is an illusion. To approach the issue of security over decentralized network, we derived a novel framework for network security under the presence of autonomous decision makers. The problem under the consideration is the N players non-cooperative game. We have established the existence of a Nash equilibrium point (NEP). The willingness of nodes to invest in protection depends on the price of protection. We showed that, when the price of protection is relatively high for all the nodes, the only equilibrium point is that of a completely unprotected network; while if this price is sufficiently low for a single node, it will always invest in protecting itself. We determine bounds on the Price of Anarchy (PoA), that describes how far the NEP is from the global optimum. We have also proposed two methods for steering the network equilibrium, namely by influencing the relative prices and by imposing an upper bound on infection probabilities. A quarantine is another possible measure against the epidemic. A quarantine on a set of network nodes separates them from the rest of the network by removing links. The concept of threshold and the N-intertwined model provides a tool to analyze how quarantine improves the network protection. We studied several different networks from artificially generated to real-world examples using the modularity algorithm. The real-world networks tend to show a better epidemic threshold after clustering than artificially generated graphs. The real-world networks have typically two or three big clusters and several smaller ones, while Barabasi-Albert (BA) and Erdos-Renyi (ER) graphs have several smaller clusters comparable in size. However, the number of removed links in a graph using modularity algorithm is unjustifiably high, suggesting that complete quarantine is not a viable solution for real-world networks.
In recent years, immunization strategies have been developed for stopping epidemics in complex-network-like environments. Yet it still remains a challenge for existing strategies to deal with dynamically-evolving networks that contain community structures, though they are ubiquitous in the real world. In this paper, we examine the performances of an autonomy-oriented distributed search strategy for tackling such networks. The strategy is based on the ideas of self-organization and positive feedback from Autonomy-Oriented Computing (AOC). Our experimental results have shown that autonomous entities in this strategy can collectively find and immunize most highly-connected nodes in a dynamic, community-based network within a few steps.
Research has shown that many social networks come into being hierarchically based on some basic building blocks called communities, within which the social interactions are very intensive, but between which they are very weak. Network community mining algorithms aim at efficiently and effectively discovering all such communities from a given network. Many related methods have been proposed and applied to different areas including social network analysis, gene network analysis and web clustering engine. Most of the existing methods for mining communities are centralized. In this paper, we present a multi-agent based decentralized algorithm, in which a group of autonomous agents work together to mine a network through a proposed self-aggregation and self-organization mechanism. Thanks to its decentralized feature, our method is potentially suitable for dealing with distributed networks, whose global structures are hard to obtain due to their geographical distributions, decentralized controls or huge sizes. The effectiveness of our method has been tested against different benchmark networks.
The term Autonomic Communication (AC) refers to self-managing systems which are capable of supporting self-configuration, self-healing and self-optimization. However, information reflection and collection, lack of centralized control, non-cooperation and so on are just some of the challenges within AC systems. Since many self-* properties (e.g. selfconfiguration, self-optimization, self-healing, and self-protecting) are achieved by a group of autonomous entities that coordinate in a peer-to-peer (P2P) fashion, it has opened the door to migrating research techniques from P2P systems. P2P’s meaning can be better understood with a set of key characteristics similar to AC: Decentralized organization, Self-organizing nature (i.e. adaptability), Resource sharing and aggregation, and Fault-tolerance. However, not all P2P systems are compatible with AC. Unstructured systems are designed more specifically than structured systems for the heterogeneous Internet environment, where the nodes’ persistence and availability are not guaranteed. Motivated by the challenges in AC and based on comprehensive analysis of popular P2P applications, three correlative standards for evaluating the compatibility of a P2P system with AC are presented in this chapter. According to these standards, a novel Efficient, Scalable and Robust (ESR) P2P overlay is proposed. Differing from current structured and unstructured, or meshed and tree-like P2P overlay, the ESR is a whole new three dimensional structure to improve the efficiency of routing, while information exchanges take in immediate neighbors with local information to make the system scalable and fault-tolerant. Furthermore, rather than a complex game theory or incentive mechanism, asimple but effective punish mechanism has been presented based on a new ID structure which can guarantee the continuity of each node’s record in order to discourage negative behavior on an autonomous environment as AC.
This thesis is concerned with stochastic perturbation theory of the symmetric eigen-value problem. In particular, we provide results about the probability of interchanges in the ordering of the eigenvalues and changes in the eigenvectors of symmetric matrices subject to stochastic perturbations. In this analysis we use a novel combination of traditional Numerical Linear Algebra, Perturbation Theory and Probability Theory. The motivation for this study arises from reliability of spectral clustering of networks, when network data is subject to noise. As far as we are aware, there is nothing comparable in the literature. Further, we make conjectures from which we derive an asymptotic relation between the distributions of the largest eigenvalue and the 2-norm of random symmetric ma- trices, whose entries above the main diagonal are independent, identically distributed random variables with probability density functions being symmetric with respect to zero, including matrices from the Gaussian Orthogonal Ensemble (GOE). As far as we know, some of these conjectures are not new (possibly only as conjectures) but we are not aware of any proofs. Also, we consider networks of coupled oscillators. In their analysis we use both, knowledge of dynamical systems and spectral properties of non-negative matrices. As a result, we present an algorithm, which uncovers the \\master-slave" structure of the network. With its help, the analysis of the dynamics and the entrainment of the entire network can be reduced to considering only few of the oscillators, those whose dynamics determine the behaviour of the rest. This can be helpful in large networks exhibiting the \\master-slave" structure. Finally, we consider similarities of spectral clustering with respect to di®erent matrices which can be associated with a given network. In particular, we compare clustering of products of Path graphs with respect to two di®erent matrices: the Laplacian and the Normalised Laplacian matrices of the graph. We make the comparison by constructing a Homotopy between two eigenvalue problems and, using some Linear Algebra techniques, we show that the two matrices give similar spectral clusterings when applied to products of Path graphs.
A network community is a special sub-network that contains a group of nodes sharing similar linked patterns. A distributed network community mining problem (D-NCMP) is concerned with finding all such communities from a distributed network. A variety of applications in WWW and ad-hoc networks such as P2P and sensor networks can be formulated into DNCMPs, in which both resources and controls are distributed and/or decentralized. The problem is difficult for some existing methods to deal with because of the fact that their required global topological representations of distributed networks are hard to obtain. In this paper, we present an autonomy oriented computing (AOC) approach [15], in which the nodes and links of a distributed network are distributed among a group of autonomous agents that collectively find global communities hidden in the network. In doing so, the agents maintain only their respective local views and update them through a proposed self-organization process. The effectiveness of the AOC based approach has been validated using network examples.
Networked systems are continuously growing in scale and complexity. The technical and policy engineering challenges introduced by such a fast growth are currently addressed locally, with limited understanding of their impact on the whole. Such approaches are becoming impractical and insufficient. Next-generation networks need to address these issues by deploying adaptive and self-managing protocols and mechanisms to relax the persistent need for human-driven management. However, achieving these objectives requires conceptual, physical, and logistical modifications to existing systems and protocols. To this end, the traditional top-down approach to network and application design needs to be supplemented by understanding the bottom-up nature of evolving real-world networks.A critical issue that is significantly impacting computer networks and applications is the absence of an in-depth understanding and lack of control over the structural properties, i.e., topology, of large networks. Network topologies define the link relationships between the nodes in the network, and have a direct impact on the performance, resilience, and security of distributed applications. Large scale networks such as the Internet are the result of a time evolving process in which nodes and links between nodes are added, removed, and reconfigured dynamically. This dynamic process takes place in a decentralized manner during which nodes make local adaptations and reconfiguration decisions that optimize local properties. As a result, these local perturbations yield an emergent network that is often unstructured and complex, and have implications at the application-level, particularly impacting routing, search, robustness, and clustering. Understanding the structures emerging out of these adaptations is a complex problem part of the science and study of complexity theory and complex adaptive systems. Tackling this complex problem requires first, identifying canonical metrics to quantify the network topology and second, analyzing the impact of local perturbations of these metrics on the resulting network topology.This thesis identifies three local metrics, transitivity, assortativity, and entropy, and analyzes the impact of their perturbation on the applications of routing, search, robustness, and clustering. The local metric of network entropy is identified as a useful information theoretic measure of homogeneity of a network neighborhood degree. The metric is further used to derive a novel mechanism of clustering detection of the network topology. The overall objective of this thesis is to investigate metrics and mechanisms to better understand the evolution of the network topology and its impact on application-level functionality. The approach is based on concepts of emergence, self-organization and graph theory, and has three key aspects: (1) the identification of canonical local and global graph metrics; (2) the quantitative analysis of the impact of local perturbations on global properties; and (3) the application of the local to global mapping on the problems of routing, search, robustness, and clustering. Adaptations are performed in a decentralized manner in which local nodes use local information to add, remove, or rewire an edge to evolve the topology. Simulations based on annealing optimization are conducted to empirically determine the optimal bounds of the network structures for the selected metrics on selected networks. Further experiments on two modeled networks, random and power-law degree distributed, and two real-world networks, the Gnutella and Canadian Autonomous System networks, show that the impact of optimizing networks with fixed degree distribution on local metrics yield networks with routing, search, robustness, and clustering that are tightly dependent on the network's degree distribution. A key outcome of this thesis is the identification of network entropy minimization as a useful local rewiring strategy to decrease average path length and search cost, while homogenizing the size of network clusters and having a low impact on robustness when applied to power-law degree distributed networks that prevail in real-world networks.