Blockchain Papers

Marie Larsson Linton, Ernie G. S. Teo, Elisabeth Bommes, Cheng–Ying Chen · 5 authors

No abstract is available for this record.

Johannes Göbel, Paul Keeler, A. E. Krzesinski, Peter Taylor

In the context of the `selfish-mine' strategy proposed by Eyal and Sirer, we study the effect of propagation delay on the evolution of the Bitcoin blockchain. First, we use a simplified Markov model that tracks the contrasting states of belief about the blockchain of a small pool of miners and the `rest of the community' to establish that the use of block-hiding strategies, such as selfish-mine, causes the rate of production of orphan blocks to increase. Then we use a spatial Poisson process model to study values of Eyal and Sirer's parameter $γ$, which denotes the proportion of the honest community that mine on a previously-secret block released by the pool in response to the mining of a block by the honest community. Finally, we use discrete-event simulation to study the behaviour of a network of Bitcoin miners, a proportion of which is colluding in using the selfish-mine strategy, under the assumption that there is a propagation delay in the communication of information between miners.

Sören Adamsson, Muhammad Hammad Nadeem Tahir

This study analyses the growing area of research that explores the evolution of technology from social and cognition perspective – and how the design and various implementation of technology are being shaped by the factors related to social-constructivism and beliefs systems of individuals. The newly developed technological phenomena of Cryptocurrency – the digital currency for all, provides us with an excellent case to study. We apply social and cognitive processes to understand technology trajectories across the life cycle of cryptocurrency. We thus deepen our understanding by analyzing why and what causes the various technological trajectories in the era of ferment and concluding our research by deriving various technological 'themes'. – that might evolve as the phenomena of cryptocurrency while moving towards the era of dominant design.

Imre Szücs, Attila Kiss

The role of Bitcoin -open source virtual peer-to-peer money -in finance has become more important with the increasing acceptance by service providers. Nevertheless several financial institutes and governments explain their revulsion against Bitcoin, due to the unknown financial risks behind it which could have an impact on the global financial world. In this paper we examine the relationship between BTC/USD exchange rate and the network properties of the underlying transactional graph. The main goal of our research is to get a deeper understanding on the behavior of Bitcoin and ground further researches on exploring the financial risk. To characterize the transactional graph network analysis techniques, while to examine the relationship data mining and time series analysis techniques were used.

Steve Y. Yang, Jinhyoung Kim

Bit coin, as the foundation for a secure electronic payment system, has drawn broad interests from researchers in recent years. In this paper, we analyze a comprehensive Bit coin transaction dataset and investigate the interrelationship between the flow of Bit coin transactions and its price movement. Using network theory, we examine a few complexity measures of the Bit coin transaction flow networks, and we model the joint dynamic relationship between these complexity measures and Bit coin market variables such as return and volatility. We find that a particular complexity measure of the Bit coin transaction network flow is significantly correlated with the Bit coin market return and volatility. More specifically we document that the residual diversity or freedom of Bit coin network flow scaled by the total system throughput can significantly improve the predictability of Bit coin market return and volatility.

Xianyi Gao, Gradeigh D. Clark, Janne Lindqvist

Digital currencies represent a new method for exchange and investment that differs strongly from any other fiat money seen throughout history. A digital currency makes it possible to perform all financial transactions without the intervention of a third party to act as an arbiter of verification; payments can be made between two people with degrees of anonymity, across continents, at any denomination, and without any transaction fees going to a central authority. The most successful example of this is Bitcoin, introduced in 2008, which has experienced a recent boom of popularity, media attention, and investment. With this surge of attention, we became interested in finding out how people both inside and outside the Bitcoin community perceive Bitcoin -- what do they think of it, how do they feel, and how knowledgeable they are. Towards this end, we conducted the first interview study (N = 20) with participants to discuss Bitcoin and other related financial topics. Some of our major findings include: not understanding how Bitcoin works is not a barrier for entry, although non-user participants claim it would be for them and that user participants are in a state of cognitive dissonance concerning the role of governments in the system. Our findings, overall, contribute to knowledge concerning Bitcoin and attitudes towards digital currencies in general.

Nicholas Roth

Bitcoin is an emerging crypto-currency, which is wrapped in mystery and controversy. The goal is to transform how we transfer payments. The current approach for sending money from one remote party to another is via bank deposit and transfer by check or bank transfer. PayPal and other services were developed to provide faster payments to verified individuals, but each layer in the transaction adds time, cost, and/or risk to the transaction. Users of this new digital currency proclaim the benefits of security, anonymity, and efficiency for making transactions. The functionality and structure of the Bitcoin Network is complex and often attacked for not being a suitable replacement for currency. An independent understanding can be developed of the composite Bitcoin Financial Systems of Systems architecture by considering the challenges any System of System would face. A functional analysis, employing the Systems Modeling Language (SysML), is performed on the Bitcoin System of Systems architecture to help gain an understanding of the structure and functionality, and how that relates to the key actors and use cases, for determining if the users’ expectations are aligned with the architecture.

