Classics

The Architecture of Complexity

Complex Networks: Augmenting the framework for the study of complex systems

L. A. N. Amaral and J. M. Ottino 2004 The European Physical Journal B, 38: 147-162


Abstract: We briefly describe the toolkit used for studying complex systems: nonlinear dynamics, statistical physics, and network theory. We place particular emphasis on network theory—the topic of this special issue—and its importance in augmenting the framework for the quantitative study of complex systems. In order to illustrate the main issues, we briefly review several areas where network theory has led to significant developments in our understanding of complex systems. Specifically, we discuss changes, arising from network theory, in our understanding of (i) the Internet and other communication networks, (ii) the structure of natural ecosystems, (iii) the spread of diseases and information, (iv) the structure of cellular signalling networks, and (v) infrastructure robustness. Finally, we discuss how complexity requires both new tools and an augmentation of the conceptual framework—including an expanded definition of what is meant by a “quantitative prediction.”


Detecting community structure in networks


Abstract: There has been considerable recent interest in algorithms for ¯nding communities in networks| groups of vertices within which connections are dense, but between which connections are sparser. Here we review the progress that has been made towards this end. We begin by describing some traditional methods of community detection, such as spectral bisection, the Kernighan{Lin algorithm and hierarchical clustering based on similarity measures. None of these methods, however, is ideal for the types of real-world network data with which current research is concerned, such as Internet and web data and biological and social networks. We describe a number of more recent algorithms that appear to work well with these data, including algorithms based on edge betweenness scores, on counts of short loops in networks and on voltage di®erences in resistor networks.


Mixing Patterns in Networks

M. E. J. Newman 2003 Phys. Rev. E, 67(2), 026126


Abstract: We study assortative mixing in networks, the tendency for vertices in networks to be connected to other vertices that are like (or unlike) them in some way. We consider mixing according to discrete characteristics such as language or race in social networks and scalar characteristics such as age. As a special example of the latter we consider mixing according to vertex degree, i.e., according to the number of connections vertices have to other vertices: do gregarious people tend to associate with other gregarious people? We propose a number of measures of assortative mixing appropriate to the various mixing types, and apply them to a variety of real-world networks, showing that assortative mixing is a pervasive phenomenon found in many networks. We also propose several models of assortatively mixed networks, both analytic ones based on generating function methods, and numerical ones based on Monte Carlo graph generation techniques. We use these models to probe the properties of networks as their level of assortativity is varied. In the particular case of mixing by degree, we find strong variation with assortativity in the connectivity of the network and in the resilience of the network to the removal of vertices.


Random Graphs as Models of Networks


Abstract: The random graph of Erd˝os and R´enyi is one of the oldest and best studied models of a network, and possesses the considerable advantage of being exactly solvable for many of its average properties. However, as a model of real-world networks such as the Internet, social networks or biological networks it leaves a lot to be desired. In particular, it differs from real networks in two crucial ways: it lacks network clustering or transitivity, and it has an unrealistic Poissonian degree distribution. In this paper we review some recent work on generalizations of the random graph aimed at correcting these shortcomings. We describe generalized random graph models of both directed and undirected networks that incorporate arbitrary non-Poisson degree distributions, and extensions of these models that incorporate clustering too. We also describe two recent applications of random graph models to the problems of network robustness and of epidemics spreading on contact networks.


Exploring complex networks

S. H. Strogatz 2001 Nature, 410: 268-276


Abstract: The study of networks pervades all of science, from neurobiology to statistical physics. The most basic issues are structural: how does one characterize the wiring diagram of a food web or the Internet or the metabolic network of the bacterium Escherichia coli? Are there any unifying principles underlying their topology? From the perspective of nonlinear dynamics, we would also like to understand how an enormous network of interacting dynamical systems — be they neurons, power stations or lasers — will behave collectively, given their individual dynamics and coupling architecture. Researchers are only now beginning to unravel the structure and dynamics of complex networks.


Collective dynamics of 'small-world' networks

D. J. Watts and S. H. Strogatz 1998 Nature, 393(6684): 440-442

www.leg.ufpr.br_pedro_figures_small-world-p.jpg


Abstract: Networks of coupled dynamical systems have been used to model biological oscillators, Josephson junction arrays,, excitable media, neural networks, spatial games, genetic control networks and many other self-organizing systems. Ordinarily, the connection topology is assumed to be either completely regular or completely random. But many biological, technological and social networks lie somewhere between these two extremes. Here we explore simple models of networks that can be tuned through this middle ground: regular networks `rewired' to introduce increasing amounts of disorder. We find that these systems can be highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs. We call them `small-world' networks, by analogy with the small-world phenomenon, (popularly known as six degrees of separation). The neural network of the worm Caenorhabditis elegans, the power grid of the western United States, and the collaboration graph of film actors are shown to be small-world networks. Models of dynamical systems with small-world coupling display enhanced signal-propagation speed, computational power, and synchronizability. In particular, infectious diseases spread more easily in small-world networks than in regular lattices.


The Strength of Weak Ties

www.leg.ufpr.br_pedro_figures_bridges.jpg

Abstract: Analysis of social networks is suggested as a tool for linking micro and macro levels of sociological theory. The procedure is illustrated by elaboration of the macro implications of one aspect of small-scale interaction: the strength of dyadic ties. It is argued that the degree of overlap of two individuals' friendship networks varies directly with the strength of their tie to one another. The impact of this principle on diffusion of influence and information, mobility opportunity, and community organization is explored. Stress is laid on the cohesive power of weak ties. Most network models deal, implicitly, with strong ties, thus confining their applicability to small, well-defined groups. Emphasis on weak ties lends itself to discussion of relations between groups and to analysis of segments of social structure not easily defined in terms of primary groups.


The strength of a tie is a (probabily linear) combination of the amount of time, the emotional intensity, the intimacy (multual confiding), and the reciprocal services which characterize the tie. Ties are strong, weak, or absent. The stronger the tie between A and B, the larger the proportion of S to whom they will both be tied. The hypothesis is made plausible also by empirical evidence that the stronger the tie connecting two individuals, the more similar they are, in various ways.

In the figure, A-B is a local bridge of degree 3 (above), and of degree 13 (below). As higher is the degree, stronger is the bridge. By the same logic used above, only weak ties may be local bridges.

Tells about the problem of a participant observation to get information of a fairy restricted circle, and therefore do not take into account the weak ties.



QR Code
QR Code wiki:suggested:classics (generated for current page)