Difference between revisions of "Mandala Network"

 
(4 intermediate revisions by one other user not shown)
Line 1: Line 1:
A Mandala network refers a family of networks that allow for fast communication and are cost-effective yet are robust against failures and attacks. They are built up in layers (or ''shells'') and their name derives from their visual similarity to Mandala images.
+
Mandala networks refer to a family of networks which are fast and cost-effective, yet robust against failures and attacks. They are built up in layers, or ''shells/generations'', and their name derives from their visual similarity to Mandala images.
  
They are defined by construction in [ref Sampaio et al] as mathematical graph with certain rules for the distribution and connectedness (or ''degree'') of the nodes and edges in each shell. They are characterised by being
+
They are defined by construction in [1] as a mathematical graph with certain rules for the distribution of nodes and edges in each shell, and how they connect to nodes in the shell below. They are characterised by being
 
* Ultra-small-world
 
* Ultra-small-world
 
* Highly sparse
 
* Highly sparse
  
In the basic method for construction, Mandala networks are cahracterised by three paramaters (''n_1'', ''b'', ''lambda''). Here ''n_1'' is the number of nodes in the first generation, ''b'' is the number of new nodes added to each external shell, and ''lambda'' is the scale factor. Once these parameters have been chosen, a Mandala network is uniquely determined by the total number of shells ''g''. The total number of nodes in each shell is labelled n_i and total number of nodes on the network is given by
+
In the basic method for construction, Mandala networks are characterised by three parameters <math>(n_1, b, \lambda)</math>, where <math>n_1</math> is the number of nodes in the first generation, <math>b</math> is the number of new nodes added to each node in subsequent shells, and <math>\lambda</math> is the number of connections between nodes in the same shell (other than the first shell). The choice of these parameters determines a ''type'' of Mandala network, where a unique Mandala network is determined by type and total number of shells <math>g</math>.  
  
N = Sum i=1 to g n_i .
+
In the first shell there are <math>n_1</math> nodes that form a connected graph. A second shell is created by connecting each node in the first shell with <math>b</math> nodes in the second shell, and connecting each node in the second shell to <math>\lambda</math> nodes in the second shell. This method is used to create a third shell where, in addition, each node is also connected to its ancestor node in the first shell. This process can be repeated iteratively to create <math>g</math> shells. Because each node is connected directly to a node in the first shell, and each node in the first shell is directly to another node in the first shell, the maximum shortest path length between nodes is 3.
  
In the first shell the nodes form a connected graph. A subsequent shell is created where each node is connected to its ancestor and to other nodes in the same shell. This process is repeated creating multiple shells. The degree of each node at the ith shell in a network with a total of ''g'' shells is given by
+
If the number of nodes in each shell is labelled by <math> n_i </math> then the total number of nodes on the network is given by
  
Kig = b lambda^{g-i} + (i-1)
+
<math>N = \sum_{i=1}^{g} n_i </math>.
  
The mean shortest path length is given by
+
Due to the symmetry of the construction, the mean shortest path length is given by
  
<l> = alpha + O(N)/N^2
+
<math>\langle l \rangle = \sum_{i=1}^{g} n_i \phi_i </math>
  
where alpha is a constant which may be determined for each network. Note that alpha > 1 as only in the case of a connected graph do we have alpha = 1.
+
where <math>\phi_i </math> is the sum of the shortest path lengths connecting a node in the <math>i</math>-th shell with all other nodes in the network. It can be shown that
  
 +
<math>\langle l \rangle = \alpha + \frac{O(N)}{N^2}</math>
  
 +
where <math>\alpha</math> is a constant which may be determined for each network. It can be shown that <math>1 \leq \alpha < \frac{8}{3}</math>, where <math> \alpha \to \frac{8}{3}</math> as <math>N \to \infty</math>.
  
 
== References ==
 
== References ==
* [https://www.nature.com/articles/srep09082 ''Mandala Networks: ultra-small-world and highly sparse graphs'', Sampaio Filho, C., Moreira, A., Andrade, R. et al. Sci Rep 5, 9082 (2015) doi:10.1038/srep09082]
+
[https://www.nature.com/articles/srep09082 (1) ''Mandala Networks: ultra-small-world and highly sparse graphs'', Sampaio Filho, C., Moreira, A., Andrade, R. et al. Sci Rep 5, 9082 (2015) doi:10.1038/srep09082]

Latest revision as of 03:29, 19 November 2020

Mandala networks refer to a family of networks which are fast and cost-effective, yet robust against failures and attacks. They are built up in layers, or shells/generations, and their name derives from their visual similarity to Mandala images.

They are defined by construction in [1] as a mathematical graph with certain rules for the distribution of nodes and edges in each shell, and how they connect to nodes in the shell below. They are characterised by being

  • Ultra-small-world
  • Highly sparse

In the basic method for construction, Mandala networks are characterised by three parameters , where is the number of nodes in the first generation, is the number of new nodes added to each node in subsequent shells, and is the number of connections between nodes in the same shell (other than the first shell). The choice of these parameters determines a type of Mandala network, where a unique Mandala network is determined by type and total number of shells .

In the first shell there are nodes that form a connected graph. A second shell is created by connecting each node in the first shell with nodes in the second shell, and connecting each node in the second shell to nodes in the second shell. This method is used to create a third shell where, in addition, each node is also connected to its ancestor node in the first shell. This process can be repeated iteratively to create shells. Because each node is connected directly to a node in the first shell, and each node in the first shell is directly to another node in the first shell, the maximum shortest path length between nodes is 3.

If the number of nodes in each shell is labelled by then the total number of nodes on the network is given by

.

Due to the symmetry of the construction, the mean shortest path length is given by

where is the sum of the shortest path lengths connecting a node in the -th shell with all other nodes in the network. It can be shown that

where is a constant which may be determined for each network. It can be shown that , where as .

References

(1) Mandala Networks: ultra-small-world and highly sparse graphs, Sampaio Filho, C., Moreira, A., Andrade, R. et al. Sci Rep 5, 9082 (2015) doi:10.1038/srep09082