Dániel Kondor, István Csabai, János Szüle, Márton Pósfai · 5 authors

A main focus in economics research is understanding the time series of prices of goods and assets. While statistical models using only the properties of the time series itself have been successful in many aspects, we expect to gain a better understanding of the phenomena involved if we can model the underlying system of interacting agents. In this article, we consider the history of Bitcoin, a novel digital currency system, for which the complete list of transactions is available for analysis. Using this dataset, we reconstruct the transaction network between users and analyze changes in the structure of the subgraph induced by the most active users. Our approach is based on the unsupervised identification of important features of the time variation of the network. Applying the widely used method of Principal Component Analysis to the matrix constructed from snapshots of the network at different times, we are able to show how structural changes in the network accompany significant changes in the exchange price of bitcoins.

David García, Claudio J. Tessone, Pavlin Mavrodiev, Nicolas Perony

What is the role of social interactions in the creation of price bubbles? Answering this question requires obtaining collective behavioural traces generated by the activity of a large number of actors. Digital currencies offer a unique possibility to measure socio-economic signals from such digital traces. Here, we focus on Bitcoin, the most popular cryptocurrency. Bitcoin has experienced periods of rapid increase in exchange rates (price) followed by sharp decline; we hypothesise that these fluctuations are largely driven by the interplay between different social phenomena. We thus quantify four socio-economic signals about Bitcoin from large data sets: price on on-line exchanges, volume of word-of-mouth communication in on-line social media, volume of information search, and user base growth. By using vector autoregression, we identify two positive feedback loops that lead to price bubbles in the absence of exogenous stimuli: one driven by word of mouth, and the other by new Bitcoin adopters. We also observe that spikes in information search, presumably linked to external events, precede drastic price declines. Understanding the interplay between the socio-economic signals we measured can lead to applications beyond cryptocurrencies to other phenomena which leave digital footprints, such as on-line social network usage.

Dániel Kondor, Márton Pósfai, István Csabai, Gábor Vattay

The possibility to analyze everyday monetary transactions is limited by the scarcity of available data, as this kind of information is usually considered highly sensitive. Present econophysics models are usually employed on presumed random networks of interacting agents, and only macroscopic properties (e.g. the resulting wealth distribution) are compared to real-world data. In this paper, we analyze BitCoin, which is a novel digital currency system, where the complete list of transactions is publicly available. Using this dataset, we reconstruct the network of transactions, and extract the time and amount of each payment. We analyze the structure of the transaction network by measuring network characteristics over time, such as the degree distribution, degree correlations and clustering. We find that linear preferential attachment drives the growth of the network. We also study the dynamics taking place on the transaction network, i.e. the flow of money. We measure temporal patterns and the wealth accumulation. Investigating the microscopic statistics of money movement, we find that sublinear preferential attachment governs the evolution of the wealth distribution. We report a scaling relation between the degree and wealth associated to individual nodes.

Jing Huang, Bo Yang, Di Jin, Yi Yang

No abstract is available for this record.

Marco LiCalzi, Andrea Collevecchio

Abstract. We study the probability that two or more agents can attain common knowledge of nontrivial events when the size of the state space grows large. We adopt the standard epistemic model where the knowledge of an agent is represented by a partition of the state space. Each agent is endowed with a partition generated by a random scheme consistent with his cognitive capacity. Assuming that agents ’ partitions are independently distributed, we prove that the asymptotic probability of nontrivial common knowledge undergoes a phase transition. Regardless of the number of agents, when their cognitive capacity is sufficiently large, the probability goes to one; and when it is small, it goes to zero. Our proofs rely on a graph-theoretic characterization of common knowledge that has independent interest.

Carlos Gershenson

