Networks and dynamic networks
The dynamic plex propagation algorithm is a way of analysis a dynamic network. There are many great resources on networks and graph theory, so this page provides a basic description of networks as relevant to the algorithm. In addition to a description of networks, this page describes the representation used by the algorithm.
The dynamic plex propagation algorithm is designed and built around binary, undirected networks (although is potentially adaptable to either weighted or directed networks). The image below shows a basic example of such a network.
Each dot in the above image is known as a vertex, while the lines between the vertices are known as edges. A network or graph is used to represent connectivity between vertices. A frequently cited example is social networks, where the vertices are people and edges represent associations (such as friendships). Looking at these networks through such visualizations, and the associated mathematical tools, provides a way to identify how different vertices and edges play a role in the network. In the social network example, it is possible to look for vertices that have many connections and therefore represent well-connected or influential people within a social group. Alternatively, in computer network management, network diagrams are used to identify potential bottlenecks (vertices that can only be reached via a single path, which is vulnerable to failure).
This algorithm focuses on binary networks, which means that there either is or is not an edge between two vertices, as opposed to weighted networks where each edge may have a weight connoting the strength of the connection.
This algorithm also focuses on undirected networks, where an edge does not constrain the direction of travel. That is, an edge represents connectivity in both directions. This is opposed to directed networks, where an edge may be constrained to moving from one vertex to the other.
In Matlab, we represent undirected binary networks as logical matrices of connectivity. In a network with n vertices, the matrix of connectivity will be of size n ⨉ n. Each entry in the matrix represents the connectivity between two vertices. For example x_{i, j} = 0 means that vertex i and vertex j are not connected, while x_{i, j} = 1 means that they are connected.
The networks used by this algorithm are not recurrent (meaning that a vertex can not connect to itself), so the diagonal of the matrix is 0 (x_{i, i} = 0).
And because the networks used by this algorithm are undirected, the matrices are symmetric (as a connection between vertex i and j implies a connection between j and i). x_{i, j} = x_{j, i}.
Using a much smaller network as an example, we can write out a connectivity matrix to illustrate the above points:
The connectivity for this network is:
[ 0, 0, 0, 1 ;
0, 0, 0, 1 ;
0, 0, 0, 0 ;
1, 1, 0, 0 ]
The one remaining element is that the dynamic plex propagation algorithm is for understanding networks that change overtime -- hence, dynamic. Specifically, we are interested in networks where the connectivity changes from time point to time point.
As a result, these dynamic networks can be represented as a series of standard n ⨉ n connectivity matrices representing the connectivity at each time point. As a result, the input to the algorithm is a n ⨉ n ⨉ m matrix, where m is the number of time steps.
The connectivity for a single time point can be found by extracting a slice of this three dimensional matrix.
X(:, :, 1) = [ ... ] % connectivity at time step 1