| Part of a series on | ||||
| Network science | ||||
|---|---|---|---|---|
| Network types | ||||
| Graphs | ||||
| ||||
| Models | ||||
| ||||
| ||||
Hierarchical network models are iterative algorithms for creating networks which are able to reproduce the unique properties of the scale-free topology and the high clustering of the nodes at the same time. These characteristics are widely observed in nature, from biology to language to some social networks.
The hierarchical network model is part of the scale-free model family sharing their main property of having proportionally more hubs among the nodes than by random generation; however, it significantly differs from the other similar models (Barabási–Albert, Watts–Strogatz) in the distribution of the nodes' clustering coefficients: as other models would predict a constant clustering coefficient as a function of the degree of the node, in hierarchical models nodes with more links are expected to have a lower clustering coefficient. Moreover, while the Barabási-Albert model predicts a decreasing average clustering coefficient as the number of nodes increases, in the case of the hierarchical models there is no relationship between the size of the network and its average clustering coefficient.
The development of hierarchical network models was mainly motivated by the failure of the other scale-free models in incorporating the scale-free topology and high clustering into one single model. Since several real-life networks (metabolic networks, the protein interaction network, the World Wide Web or some social networks) exhibit such properties, different hierarchical topologies were introduced in order to account for these various characteristics.
Hierarchical network models are usually derived in an iterative way by replicating the initial cluster of the network according to a certain rule. For instance, consider an initial network of five fully interconnected nodes (N=5). As a next step, create four replicas of this cluster and connect the peripheral nodes of each replica to the central node of the original cluster (N=25). This step can be repeated indefinitely, thereby for any k steps the number of nodes in the system can be derived by N=5k+1. [1]
Of course there have been several different ways for creating hierarchical systems proposed in the literature. These systems generally differ in the structure of the initial cluster as well as in the degree of expansion which is often referred to as the replication factor of the model. [2] [3]
Being part of the scale-free model family, the degree distribution of the hierarchical network model follows the power law meaning that a randomly selected node in the network has k edges with a probability
where c is a constant and γ is the degree exponent. In most real world networks exhibiting scale-free properties γ lies in the interval [2,3]. [4]
As a specific result for hierarchical models it has been shown that the degree exponent of the distribution function can be calculated as
where M represents the replication factor of the model. [5]
In contrast to the other scale-free models (Erdős–Rényi, Barabási–Albert, Watts–Strogatz) where the clustering coefficient is independent of the degree of a specific node, in hierarchical networks the clustering coefficient can be expressed as a function of the degree in the following way:
It has been analytically shown that in deterministic scale-free networks the exponent β takes the value of 1. [2]
Based on the actor database available at www.IMDb.com the network is defined by Hollywood actors who are connected to each other if they both appeared in the same movie, resulting in a data set of 392,340 nodes and 15,347,957 edges. As earlier studies have shown, this network exhibits scale-free properties at least for high values of k. Moreover, the clustering coefficients seem to follow the required scaling law with the parameter -1 providing evidence for the hierarchical topology of the network. Intuitively, one-performance actors have by definition a clustering coefficient of one while actors starring in several movies are highly unlikely to work with the same crew which in general results in a decreasing clustering coefficient as the number of co-stars grows. [1]
Words can be regarded as network if one specifies the linkage criteria between them. Defining links as appearance as a synonym in the Merriam-Webster dictionary a semantic web of 182,853 nodes with 317,658 edges was constructed. As it turned out, the obtained network of words indeed follows a power law in its degree distribution while the distribution of the clustering coefficient indicates that the underlying web follows a hierarchical structure with γ=3.25 and β=1. [1]
By mapping the www.nd.edu domain a network of 325,729 nodes and 1,497,135 edges was obtained whose degree distribution followed a power law with γout=2.45 and γin=2.1 for the out- and in-degrees, respectively. The evidence for the scaling law distribution of the clustering coefficients is significantly weaker than in the previous cases although there is a clearly visible declining pattern in the distribution of C(k) indicating that the more links a domain has the less interconnected the linked/linking web pages are. [1] [6]
The domain network, i.e. the internet at the autonomous system (AS) level where the administrative domains are said to be connected in case there is a router which connects them, was found to comprise 65,520 nodes and 24,412 links between them and exhibit the properties of a scale-free network. The sample distribution of the clustering coefficients was fitted by the scaling function C(k)~k−0.75 whose exponent is (in absolute terms) somewhat smaller than the theoretical parameter for deterministic scale-free networks. [1] [7]
A scale-free network is a network whose degree distribution follows a power law, at least asymptotically. That is, the fraction P(k) of nodes in the network having k connections to other nodes goes for large values of k as
A small-world network is a mathematical graph in which most nodes are not neighbors of one another, but the neighbors of any given node are likely to be neighbors of each other. Due to this, most neighboring nodes can be reached from every other node by a small number of hops or steps. Specifically, a small-world network is defined to be a network where the typical distance L between two randomly chosen nodes grows proportionally to the logarithm of the number of nodes N in the network, that is:
In the context of network theory, a complex network is a graph (network) with non-trivial topological features—features that do not occur in simple networks such as lattices or random graphs but often occur in networks representing real systems. The study of complex networks is a young and active area of scientific research inspired largely by empirical findings of real-world networks such as computer networks, biological networks, technological networks, brain networks, climate networks and social networks.
In the study of graphs and networks, the degree of a node in a network is the number of connections it has to other nodes and the degree distribution is the probability distribution of these degrees over the whole network.
The Barabási–Albert (BA) model is an algorithm for generating random scale-free networks using a preferential attachment mechanism. Several natural and human-made systems, including the Internet, the World Wide Web, citation networks, and some social networks are thought to be approximately scale-free and certainly contain few nodes with unusually high degree as compared to the other nodes of the network. The BA model tries to explain the existence of such nodes in real networks. The algorithm is named for its inventors Albert-László Barabási and Réka Albert.
The Watts–Strogatz model is a random graph generation model that produces graphs with small-world properties, including short average path lengths and high clustering. It was proposed by Duncan J. Watts and Steven Strogatz in their article published in 1998 in the Nature scientific journal. The model also became known as the (Watts) beta model after Watts used to formulate it in his popular science book Six Degrees.
In complex network theory, the fitness model is a model of the evolution of a network: how the links between nodes change over time depends on the fitness of nodes. Fitter nodes attract more links at the expense of less fit nodes.
In applied probability theory, the Simon model is a class of stochastic models that results in a power-law distribution function. It was proposed by Herbert A. Simon to account for the wide range of empirical distributions following a power-law. It models the dynamics of a system of elements with associated counters. In this model the dynamics of the system is based on constant growth via addition of new elements as well as incrementing the counters at a rate proportional to their current values.
A Boolean network consists of a discrete set of boolean variables each of which has a Boolean function assigned to it which takes inputs from a subset of those variables and output that determines the state of the variable it is assigned to. This set of functions in effect determines a topology (connectivity) on the set of variables, which then become nodes in a network. Usually, the dynamics of the system is taken as a discrete time series where the state of the entire network at time t+1 is determined by evaluating each variable's function on the state of the network at time t. This may be done synchronously or asynchronously.
Network science is an academic field which studies complex networks such as telecommunication networks, computer networks, biological networks, cognitive and semantic networks, and social networks, considering distinct elements or actors represented by nodes and the connections between the elements or actors as links. The field draws on theories and methods including graph theory from mathematics, statistical mechanics from physics, data mining and information visualization from computer science, inferential modeling from statistics, and social structure from sociology. The United States National Research Council defines network science as "the study of network representations of physical, biological, and social phenomena leading to predictive models of these phenomena."
In the context of the physical and mathematical theory of percolation, a percolation transition is characterized by a set of universal critical exponents, which describe the fractal properties of the percolating medium at large scales and sufficiently close to the transition. The exponents are universal in the sense that they only depend on the type of percolation model and on the space dimension. They are expected to not depend on microscopic details such as the lattice structure, or whether site or bond percolation is considered. This article deals with the critical exponents of random percolation.
Evolving networks are networks that change as a function of time. They are a natural extension of network science since almost all real world networks evolve over time, either by adding or removing nodes or links over time. Often all of these processes occur simultaneously, such as in social networks where people make and lose friends over time, thereby creating and destroying edges, and some people become part of new social networks or leave their networks, changing the nodes in the network. Evolving network concepts build on established network theory and are now being introduced into studying networks in many diverse fields.
In social network analysis, the co-stardom network represents the collaboration graph of film actors i.e. movie stars. The co-stardom network can be represented by an undirected graph of nodes and links. Nodes correspond to the movie star actors and two nodes are linked if they co-starred (performed) in the same movie. The links are un-directed, and can be weighted or not depending on the goals of study. If the number of times two actors appeared in a movie is needed, links are assigned weights. The co-stardom network can also be represented by a bipartite graph where nodes are of two types: actors and movies. And edges connect different types of nodes if they have a relationship. Initially the network was found to have a small-world property. Afterwards, it was discovered that it exhibits a scale-free (power-law) behavior.
Price's model is a mathematical model for the growth of citation networks. It was the first model which generalized the Simon model to be used for networks, especially for growing networks. Price's model belongs to the broader class of network growing models whose primary target is to explain the origination of networks with strongly skewed degree distributions. The model picked up the ideas of the Simon model reflecting the concept of rich get richer, also known as the Matthew effect. Price took the example of a network of citations between scientific papers and expressed its properties. His idea was that the way an old vertex gets new edges should be proportional to the number of existing edges the vertex already has. This was referred to as cumulative advantage, now also known as preferential attachment. Price's work is also significant in providing the first known example of a scale-free network. His ideas were used to describe many real-world networks such as the Web.
Robustness, the ability to withstand failures and perturbations, is a critical attribute of many complex systems including complex networks.
The Bianconi–Barabási model is a model in network science that explains the growth of complex evolving networks. This model can explain that nodes with different characteristics acquire links at different rates. It predicts that a node's growth depends on its fitness and can calculate the degree distribution. The Bianconi–Barabási model is named after its inventors Ginestra Bianconi and Albert-László Barabási. This model is a variant of the Barabási–Albert model. The model can be mapped to a Bose gas and this mapping can predict a topological phase transition between a "rich-get-richer" phase and a "winner-takes-all" phase.
In network science, a hub is a node with a number of links that greatly exceeds the average. Emergence of hubs is a consequence of a scale-free property of networks. While hubs cannot be observed in a random network, they are expected to emerge in scale-free networks. The uprise of hubs in scale-free networks is associated with power-law distribution. Hubs have a significant impact on the network topology. Hubs can be found in many real networks, such as the brain or the Internet.
In a scale-free network the degree distribution follows a power law function. In some empirical examples this power-law fits the degree distribution well only in the high degree region, however for small degree nodes the empirical degree-distribution deviates from it. See for example the network of scientific citations. This deviation of the observed degree-distribution from the theoretical prediction at the low-degree region is often referred as low-degree saturation.
The initial attractiveness is a possible extension of the Barabási–Albert model. The Barabási–Albert model generates scale-free networks where the degree distribution can be described by a pure power law. However, the degree distribution of most real life networks cannot be described by a power law solely. The most common discrepancies regarding the degree distribution found in real networks are the high degree cut-off and the low degree cut-off. The inclusion of initial attractiveness in the Barabási–Albert model addresses the low-degree cut-off phenomenon.
In the scale-free network theory, a mediation-driven attachment (MDA) model appears to embody a preferential attachment rule tacitly rather than explicitly. According to MDA rule, a new node first picks a node from the existing network at random and connect itself not with that but with one of the neighbors also picked at random.