The following news item is taken in part from the July 22, 2010 issue of The Economist titled “Agents of change,” by Philip Ball. Conventional economic models failed to foresee the financial crisis. Could agent-based modeling (ABM) do better? ABM does not assume that the economy can achieve a settled equilibrium. No order or design is imposed on the economy from the top down. Unlike many models, ABMs are not populated with “representative agents”: identical traders, firms, or households whose individual behavior mirrors the economy as a whole. Rather, an ABM uses a bottom-up approach which assigns particular behavioral rules to each agent. For example, some may believe that prices reflect fundamentals whereas others may rely on empirical observations of past price trends. A link to this article can be found at http://www.economist.com/node/16636121?story_id=16636121. The following news item is taken in part from the August 5, 2010 issue of Nature titled “Link communities reveal multiscale complexity in networks,” by Yong-Yeol Ahn, James P. Bagrow, and Sune Lehmann. Here, we reinvent communities as groups of links rather than nodes and show that this unorthodox approach successfully reconciles the antagonistic organizing principles of overlapping communities and hierarchy. In contrast to the existing literature, which has entirely focused on grouping nodes, link communities naturally incorporate overlap while revealing hierarchical organization. We find relevant link communities in many networks. A link to this article can be found at http://dx.doi.org/10.1038/nature09182. The following news item is taken in part from the August 12, 2010 issue of Science titled “Stability of Ecological Communities and the Architecture of Mutualistic and Trophic Networks,” by Elisa Thébault and Colin Fontaine. Research on the relationship between the architecture of ecological networks and community stability has mainly focused on one type of interaction at a time, making difficult any comparison between different network types. We used a theoretical approach to show that the network architecture favoring stability fundamentally differs between trophic and mutualistic networks. A highly connected and nested architecture promotes community stability in mutualistic networks, whereas the stability of trophic networks is enhanced in compartmented and weakly connected architectures. These theoretical predictions are supported by a meta-analysis on the architecture of a large series of real pollination (mutualistic) and herbivory (trophic) networks. We conclude that strong variations in the stability of architectural patterns constrain ecological networks toward different architectures, depending on the type of interaction. A link to this article can be found at http://dx.doi.org/10.1126/science.1188321. The following news item is taken in part from the August 5, 2010 issue of arXiv titled “Emergence of Zipf's Law in the Evolution of Communication,” by Bernat Corominas-Murtra, Jordi Fortuny, and Ricard V. Solé. Zipf's law seems to be ubiquitous in human languages and appears to be a universal property of complex communicating systems. Following an early proposal made by Zipf concerning the presence of a tension between the efforts of speaker and hearer in a communication system, we introduce evolution by means of a variational approach to the problem based on Kullback's Minimum Discrimination of Information Principle. Using a formalism fully embedded in the framework of information theory, we demonstrate that Zipf's law is the only expected outcome of an evolving, communicative system under a rigorous definition of the communicative tension described by Zipf. A link to this article can be found at http://arXiv.org/abs/1008.0938. The following news item is taken in part from the August 26, 2010 issue of Nature titled “The evolution of eusociality,” by Martin A. Nowak, Corina E. Tarnita, and Edward O. Wilson. Eusociality, in which some individuals reduce their own lifetime reproductive potential to raise the offspring of others, underlies the most advanced forms of social organization and the ecologically dominant role of social insects and humans. For the past four decades kin selection theory, based on the concept of inclusive fitness, has been the major theoretical attempt to explain the evolution of eusociality. Here, we show the limitations of this approach. We argue that standard natural selection theory in the context of precise models of population structure represents a simpler and superior approach, allows the evaluation of multiple competing hypotheses, and provides an exact framework for interpreting empirical observations. A link to this article can be found at http://dx.doi.org/10.1038/nature09205. The following news item is taken in part from the August 27, 2010 issue of Science titled “Optimally Interacting Minds,” by Bahador Bahrami, Karsten Olsen, Peter E. Latham, Andreas Roepstorff, Geraint Rees, and Chris D. Frith. In everyday life, many people believe that two heads are better than one. Our ability to solve problems together appears to be fundamental to the current dominance and future survival of the human species. But are two heads really better than one? We addressed this question in the context of a collective low-level perceptual decision-making task. For two observers of nearly equal visual sensitivity, two heads were definitely better than one, provided they were given the opportunity to communicate freely, even in the absence of any feedback about decision outcomes. But for observers with very different visual sensitivities, two heads were actually worse than the better one. A link to this article can be found at http://dx.doi.org/10.1126/science.1185718. The following news item is taken in part from the August 19, 2010 issue of Nature titled “Promiscuity and the evolutionary transition to complex societies,” by Charlie K. Cornwallis, Stuart A. West, Katie E. Davis, and Ashleigh S. Griffin. A phylogenetic analysis of breeding behavior in birds shows that cooperation is more likely when promiscuity is low—a circumstance in which helpers can be more certain that they are offering aid to relatives. Intermediate levels of promiscuity favor the ability to distinguish relatives from nonrelatives. At high levels of promiscuity, no form of cooperation is favored. Levels of promiscuity therefore provide an explanation for differences between species in levels of cooperation. A link to this article can be found at http://dx.doi.org/10.1038/nature09335. The following news item is taken in part from the August 23, 2010 issue of arXiv titled “Network Complexity of Foodwebs,” by Russell K. Standish. In previous work, I have developed an information theoretic complexity measure of networks. When applied to several real world foodwebs, there is a distinct difference in complexity between the real foodweb, and randomized control networks obtained by shuffling the network links. One hypothesis is that this complexity surplus represents information captured by the evolutionary process that generated the network. In this paper, I test this idea by applying the same complexity measure to several well-known artificial life models that exhibit ecological networks: Tierra, EcoLab, and Webworld. Contrary to what was found in real networks, the artificial life-generated foodwebs had little information difference between itself and randomly shuffled versions. A link to this article can be found at http://arXiv.org/abs/1008.3800. The following news item is taken in part from the August, 2010 issue of PLoS ONE titled “A New Measure of Centrality for Brain Networks,” by Karen E. Joyce, Paul J. Laurienti, Jonathan H. Burdette, and Satoru Hayasaka. Recent developments in network theory have allowed for the study of the structure and function of the human brain in terms of a network of interconnected components. In the work presented here, we propose a new centrality metric called leverage centrality that considers the extent of connectivity of a node relative to the connectivity of its neighbors. The leverage centrality of a node in a network is determined by the extent to which its immediate neighbors rely on that node for information. Degree, betweenness, eigenvector, and leverage centrality were compared using functional brain networks generated from healthy volunteers. We propose that this metric may be able to identify critical nodes that are highly influential within the network. A link to this article can be found at http://dx.doi.org/10.1371/journal.pone.0012200. The following news item is taken in part from the September 10, 2010 issue of Science titled “Biodiversity Conservation: Challenges Beyond 2010,” by Michael R.W. Rands, William M. Adams, Leon Bennun, Stuart H.M. Butchart, Andrew Clements, David Coomes, Abigail Entwistle, Ian Hodge, Valerie Kapos, Jörn P.W. Scharlemann, William J. Sutherland, and Bhaskar Vira. The continued growth of human populations and of per capita consumption have resulted in unsustainable exploitation of Earth's biological diversity, exacerbated by climate change, ocean acidification, and other anthropogenic environmental impacts. We argue that effective conservation of biodiversity is essential for human survival and the maintenance of ecosystem processes. Despite some conservation successes (especially at local scales) and increasing public and government interest in living sustainably, biodiversity continues to decline. Moving beyond 2010, successful conservation approaches need to be reinforced and adequately financed. However, in addition, more radical changes are required that recognize biodiversity as a global public good, that integrate biodiversity conservation into policies and decision frameworks for resource production and consumption, and that focus on wider institutional and societal changes to enable more effective implementation of policy. A link to this article can be found at http://dx.doi.org/10.1126/science.1189138. The following news item is taken in part from the September 6, 2010 issue of arXiv titled “Are large complex economic systems unstable?,” by Sitabhra Sinha. Although classical economic theory is based on the concept of stable equilibrium, real economic systems appear to be always out of equilibrium. Indeed, they share many of the dynamical features of other complex systems, e.g., ecological foodwebs. We focus on the relation between increasing complexity of the economic network and its stability with respect to small perturbations in the dynamical variables associated with the constituent nodes. Inherent delays and multiple time scales suggest that economic systems will be more likely to exhibit instabilities as their complexity is increased even though the speed at which transactions are conducted has increased many fold through technological developments. Analogous to the birth of nonlinear dynamics from Poincare's work on the question of whether the solar system is stable, we suggest that similar theoretical developments may arise from efforts by econophysicists to understand the mechanisms by which instabilities arise in the economy. A link to this article can be found at http://arXiv.org/abs/1009.0972. The following news item is taken in part from the September 3, 2010 issue of Science titled “The Spread of Behavior in an Online Social Network Experiment,” by Damon Centola. How do social networks affect the spread of behavior? A popular hypothesis states that networks with many clustered ties and a high degree of separation will be less effective for behavioral diffusion than networks in which locally redundant ties are rewired to provide shortcuts across the social space. A competing hypothesis argues that when behaviors require social reinforcement, a network with more clustering may be more advantageous, even if the network as a whole has a larger diameter. I investigated the effects of network structure on diffusion by studying the spread of health behavior through artificially structured online communities. Individual adoption was much more likely when participants received social reinforcement from multiple neighbors in the social network. The behavior spread farther and faster across clustered-lattice networks than across corresponding random networks. A link to this article can be found at http://dx.doi.org/10.1126/science.1185231. The following news item is taken in part from the September, 2010 issue of Cognitive Science titled “Language Acquisition Meets Language Evolution,” by Nick Chater and Morten H. Christiansen. Recent research suggests that language evolution is a process of cultural change, in which linguistic structures are shaped through repeated cycles of learning and use by domain-general mechanisms. This paper draws out the implications of this viewpoint for understanding the problem of language acquisition, which is cast in a new, and much more tractable, form. In essence, the child faces a problem of induction, where the objective is to coordinate with others (C-induction), rather than to model the structure of the natural world (N-induction). We argue that, of the two, C-induction is dramatically easier. More broadly, we argue that understanding the acquisition of any cultural form, whether linguistic or otherwise, during development, requires considering the corresponding question of how that cultural form arose through processes of cultural evolution. This perspective helps resolve the “logical” problem of language acquisition and has far-reaching implications for evolutionary psychology. A link to this article can be found at http://dx.doi.org/10.1111/j.1551-6709.2009.01049.x. The following news item is taken in part from the September 8, 2010 issue of Nature titled “Early warning signals of extinction in deteriorating environments,” by John M. Drake and Blaine D. Griffen. Although understanding the causes of population extinction has been a central problem in theoretical biology for decades, the ability to anticipate extinction has remained elusive. Here, we argue that the causes of a population's decline are central to the predictability of its extinction. Specifically, environmental degradation may cause a tipping point in population dynamics, corresponding to a bifurcation in the underlying population growth equations, beyond which decline to extinction is almost certain. A link to this article can be found at http://dx.doi.org/10.1038/nature09389. The following news item is taken in part from the September, 2010 issue of SFI Working Papers titled “Self-Stabilizing Decentralized Signal Control of Realistic, Saturated Network Traffic,” by Stefan Lammer and Dirk Helbing. A coordination of vehicle flows is usually reached by a cyclical operation of traffic lights, and by synchronizing these cycles. However, the typical conditions, for which traffic lights are normally optimized for, never occur exactly. Large fluctuations in the number of vehicles arriving during one cycle time may lead to an inefficient usage of green times, which are often either too short or too long. The method we propose here allows for variable adjustments not only of the duration, but also of the order of green phases, while it reaches at least the same intersection throughput capacity as an optimized fixed-time controller. A link to this article can be found at http://www.santafe.edu/research/working-papers/abstract/67d8c997e841b3a 2e253aacad4e2851b/. The following news item is taken in part from the September, 2010 issue of SFI Working Papers titled “Information Driven Self-Organization: The Dynamical System Approach to Autonomous Robot Behavior,” by Nihat Ay, Ralf Der, and Mikhail Prokopenko. In recent years, information theory has come into the focus of researchers interested in the sensorimotor dynamics of both robots and living beings. One root for these approaches is the idea that living beings are information processing systems and that the optimization of these processes should be an evolutionary advantage. Apart from these more principal questions, there is much interest recently in the question how a robot can be equipped with an internal drive for innovation or curiosity that may serve as a drive for an open ended, self-determined development of the robot. The success of these approaches depends essentially on the choice of a convenient measure for the information. This paper studies in some detail the use of the predictive information of the sensorimotor process. A link to this article can be found at http://www.santafe.edu/research/working-papers/abstract/b67e300041 30f486027ea324c080a058/. Winter Meeting on Statistical Physics, Taxco, Guerrero, Mexico, 2011/1/4-7 https://sites.google.com/site/wintermeetingstatphys IWSOS 2011, Fifth International Workshop on Self-Organizing Systems, Karlsruhe, Germany, 2011/02/23-25 http://iwsos2011.tm.kit.edu/ IEEE Symposium Series on Computational Intelligence—SSCI 2011, Paris, France, 2011/04/11-15 http://www.ieee-ssci.org/ EVOSTAR 2011, Torino, Italy, 2011/4/27-29 http://evostar.org/ International Conference on Complex Systems (ICCS 2011), Boston, MA, USA, 2011/06/26-07/01 http://www. necsi.edu/events/iccs2011/ GECCO 2011: Genetic and Evolutionary Computation Conference, Dublin, Ireland, 2011/07/12-16 http://www. sigevo.org/gecco-2011/ IJCAI 2011, The 22nd International Joint Conference on Artificial Intelligence, Barcelona, Spain, 2011/07/16-22 http://ijcai-11.iiia.csic.es/ ECAL 11: European Conference on Artificial Life, Paris, France, 2011/08/8-12 http://www.ecal11.org/

Jasmina Omić

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.

Zhivko Stoyanov

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.

V. Matossian

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.