Complex Network

From CasGroup

A '''complex network''' forms the backbone of a [[Complex System|complex system]]: the nodes correspond to the agents, entities or parts of the complex system, the edges to the interactions between them. A network is essentially anything which can be represented by a graph: a set of points, nodes or vertices, connected by links, ties or edges. In social networks, the nodes are people, and the ties between them are (variously) acquaintance, friendship, political alliance or professional collaboration. In [[Multi-Agent System|multi-agent systems]], the nodes are agents, and two nodes are connected if they interact with each other. In [[Distributed Computing|distributed computing]] and [[Distributed System|distributed systems]], the nodes are computers or processes, and the links are channels for messages. In the case of the Internet, the nodes are actual machines, and they are joined by a link when they are physically tied together. In the case of the World Wide Web (WWW), the nodes are Web sites, and they are joined when there is a hyper-link from one to the other, see C.R. Shalizi's Article "Growth, Form, Function, Crashes" below. Complex networks are special networks at the edge of chaos where the degree of connectivity is neither regular nor random. The most complex networks of the real world are either small-world networks or scale-free networks at the border between regular and random networks, between order and randomness. == Scale-Free Networks == A network is named scale-free, if it does not have a certain scale. A network with a single scale is similar to grid: every node has the same degree or the same number of links/edges. In a [[scale-free network]], some nodes have a huge number of connections to other nodes, whereas most nodes have only a few. Typically the degree of connectivity can be described by a [[power law]]. According to Mark Newman in [http://arxiv.org/abs/cond-mat/0412004], "when the probability of measuring a particular value of some quantity varies inversely as a power of that value, the quantity is said to follow a power law, also known variously as Zipf's law or the Pareto distribution. The distributions of the sizes of cities, earthquakes, solar flares, moon craters, wars and people's personal fortunes all appear to follow power laws". Scale-free networks and networks which can be described by power-laws are robust against accidental failures but vulnerable to deliberate attacks against hubs and supernodes. == Small-World Networks == A network is called [[small-world network]] by analogy with the [[small-world phenomenon]], (popularly known as [[six degrees of separation]]). The small world hypothesis, which has been tested in experiments (see [http://smallworld.columbia.edu/results.html The Small World Project]), is the idea that two arbitrary people are connected by only six degrees of separation, i.e. the diameter of the corresponding graph of social connections is not much larger than six. Small-world networks have been described first by Duncan J. Watts and Steven H. Strogatz. They appear to be 'small' because they have a small average and characteristic path length, like random or complete graphs. Yet they can be highly clustered, like regular lattices. They can be found at the edge or boundary between regular networks and random networks, and are created from regular networks through rewiring of a few short cuts. == Common characteristics == Both classes of complex networks, small-world and scale-free networks are very similar. They can be found at the edge of chaos between complete randomness and total order. Small-world networks or graphs emerge through the random rewiring of regular grids or lattices: ''you add randomness to order''. Scale-free networks arise in networks if ''you add order to randomness'': instead of considering a pure random growth of a network, you consider a random growth with preferential attachment. The small-world property can be associated with global connectivity and the shortest path length, it arises in regular networks through the addition of random shortcuts. The scale-free property can be associated with local connectivity, it arises in random networks through clustering. == Researchers and Scientists == *[http://amaral.chem-eng.northwestern.edu/ L.A.N. Amaral] *[http://tam.cornell.edu/Strogatz.html Steven Strogatz] *[http://www.nd.edu/~alb/ Albert-László Barabási] *[http://smallworld.columbia.edu/watts.html Duncan J. Watts] *[http://www-personal.umich.edu/~mejn/ Mark Newman] *[http://www.ingenuitygap.com/ Thomas Homer-Dixon] == Links == *[http://www.nd.edu/~networks Self-Organized Networks] *[http://www.sfu.ca/~insna/INSNA/Hot/scale_free.htm Scale-Free and Small-World Networks] == Articles == * C.R. Shalizi, ''Growth, Form, Function, Crashes'', Santa Fe Institute Bulletin 15:2 (2000) [http://discuss.santafe.edu/dynamics/stories/storyReader$54] * C.R. Shalizi, ''Complex Networks'' Notebook-Entry [http://cscs.umich.edu/~crshalizi/notebooks/complex-networks.html] *L.A.N. Amaral and J.M. Ottino , ''Complex networks - Augmenting the framework for the study of complex systems'', Eur. Phys. J. B 38 (2004) 147-162 *A. Barabasi and E. Bonabeau, ''Scale-Free Networks'', Scientific American, May 2003, 50-59 *K. Wiesenfeld, P. Colet, S.H. Strogatz, ''Exploring Complex Networks'', Nature Vol 410 (2001) 268-276 *D.J. Watts and S. H. Strogatz., ''Collective dynamics of 'small-world' networks'', Nature Vol 393 (1998) 440-442 *M. E. J. Newman [http://arxiv.org/abs/cond-mat/0412004 Power laws, Pareto distributions and Zipf's law] *M. E. J. Newman [http://arxiv.org/abs/cond-mat/0303516 The structure and function of complex networks] == Books == *Duncan J. Watts, ''Six Degrees: The Science of a Connected Age'', W. W. Norton & Company, 2003, ISBN 0393041425 *Duncan J. Watts, ''Small Worlds : The Dynamics of Networks between Order and Randomness'', Princeton University Press, 2003, ISBN 0691117047 *Albert-László Barabási, ''Linked: How Everything Is Connected to Everything Else and What It Means'', Plume, 2003, ISBN 0452284392 *Mark Buchanan, ''Nexus: Small Worlds and the Groundbreaking Theory of Networks'', W. W. Norton & Company, 2003, ISBN 0393324427 *E. Ben-Naim, H. Frauenfelder, Z. Toroczkai, ''Complex Networks'', Springer, 2004, ISBN 3540223541

Return to Complex Network.