Error and attack tolerance of complex networks

Error and attack tolerance of complex networks
Reka Albert, Hawoong Jeong & Albert-Laszlo Barabasi
Department of Physics, University of Notre Dame, USA

---

Content::

• two major complex networks classes based on their connectivity distribution P(k), giving the probability that a node in the network is connected to k other nodes:
• • Exponential networks: P(k) that peaks at an average <k> and decays exponentially for large k. e.g. random graph model of Erdos and Renyi, [1][2] and the small-world model ofWatts and Strogatz[3], fairly homogeneous network, i.e. each node has approximately the same number of links
  • Scale-free networks: P(k) decays as a power-law, that is P(k) <-> K ^(-r), e.g. internet, WWW, free of a characteristic scale, inhomogeneous networks, i.e.
• Difference: highly connected nodes are practically prohibited in exponential networks, but is statistically significant in scale-free networks. e.g. in an example shown in the paper, in the exponential network only 27% of the nodes are reached by the five most connected nodes, in the scale-free network more than 60% are reached, demonstrating the importance of the connected nodes in the scale-free network.
• Scale-free network is reproduce by model with growth and preferential attachment. i.e. new node is connect to existed node i with probability direct ratio to node i's connectivity.
• By tracking the change on network's diameter, this paper analyze the impact of attach and error tolerance of network.

Info:

• Use network visualization Pajek program for large network analysis: http://vlado.fmf.uni-lj.si/pub/networks/pajek/pajekman.htm.
• Use topological map of the Internet, containing 6,209 nodes and 12,200 links (<k> = 3:4) collected by the National Laboratory for Applied Network Research hhttp://moat.nlanr.net/Routing/rawdata/
• 1999 data shown parameter r of Internet is 2.48