Semirings and Matrix Analysis of Networks

Synonyms

Algebraic path problem; Matrix; Multiplication of vector and matrix; Network; Network multiplication; Semiring; Simple walk; Value matrix; Walk

Glossary

Algebraic Structure

A set with one or more operations defined on it

Network Analysis

A study of networks as representations of relations between discrete objects

Sparse Matrix

A matrix with most of entries equal to zero

Large Network

A network with several thousands or millions of nodes

Complete Graph

K _n A network in which every pair of nodes is linked

Introduction

Semirings are an algebraic structure with two operations that provide the basic conditions for studying matrix addition and multiplication and path problems in networks. Several results and algorithms from different fields of application turn out to be just special cases over the corresponding semirings.

Semirings

Let $\mathbb K$ be a set and a;b;c elements from $\mathbb K$. A semiring (Abdali and Saunders 1985; Baras and Theodorakopoulos 2010; Batagelj 1994) is an algebraic structure. ( $\mathbb K$, ⊕, ⊙,0,1) with two binary operations addition ⊕ and multiplication ⊙ where:

( $\mathbb K$,⊕) is an abelian monoid with neutral element 0 (zero):

$$\begin{array}{ll}& a \oplus b = b \oplus a\,{\rm{commutativity}} \cr& (a \oplus b) \oplus c = a \oplus (b \oplus c)\,{\rm{associativity}} \cr& a \oplus 0 = a\,{\rm{existence}}\,{\rm{of}}\,{\rm{zero}}\end{array}$$
( $\mathbb K$,⊙) is a monoid with neutral element 1 (unit):

$$\begin{array}{ll}& (a \odot b) \odot c = a \odot (b \odot c)\,{\rm{associativity}} \cr& a \odot 1 = 1 \odot a = a\,{\rm{existence}}\,{\rm{of}}\,{\rm{unit}}\end{array}$$
Multiplication ⊙ distributes over addition ⊕:

$$\begin{array}{ll}& a \odot (b \oplus c) = a \odot b \oplus a \odot c \cr& (b \oplus c) \odot a = b \odot a \oplus c \odot a \end{array}$$

In the expressions we assume precedence of multiplication over addition.

A semiring ( $\mathbb K$, ⊕,⊙,0,1) is complete iff the addition is well defined for countable sets of elements and the commutativity, associativity, and distributivity hold in the case of countable sets. These properties are generalized in this case; for example, the distributivity takes form

$$\begin{array}{ll}& \left( { \oplus _i a_i } \right) \odot \left( { \oplus _j b_j } \right) = \oplus _i \left( { \oplus _j (a_i \odot b_j )} \right) \cr & = \oplus _{i,j} (a_i \odot b_j ).\end{array}$$

The addition is idempotent iff a ⊕ a = a for all a ∈ $\mathbb K$ : In this case the semiring over a finite set $\mathbb K$ is complete.

A semiring ( $\mathbb K$, ⊕,⊙,0,1) is closed iff for the additional (unary) closure operation * it holds for all a * $\mathbb K$:

$$a^* = 1 \oplus a \odot a^* = 1 \oplus a^* \odot a.$$

Different closures over the same semiring can exist. A complete semiring is always closed for the closure

$$a^* = \oplus_{k \in \mathbb{N}} a^k.$$

In a closed semiring we can also define a strict closure ā by

$$\overline{a} = a \odot a^*.$$

In a semiring ( $\mathbb K$, ⊕;⊙,0,1) the absorption law holds iff for all a, b, c ∈ $\mathbb K$:

$$a \odot b \oplus a\odot c \odot b = a \odot b.$$

Because of distributivity it is sufficient to check the property 1 ⊕ c = 1 for all c ∈ $\mathbb K$.

Combinatorial Semiring (ℕ, +, ∙, 0,1)

This is the most commonly used semiring. Also some other sets are used: ℝ, $\mathbb{R}, \mathbb{R}_0^+, \mathbb{Q}$. For ℕ̄ = ℕ∪ {∞}, the semiring is closed for $a^* = \sum_{k \in \overline{\mathbb{N}}}a^k$ because it is a complete semiring. Another possible closure for ℝ̄ = ℝ ∪ {∞} is a* = 1=.1 − a) for a ≠ 1, ∞ and 0* = 1;1* = ∞, and ∞* = ∞. This semiring is commutative because it holds a ⊙ b = b ⊙ a for all a and b in the set. Combinatorial semiring is not an idempotent semiring.

