Network Models
This section describes the network formation models implemented in NOESIS. Network models allow studying and understanding the properties of many interesting networks. Several network formation models have been described in the scientific literature to model the topology and structure of real-world networks, which often exhibit particular node degree distributions and a small diameter. These models define algorithmic procedures for generating synthetic networks with very specific properties, which are helpful to test novel network analysis techniques.
NOESIS features several network formation models, including the most influential ones, such as the Erdös-Rényi, the Barabási-Albert, or the Watts-Strogatz models. Many influential random network models can be found within the noesis.model.random package. In addition, NOESIS provides several regular network models in the noesis.model.regular package.
Creating a network using a network formation model
Creating networks using the network formation models included in NOESIS is straightforward, just instantiate a network using the desired network formation model by providing the desired parameters for the generated network. Each network formation model has its own set of parameters, which are described in detail and exemplified below.
Random network models
Erdös-Rényi model
The Erdös–Rényi model is one of the most basic models to generate random graphs. In this model, networks are chosen randomly among the collection of all possible networks with the specified parameters. This model requires specifying the number of nodes and the number of links in the network.
The following code snippet creates an Erdös-Rényi random network with 100 nodes and 500 links:
Network network = new ErdosRenyiNetwork(100, 500); Reference: Erdos, P. & Rényi, A. (1960). On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1), 17-60.
Gilbert's model
Another simple model is the Gilbert's model, where each pair of nodes are connected by a link with a given probability. This model requires specifying the number of nodes and the probability of link between every pair of nodes in the network.
A Gilbert's random network with 100 nodes and a link probability of 0.1 can be created as:
Network network = new GilbertNetwork (100, 0.1);Reference: Gilbert, E. N. (1959). Random graphs. Annals of Mathematical Statistics, 30, 1141–1144. DOI: 10.1214/aoms/1177706098.
Lewis' anchored random model
The Lewis' anchored random network is a variation of the Erdös-Rényi model. This model takes two parameters: the number of nodes and the number of links in the network.
An example is shown in the following code snippet:
Network network = new AnchoredRandomNetwork(100, 500);Reference: Lewis, T. G. (2011). Network science: Theory and applications. John Wiley & Sons.
Connected random network model
The connected random model is yet another variation of the Erdös-Rényi model. In order to create a network using this model, you must provide two parameters: the number of nodes and the number of links in the network.
An example of a network with 100 nodes and 500 links is shown in the following code snippet:
Network network = new ConnectedRandomNetwork (100, 500);
Watts–Strogatz model
We can generate networks using more complex models, such as the Watts–Strogatz model. This model generates networks with small-world properties similar to those observed in real-world networks. In order to achieve these properties, this model initially creates a ring-like network, where each node is only connected to its closest neighbors in the ring. Next, the model requires a link rewiring phase, where links are rewired with a given probability to a random target node. This model requires the number of nodes, the number of links, and the probability of rewire for links.
A network with 100 nodes and 300 links using the Watts-Stogatz model, with a link rewiring probability of 0.2, can be generated using the following code snippet:
Network network = new WattsStrogatzNetwork(100, 300, 0.2);Reference: Watts, D. J. & Strogatz, S. H. (1998). Collective dynamics of 'small-world' networks. Nature, 393 (6684), 440–442. DOI: 10.1038/30918.
Barabási–Albert model
The Barabási–Albert model generates scale-free networks, where node degrees follow a power law distribution. This behavior is achieved using the preferential attachment mechanism, where nodes are more likely to form new links with higher degree nodes. This model requires the number of nodes and the number of links for each node in the network.
A Barabási-Albert network with 100 nodes and 5 links for each node can be generated as follows:
Network network = new BarabasiAlbertNetwork(100, 5);References:
- Barabási, A. L., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286(5439), 509-512. DOI: 10.1126/science.286.5439.509.
- Albert, R., & Barabási, A. L. (2002). Statistical mechanics of complex networks. Reviews of modern physics, 74(1), 47. DOI: 10.1103/RevModPhys.74.47.
Price's model
The Price's model can be used to generate networks with similar properties to real citation networks. This model is similar to the Barabási-Alber model, given that citation networks also tend to follow a power law degree distribution. This model requires the number of nodes, the number of citation links for each node, and the number of free citations for each node in the network. The difference between citation and free links is, while citation links are created using the preferential attachment mechanism, free links are created at random uniformly choosing a target node.
A Price's network with 50 nodes, 4 citation links for each node, and 1 free link for each node can be generated using the following line of code:
Network network = new PriceCitationNetwork(50, 4, 1);References:
- Derek J. de Solla Price. (1976). A general theory of bibliometric and other cumulative advantage processes. Journal of the American Society for Information Science, 27(5):292-306. DOI: 10.1002/asi.4630270505.
- P. L. Krapivsky and S. Redner. (2001). Organization of growing random networks. Physical Review E - Statistical, Nonlinear, and Soft Matter Physics, 63:066123. DOI: 10.1103/PhysRevE.63.066123.
Regular network models
NOESIS also includes many regular network models in its noesis.model.regular package. Instead of generating random networks, these models generate networks with a well-known topology. In addition, NOESIS can provide relevant topological metrics, such as distance between nodes, diameter, min-max degree, or clustering coefficient, based on theoretical results.
Complete network
A complete network is a regular network where every pair of nodes is connected by a link. This model only takes the number of nodes in the network as parameter. An example for creating a complete network with 15 nodes is shown below:
RegularNetwork network = new CompleteNetwork(15);
Star network
In a star network, all nodes are connected to a central or root node. This model requires specifying the number of nodes in the network as parameter. An example for creating a star network with 15 nodes is shown below:
RegularNetwork network = new StarNetwork(15);
Ring network
As its name suggests, in this model, nodes are connected to exactly two neighbors composing a unique component. This model only requires the number of nodes in the network as parameter. The following code snippet creates a ring network with 15 nodes:
RegularNetwork network = new RingNetwork(15);
Tandem network
A tandem network is similar to a rope: two end nodes are connected by a chain of internal nodes. These internal nodes are connected only to exactly two neighbors. As in the previous regular models, instantiating a network using this model only requires passing the number of nodes in the network as parameter. A tandem network with 15 nodes can be created as shown below:
RegularNetwork network = new TandemNetwork(15);
Mesh network
In a mesh network, nodes are arranged in a two-dimensional grid. This model requires specifying the number of rows and the number of columns. For example, to create a mesh network with 10 rows and 10 columns we would write the following line of code:
RegularNetwork network = new MeshNetwork(10,10);
Toroidal network
A toroidal network is a mesh network where the outer nodes of the grid are also connected with the outer nodes at the other end of their row and their column. As for mesh networks, this models requires passing the number of rows and the number of columns in the network. A toroidal network with 10 rows and 10 columns can be created as follows:
RegularNetwork network = new ToroidalNetwork(10,10);
Hypercube network
This model creates an hypercube, where corners are represented as nodes and edges as links. This model only requires specifying the dimensionality of the hypercube. For example, a 3-dimensional cube can be created with the following line:
RegularNetwork network = new HypercubeNetwork(3);
Binary tree network
In a binary tree, nodes are arranged hierarchically so that each node is connected to its parent and, at most, to two children. This model requires specifying the number of nodes in the tree. The binary tree is grown on a level-by-level basis. In order to create a binary tree with 15 nodes, you should type the following line of code:
RegularNetwork network = new BinaryTreeNetwork(15);
Isolate network
An isolate network is simply a network without links. This model requires specifying the number of nodes in the network. A isolate network can be created using the following code snippet:
RegularNetwork network = new IsolateNetwork(15);