Properties of complex networks Sample Clauses

Properties of complex networks. Networks can be used to describe and analyze many different types of interactions, from those between people (social networks), to the flow of goods across an area (transportation networks), to links between websites (the WWW graph), to thermo- dynamic interaction between particles (statistical mechanics), and so forth. Every net- work is associated with both a graph and an adjacency matrix, allowing the use of tools from graph theory and linear algebra to be used in their analysis. Although there is no precise definition of a complex network, there are a number of properties that complex networks tend to have in common. More information about complex networks can be found in many places, including [40, 83, 84] Complex networks are fundamentally different from random networks generated according to the Xxxxx-Xxxxx xxxxx [00, 36]. There are two closely related variants of this model: in the G(n, m) model, a graph is chosen uniformly at random from the set of all graphs with n nodes and m edges. In the G(n, p) model, a graph with n nodes is constructed by randomly connecting each pair of nodes with probability p. If p is set to p = .nΣm, the two models behave similarly as n tends to infinity. Networks produced by Xxxxx-Xxxxx random models tend to have a Poisson degree-distribution. That is, the majority of nodes tend to have a degree close to the average degree, with relatively few outliers. However, this is not the case for complex networks. It has been shown that many real-world networks follow a power law degree distribution, i.e. that the fraction of nodes of degree k is approximately P (k) ≈ k−γ where often 2 < γ < 3 [5, 51]. Oth- ers have a mixed degree distribution which follows an exponential degree distribution for low-degree nodes and changes into a power law distribution once the node degree increases sufficiently [80, 99]. Networks with these types of degree-distributions are often called scale-free networks. Power law degree-distributions have been observed in many types of networks including biological networks (such as protein-protein inter- action and gene-regulation networks) [11, 42, 43], the internet and world-wide-web [3, 5, 51], and social networks [26]. More information on scale-free networks can be found in [24, 59]. The clustering coefficient of a network measures the propensity of the nodes in the network to form triangles. The clustering coefficient of a node i is given by i C = 2|C3(i)| , di(di − 1) where |C3(i)| is the number of t...