Reachability Semiring ({0,1}, ∨, ∧, 0,1)

The logical (Boolean) semiring is useful for solving the connectivity questions in networks. The multiplication is commutative and the absorption law holds. The reachability semiring is closed for a* = 1 ∨ a ∧ a * = 1.

Shortest Paths Semiring $(\overline{\mathbb{R}}^+_0,\!\min,\!+,\!\infty,\!0)$

The commutativity of multiplication holds in this semiring. The semiring is closed for a* = min(0, a + a*) = 0 (0 is the smallest element in the set $\mathbb{R}^+_0$). Since min(0, a) = 0, the absorption law also holds. For the set ℕ ∪ {∞}, the semiring is called tropical semiring. Another set is ℝ ∪ {∞} and in this case the semiring is isomorphic ( x → − x) to max-plus semiring (ℝ,∪{−∞}, max; +, −,∞,0).

Pathfinder Semiring $(\overline{\mathbb{R}}_0^+, \min, \fbox{r}, \infty, 0)$

The Pathfinder semiring (Schvaneveldt et al. 1988) is a special case from the family of the semirings obtained as follows. Let B ⊆ ℝ̄ be such that ( B, +, ∙,0;1) or ( B, min; +, U, 0) is a semiring ( U = max( B)). Therefore 0 ∈ B and 1 ∈ B. Let A ⊆ ℝ be such that g : A → B is a bijection. Let us define operations ⊕,▿, ⊙ so that g is a homomorphism:

$$\begin{array}{ll}g(a \oplus b)& = \,g(a) + g(b), \cr g(a\nabla b)& = \,\min (g(a),g(b)), \cr g(a \odot b)& = \,\,g(a)\cdot g(b). \end{array}$$

This is equivalent to

$$\begin{array}{ll}a \oplus b& = \,g^{ - 1} (g(a) + g(b)), \cr a\nabla b& = \,g^{ - 1} (\min (g(a),g(b))), \cr a \odot b& = \,g^{ - 1} (g(a)\cdot g(b)).\end{array}$$

The function g ⁻¹ is also a homomorphism. If g is strictly increasing function, then a▿ b = g ⁻¹(min( g( a), g( b))) = min(a,b). Since the homomorphisms preserve the algebraic properties, also the structure ( A, ⊕,⊙, g ⁻¹(0), g ⁻¹(1)) A ⊆ $\overline {\mathbb R}$, is a semiring.

For $g(x) = x^r, g^{-1}(y) = \sqrt[r]{y}$, we get the Pathfinder semiring. $(\overline{\mathbb{R}}_0^+, \min, \fbox{r}, \infty, 0)$. The multiplicative operation is the Minkowski operation $a \fbox{r} b = \sqrt[r]{a^r + b^r}$. This semiring is closed for a* =0 and the absorption law holds in it.

In Pathfinder algorithm the value r for the Minkowski operation is selected according to dissimilarity measure. For a value r = 1, the semiring is the shortest path semiring, and for a value r = ∞, the semiring is min-max semiring.

Several other examples of semirings can be found in Carré ( 1979), Burkardet al. ( 1984), Gondran and Minoux ( 2008), Baras and Theodorakopoulos ( 2010), and Kepner and Gilbert ( 2011).

Matrices

A m × n matrix A over a set $\mathbb K$ is a rectangular array of elements from the set $\mathbb K$ that consists of m rows and n columns. The entry in ith row and j th column is denoted by a _ij. If m = n the matrix A is called a square matrix. The matrix with all entry values equal to 0 is called the zero matrix and is denoted by O _mn.

The transpose of matrix A is a matrix A ^T in which the rows of A are written as the columns of $\bf{A}^T: a_{ij}^T = a_{ji}$. A square matrix A is symmetric if A = A ^T.

A diagonal matrix is a square matrix A such that only diagonal elements are nonzero: a _ij = 0; i ≠ j.If a _ii = 1; i = 1,…, n, this matrix is called the identity matrix I _n of order n. The matrix A is upper triangular if a _ij = 0, i > j, and its transpose is the lower triangular matrix.

