8-simplex honeycomb: Difference between revisions
en>Tomruen |
en>Tomruen |
||
| Line 1: | Line 1: | ||
{{Network_Science}} | |||
'''Hierarchical network models''' are iterative algorithms for creating [[Complex network|networks]] which are able to reproduce the unique properties of the [[Scale-free network|scale-free]] [[Network topology|topology]] and the high [[Clustering coefficient|clustering]] of the [[Node (graph theory)|nodes]] at the same time. These characteristics are widely observed in nature, from [[biology]] to [[language]] to some [[social network]]s. | |||
== Concept == | |||
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 model|Barabási–Albert]], [[Watts and Strogatz model|Watts–Strogatz]]) in the [[Distribution (mathematics)|distribution]] of the nodes' clustering coefficients: as other models would predict a constant clustering coefficient as the function of the [[Degree (graph theory)|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 network modelling|metabolic networks]], the [[Protein–protein interaction|protein interaction network]], the [[WWW|World Wide Web]] or some [[social network]]s) exhibit such properties, different hierarchical topologies were introduced in order to account for these various characteristics. | |||
== Algorithm == | |||
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=5<sup>k+1</sup>''.<ref name= RB-2003>{{Cite doi|10.1103/PhysRevE.67.026112}}</ref> | |||
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.<ref name= DGM-2002>{{Cite doi|10.1103/PhysRevE.65.066122}}</ref><ref name= BRV-2001>{{Cite doi|10.1016/S0378-4371(01)00369-7}}</ref> | |||
[[File:Hierarchical network model example.png|thumb|Example of a hierarchical network structure.]] | |||
== Properties == | |||
=== Degree distribution === | |||
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 | |||
: <math>P\left(k\right)\sim ck^{-\gamma} \, </math> | |||
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].<ref name= BA-1999>{{Cite doi|10.1126/science.286.5439.509}}</ref> | |||
As a specific result for hierarchical models it has been shown that the degree exponent of the distribution function can be calculated as | |||
: <math>\gamma=1+\frac{lnM}{ln(M-1)} </math> | |||
where ''M'' represents the replication factor of the model.<ref name= N-2003>{{Cite doi|10.1103/PhysRevE.67.045103}}</ref> | |||
=== Clustering coefficient === | |||
In contrast to the other scale-free models ([[Erdős–Rényi model|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: | |||
: <math>C\left(k\right)\sim k^{-\beta} \, </math> | |||
It has been analytically shown that in deterministic scale-free networks the exponent β takes the value of 1.<ref name= DGM-2002/> | |||
== Examples == | |||
=== Actor network === | |||
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.<ref name= RB-2003/> | |||
=== Language network === | |||
Words can be regarded a 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.<ref name= RB-2003/> | |||
=== Network of webpages === | |||
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 γ<sub>out</sub>=2.45 and γ<sub>in</sub>=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.<ref name= RB-2003/><ref name= AJB-1999>{{Cite doi|10.1038/43601}}</ref> | |||
=== Domain network === | |||
The [[Administrative domain|domain]] network, i.e. the internet at the autonomuous 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<sup>-0.75</sup>'' whose exponent is (in absolute terms) somewhat smaller than the theoretical parameter for deterministic scale-free networks.<ref name= RB-2003/><ref name= VSPV-2002>{{Cite doi|10.1103/PhysRevE.65.066130}}</ref> | |||
== References == | |||
{{Reflist}} | |||
[[Category:Networks]] | |||
[[Category:Social networks]] | |||
Revision as of 02:42, 22 January 2014
Template:Network Science 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.
Concept
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 the 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.
Algorithm
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]
Properties
Degree distribution
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]
Clustering coefficient
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]
Examples
Actor network
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]
Language network
Words can be regarded a 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]
Network of webpages
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]
Domain network
The domain network, i.e. the internet at the autonomuous 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]
References
43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.