Complex Network
From CasGroup
(→Common characteristics) |
|||
| Line 1: | Line 1: | ||
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. | 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 | A network is named scale-free, if it does not have a certain scale. A network | ||
| Line 7: | Line 7: | ||
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]]. | 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], | + | 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. | 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 == | == Small-World Networks == | ||
| Line 37: | Line 28: | ||
networks if ''you add order to randomness'': instead of considering | networks if ''you add order to randomness'': instead of considering | ||
a pure random growth of a network, you consider a random growth with | a pure random growth of a network, you consider a random growth with | ||
| - | preferential attachment. | + | [[Preferential attachment|preferential attachment]]. |
The small-world property can be associated with global connectivity | The small-world property can be associated with global connectivity | ||