Let ${\mathcal M}$ _mn( $\mathbb K$) be a set of matrices of order m × n over the semiring ( $\mathbb K$, ⊕, ⊙,0,1) in which we additionally require

$$\forall s \in {\mathbb K}: s \odot 0 = 0 \odot s = 0$$

and let ${\mathcal M}$( $\mathbb K$) be a set of all matrices over the $\mathbb K$. The operations ⊕ and ⊙ can be extended to the ${\mathcal M}$( $\mathbb K$):

$$\begin{array}{ll}{\bf{A}},{\rm{ }}{\bf{B}}& \in {\cal M}_{mn} ({\mathbb K}):{\rm{ }}{\bf{A}} \oplus {\bf{B}} = [a_{uv} \oplus b_{uv} ] \in {\cal M}_{mn} ({\mathbb K}) \cr & \cr& \quad \quad \quad {\bf{A}} \in {\cal M}_{mk} ({\mathbb K}),{\rm{ }}{\bf{B}} \in {\cal M}_{kn} ({\mathbb K}): \cr & {\bf{A}} \odot {\bf{B}} = [ \oplus _{t = 1}^k a_{ut} \odot b_{tv} ] \in {\cal M}_{mn} ({\mathbb K}).\end{array}$$

Then:

( ${\mathcal M}$ _mn( $\mathbb K$),⊕; O _mn) is an abelian monoid.
$(\mathcal{M}_{n^2}({\mathbb K}), \odot, \bf{I}_{n})$ is a monoid.
$(\mathcal {M}_{n^2}({\mathbb K}), \oplus, \odot, \bf{O}_n, \bf{I}_n)$ is a semiring.

For matrices A and B, it holds

$$(\bf{A} \odot \bf{B})^T = \bf{B}^T \odot \bf{A}^T.$$

Network Multiplication

A (simple directed) network ${\mathcal N }$ is an ordered pair of sets ( ${\mathcal V },{\mathcal A }$) where ${\mathcal V }$ is the set of nodes and ${\mathcal A }$ ⊆ ${\mathcal V }$ × ${\mathcal V }$ is the set of arcs. We assume that the set of nodes is finite ${\mathcal V }$ = { v ₁, v ₂,… v _n}. Let ${\mathcal N }$ = (( ${\mathcal I }$, ${\mathcal J }$), ${\mathcal A }$, w) be a simple two-mode network, where ${\mathcal I }$ and ${\mathcal J }$ are disjoint (sub)sets of nodes ( ${\mathcal V }$ = ${\mathcal I }$∪ ${\mathcal J }$; ${\mathcal I }$ ∩ ${\mathcal J }$ = 0), ${\mathcal A }$ is a set of arcs linking ${\mathcal I }$ and ${\mathcal J }$, and the mapping w : ${\mathcal A }$ → $\mathbb K$ is the arcs value function called also a weight. We can assign to the network its value matrix W = [ w _ij] with elements

$$w_{ij} = \left\{ \begin{matrix} {w((i,j))} & {(i,j) \in {\mathcal A}} \cr 0 & {{\rm{otherwise}}.} \cr\end{matrix} \right.$$

The problem with value matrices in computer applications is their size. The value matrices of large networks are sparse. There is no need to store the zero values in a matrix, and different data structures can be used for saving and working with value matrices: special dictionaries and lists.

Let ${\mathcal N }$ _A = (( ${\mathcal I }$, Ƙ), ${\mathcal A }$ _A, w and ${\mathcal N }$ _B = ((Ƙ,ℑ)A _B, w _B) be a pair of networks with corresponding matrices A _I×J and B, respectively. Assume also that w _A : ${\mathcal A }$ _A → $\mathbb K$, w _B : ${\mathcal A }$ _B → $\mathbb K$ and ( $\mathbb K$,⊕,∩,0;1) is a semiring. We say that such networks/matrices are compatible. The product ${\mathcal N }_A$ ★ ${\mathcal N }_B$ of networks ${\mathcal N }$ _A and ${\mathcal N }$ _A is a network ${\mathcal N }_C$ = (( I,J), ${\mathcal A }$ _C, w _C) for ${\mathcal A }$ _C = {( i,j);i ∈ I, j ∈ J,c _i,j ≠ 0} and w _C( i,j) = c for ( i,j) ∈ ${\mathcal A }$ _C, where C = [ c _ij]= A ∩ B. If all three sets of nodes are the same ( I = K = J), we are dealing with ordinary one-mode networks with square matrices.

When do we get an arc in the product network? Let's look at the definition of the matrix product

$$c_{ij} = \oplus_{k \in K} a_{ik} \odot b_{kj}.$$

There is an arc ( i;j) ∈ ${\mathcal A }$ _C if c _ij is nonzero. Therefore at least one term a _ij ∙ b _ij is nonzero, but this means that both a _ij and b _ij should be nonzero, and thus ( i,k) ∈ A _A and ( k,j) ∈ ${\mathcal A }$ _B (see Fig. 1):

$$c_{ij} = \oplus_{k \in N_{\bf{A}}(i)\cap N^-_{\bf{B}}(j)} a_{ik} \odot b_{kj},$$

where N _A( i) are the successors of node i in network N _A and $N_{\bf B}^- (j)$ are the predecessors of node j in network ${\mathcal N }_B$. The value of the entry c _i,j equals to the value of all paths (of length 2) from i ∈ ${\mathcal I }$ to j ∈ ${\mathcal J }$ passing through some node k ∈ $\mathbb K$.

Semirings and Matrix Analysis of Networks, Fig. 1

Multiplication of networks

The standard procedure to compute the product of matrices $A_{\mathcal I\times \mathcal K}$ and $B_{\mathcal K\times \mathcal J}$ has the complexity O(ǀ, ${\mathcal I }$,ǀ,∙ ǀ $\mathbb K$ǀ∙ǀ ${\mathcal J }$ǀ) and is therefore too slow to be used for large networks. Since the matrices of large networks are usually sparse, we can compute the product of two networks much faster considering only nonzero entries (Batagelj and Mrvar 2008; Batagelj and Cerinšek 2013):

In general the multiplication of large sparse network is “dangerous” operation since the result can “explode” — it is not sparse.

From the network multiplication algorithm, we see that each intermediate node k ∈ $\mathbb K$ adds to a product network a complete two-mode subnetwork $K_{N^-_{\bf{A}}(k),N_{\bf{B}}(k)}$ (or, in the case A = B, a complete subnetwork K _N(k)). If both degrees $\deg_A(k)=|N^-_{\bf{A}}(k)|$ and deg _B( k) = ǀ N _B( k)ǀ are large, then already the computation of this complete subnetwork has a quadratic (time and space) complexity — the result “explodes.ȝ

If for the sparse networks ${\mathcal N }$ _A and ${\mathcal N }$ _B, there are in $\mathbb K$ only few nodes with large degree and no one among them with large degree in both networks, then also the resulting product network ${\mathcal N }$ _C is sparse.

The Algebraic Path Problem

The use of special semiring and a multiplication of network can lead us to the essence of the shortest path problem (Baras and Theodorakopoulos 2010). Many other network problems can be solved by replacing the usual addition and multiplication with the corresponding operations from an appropriate semiring.

Let ${\mathcal N}$ = ( ${\mathcal V}$, ${\mathcal A}$, w) be a network where w: ${\mathcal A}$ → $\mathbb K$ is the value (weight) of arcs such that ( $\mathbb K$, ⊕, ⊙,0,1) is a semiring. We will denote the number of nodes as n = ǀ ${\mathcal V}$ǀ and the number of arcs as m = ǀ ${\mathcal A}$ǀ.

A finite sequence of nodes σ = ( u ₀, u ₁, u ₂,…, u _p−1, u _p) is a walk of length p on ${\mathcal N}$ iff every pair of neighboring nodes is linked: ( u _i−1, u _i) ∈ ${\mathcal A}$ i = 1,…, p. A finite sequence ς is a semiwalk or chain on ${\mathcal N}$ iff every pair of neighboring nodes is linked neglecting the direction of an arc. ( u _i−1, u _i ∈ ${\mathcal A}$ ∨ ( u _i, u _i−1) ∈ ${\mathcal A}$, i = 1, … p. The (semi)walk is closed iff its end nodes coincide: u ₀ = u _p. A walk is simple or a path iff no node repeats in it. If the ends of a simple walk coincide, it is called a cycle.

We can extend the value function w to walks and sets of walks on ${\mathcal N}$ by the following rules (see Fig. 2):

Let σ _v = ( v) be a null walk in the node v ∈ ${\mathcal V}$; then w(σ _v) = 1.
Let σ = ( u ₀, u ₁, u ₂,…, u _p−1, u _p) be a walk of length p ≥ 1 on ${\mathcal N}$; then

$$w(\sigma) = \odot_{i=1}^k w(u_{i-1}, u_i).$$
For empty set of walks ∅, it holds w(∅) = 0.
Let S = {σ ₁, σ ₂,…} be a set of walks in ${\mathcal N}$; then

$$w(\mathcal{S}) = \oplus_{\sigma \in \mathcal{S}} w(\sigma).$$

Semirings and Matrix Analysis of Networks, Fig. 2

Semiring operations and values of walks

Let σ ₁ and σ ₂ be compatible walks on ${\mathcal N}$ — the end node of the walk σ ₁ is equal to the start node of the walk σ ₁. Such walks can be concatenated in a new walk σ ₁ ∘ σ ₁ for which holds

$$w(\sigma _1 \circ \sigma _2 ) = \left\{ \begin{matrix} {w(\sigma _1 ) \odot w(\sigma _2 )} & {\sigma _1 \,{\rm{and}}\,\sigma _2 \,{\rm{are}}} \cr {} & {{\rm{compatible}}} \cr 0 & {{\rm{otherwise}}.} \cr\end{matrix} \right.$$

Let ${\mathcal S}_1$ and S ₂ be finite sets of walks; then

$$w(\mathcal{S}_1 \cup \mathcal{S}_2) \oplus w(\mathcal{S}_1 \cap \mathcal{S}_2) = w(\mathcal{S}_1) \oplus w(\mathcal{S}_2).$$

In the special case when ${\mathcal S}_1$ ∩ ${\mathcal S}_1$ = ∅, it holds w( ${\mathcal S}_1$ ∪ ${\mathcal S}_2$) = w( ${\mathcal S}_1$)⊕ w( ${\mathcal S}_1$). Also the concatenation of walks can be generalized to sets of walks:

$$\begin{array}{ll}\mathcal{S}_1 & \circ \mathcal{S}_2 = \{ \sigma _1 \circ \sigma _2 :\sigma _1 \in \mathcal{S}_1, \sigma _2 \in \mathcal{S}_2, \sigma _1 \cr & {\rm{and}}\,\sigma _2 \,{\rm{are}}\,{\rm{compatible}}\}.\end{array}$$

It also holds ${\mathcal S}$ ∘ ∅ = ∅ ∘ ${\mathcal S}$ = ∅.

We denote by:

$\mathcal{S}^k_{uv}$ the set of all walks of length k from node u to node v
$\mathcal{S}^{(k)}_{uv}$ the set of all walks of length at most k from node u to node v
$\mathcal{S}^*_{uv}$ the set of all walks from node u to node v
$\overline{\mathcal S}$ _uv the set of all nontrivial walks from node u to node v
$\varepsilon_{uv}$ the set of all simple walks (paths) from node u to node v

The following relations hold among these sets:

$$\mathcal{S}^k_{uv} \subseteq \mathcal{S}^{(k)}_{uv} \subseteq \mathcal{S}^*_{uv}$$

$$k \ne l\; \Leftrightarrow \;S_{uv} ^k \; \cap \;S_{uv} ^l = \theta$$

$$S_{uv} ^{(k)} = \bigcup\limits_{i = 0}^k {S_{uv} ^i,} S_{uv} ^* = \bigcup\limits_{k = 0}^\infty {S_{uv} ^k }$$

$$K \ge \left| v \right| - 1:\varepsilon _{uv} \subseteq S_{uv} ^{(k)}$$

$$w(S_{uv} ^{(k)} ) = \sum\limits_{i = 0}^k {w(S_{uv} ^i )}.$$

A set of walks ${\mathcal S}$ is uniquely factorizable to sets of walks ${\mathcal S}_1$ and ${\mathcal S}_2$ if ${\mathcal S}$ = ${\mathcal S}_1$ ∘ ${\mathcal S}_2$, and for all walks σ ₁,σ ₁′∈ ${\mathcal S}_1$, σ ₂′∈ ${\mathcal S}_2$, σ ₁ ≠ σ ₂′, σ ₂≠ σ ₂′, it holds σ ₁ ∘ σ ₂ ≠ σ ₁′ ∘ σ ₂′.

For example, for s; 0 < s < k, the nonempty set $\mathcal{S}^k_{uv}$ is uniquely factorizable to sets $\mathcal{S}^s_{u\bullet}$ and $\mathcal{S}^{k-s}_{\bullet v}$, where $\mathcal{S}_{u\bullet}^s = \bigcup_{t \in \mathcal{V}} \mathcal{S}_{ut}^s$, etc.

Theorem 1 Let the finite set ${\mathcal S}$ be uniquely factorizable for ${\mathcal S}_1$ and ${\mathcal S}_2$ or a semiring be complete. Then it holds

$$w(\mathcal{S}_1 \circ \mathcal{S}_2) = w(\mathcal{S}_1) \odot w(\mathcal{S}_2).$$

The kth power W _k of any square matrix W over $\mathbb K$ is unique because of associativity.

Theorem 2 The entry $w_{uv}^k$ of kth power W _k of value matrix W is equal to the value of all walks of length k from node u to node v:

$$w(S_{uv}^k) = \bf{W}^k[u,v] = w_{uv}^k.$$

Therefore if a network ${\mathcal N}$ is acyclic, then it holds for a value matrix W:

$$\exists k_0 <n: \forall k> k_0: \bf{W}^k = 0,$$

k ₀ is the length of the longest walk in the network.

If W is the network adjacency matrix over the combinatorial semiring, the entry $w_{uv}^k$ counts the number of different walks of length k from u to v.

Let us denote

$$\bf{W}^{(k)} = \sum_{i=0}^k \bf{W}^i.$$

In an idempotent semiring, it holds W ^(k) = (1 + W.) ^k.

Theorem 3

$$w(S^{(k)}_{uv}) = \bf{W}^{(k)}[u,v] = w^{(k)}_{uv}.$$

For the combinatorial semiring and W is the network adjacency matrix, the entry $w_{uv}^{(k)}$ counts the number of different walks of length at most k from u to v.

The matrix semiring over a complete semiring is also complete and therefore closed for $\bf{W}^* = \oplus_{k=0}^{\infty} \bf{W}^k$.

Theorem 4. For a value matrix W over a complete semiring with closure W* and strict closure W̄ hold:

$$\begin{array}{ll}& w({\mathcal S}_{uv}^* ){\rm{ }} = {\rm{ }}{\bf{W}}^* [u,v] = w_{uv}^* \qquad {\rm{and}} \cr& w(\overline {\cal S} _{uv} ){\rm{ }} = \overline {\bf{W}} [u,v] = \bar w_{uv}.\end{array}$$

For the reachability semiring and W is the network adjacency matrix, the matrix W̄ is its transitive closure.

For the shortest paths semiring and W is the network value matrix, the entry $w_{uv}^*$ is the value of the shortest path from u to v.

The paper Quirin et al. ( 2008) could be essentially reduced to the observation that the structure $(\overline{\mathbb{R}}_0^+, \min, \fbox{r}, \infty, 0)$ is a (Pathfinder) complete semiring.

Let ( $\mathbb K$, ⊕, ⊙,0,1) be an absorptive semiring and σ be a nonsimple walk from a set $\mathcal{S}^{(k)}_{uv}$. Therefore at least one node v _j appears more than once in σ. The part of a walk between its first and last appearance is a closed walk C (see Fig. 3). The whole walk can be written as σ = P ∘ C ∘ Q where P is the initial segment of σ from u to the first appearance of v _j, and Q is the terminal segment of σ from the last appearance of v _j to v. Note that P ∘ Q is also a walk. The value of both walks together is

$$w(\{ P \circ Q, P \circ C \circ Q \}) = w(P \circ Q).$$

We see that the walks that are not paths do not contribute to the value of walks. Therefore

$$w(\mathcal{S}^*_{uv}) = w(\mathcal{E}_{uv}).$$

Equality holds also for $\mathcal{S}^*_{uv} = \emptyset$.

Semirings and Matrix Analysis of Networks, Fig. 3

Example of a walk that is not a path

Since the node set ${\mathcal V}$ is finite, also the set ${\mathbb E }$ _uv is finite which allows us to compute the value $w(S^*_{uv})$. We already know that W* = W ₍₎ k= (1 + W) _k for k large enough.

To compute the closure matrix W* of a given matrix over a complete semiring ( $\mathbb K$, ⊕, ⊙, 0, 1), we can use the Fletcher's algorithm (Fletcher 1980):

If we delete the statement c _k[ k,k] := 1 ⊕ c _k[ k,k], we obtain the algorithm for computing the strict closure W̄. If the addition ⊕ is idempo-tent, we can compute the closure matrix in place — we omit the subscripts in matrices C _k.

The Fletcher's algorithm is a generalization of a sequence of algorithms (Kleene, Warshall, Floyd, Roy) for computing closures on specific semirings.

Multiplication of Matrix and Vector

Let e _i be a unit vector of length n. — the only nonzero element is at the ith position and it is equal to 1. It is essentially a 1 × n matrix. The product of a unit vector and a value matrix of a network can be used to calculate the value of walks from a node i to all the other nodes.

Let us denote

$$q_1^T = e_i^T \odot \bf{W}.$$

The values of elements of the vector q ₁ are equal to the values of walks of the length 1 from a node i to all other nodes: $q_1 [j] = w(S_{ij} ^1 )$. We can calculate iteratively the values of all walks of the length s, s = 2,3,… k that start in the node i:

$$q_s^T = q_{s-1}^T \odot \bf{W}$$

or $q_s^T = e_i^T \odot \bf{W}^s$ and $q_s[j] = w(\mathcal{S}_{ij}^s)$. Similarly we get ${q^{(k)}}^T = e_i^T \odot \bf{W}^{(k)}, \ q^{(k)}[j] = w(\mathcal{S}^{(k)}_{ij})$ and ${q^*}^T = e_i^T \odot \bf{W}^*, \ q^*[j] = w(\mathcal{S}^*_{ij})$.

This can be generalized as follows. Let ${\mathcal I}$ ⊆ ${\mathcal V}$ and $e_{\mathcal V}$ is the characteristic vector of the set ${\mathcal I}$ — it has value 1 for elements of ${\mathcal V}$ and is 0 elsewhere. Then, for example, for $q_k^T = e_{\mathcal{I}}^T \odot \bf{W}^k$, it holds $q_k[j] = w(\bigcup_{i \in \mathcal{I}}\mathcal{S}^k_{ij})$.

Acknowledgments

The first author was financed in part by the European Union, European Social Fund. The work was supported in part by grant within the EUROCORES Programme EUROGIGA (project GReGAS) of the European Science Foundation.

Cross-References

Eigenvalues, Singular Value Decomposition

Iterative Methods for Eigenvalues/Eigenvectors

Markov Chain Monte Carlo Model

Matrix Algebra, Basics of

Spectral Analysis

References

Abdali SK, Saunders BD (1985) Transitive closure and related semiring properties via eliminants. Theor Com-put Sci 40:257–274 MathSciNet

Baras JS, Theodorakopoulos G (2010) Path problems in networks. Morgan & Claypool, Berkeley MATH

Batagelj V (1994) Semirings for social networks analysis. J Math Soc 19(1):53–68 MATHMathSciNet

Batagelj V, Cerinšek M (2013) On bibliographic networks. Scientometrics 96(3):845–864

Batagelj V, Mrvar A (2008) Analysis of kinship relations with Pajek. Soc Sci Comput Rev 26(2): 224–246

Burkard RE, Cuninghame-Greene RA, Zimmermann U (eds) (1984) Algebraic and combinatorial methods in operations research. Annals of discrete mathematics, vol 19. North Holland, Amsterdam/New York

Carré B (1979) Graphs and networks. Clarendon, Oxford MATH

Fletcher JG (1980) A more general algorithm for computing closed semiring costs between vertices of a directed graph. Commun ACM 23(6): 350–351 MathSciNet

Gondran M, Minoux M (2008) Graphs, dioids and semirings: new models and algorithms. Springer, New York

Kepner J, Gilbert J (2011) Graph algorithms in the language of linear algebra. SIAM, Philadelphia MATH

Quirin A, Cordón O, Santamaria J, Vargas-Quesada B, Moya-Anegón F (2008) A new variant of the Pathfinder algorithm to generate large visual science maps in cubic time. Inf Process Manag 44(4): 1611–1623

Schvaneveldt RW, Dearholt DW, Durso FT (1988) Graph theoretic foundations of Pathfinder networks. Comput Math Appl 15(4):337–345 MATHMathSciNet