9 - Semirings and Lattices

Summary

In this chapter we elaborate some of the algebraic concepts introduced in Chapter 4 to provide foundations for a deeper understanding of signed networks and balance algorithms discussed in Chapter 10.

We continue to consider networks as graphs G = (ν, ε, A), where ε is the set of edges and A is the set of arcs that link pairs of vertices from ν. As in Chapter 4, we use L = ε ∪ A for the set of lines in the graph, G. These ties can be binary or valued. The lines form walks that, from Chapter 4, are finite sequences of alternating vertices and lines, S = υ₀, s₁, υ₁, s₂, υ₂, …, s_k, υ_k, of a graph G = (ν, ε, A). Throughout this chapter we use either {υ_i } or {u, υ, w, x, y, x, z} to denote vertices.

WALKS, PATHS, AND ALGEBRAS

A variety of interesting problems stem from considering walks (or paths) in graphs and require special algebras for their solution. If the graph represents, for example, a communication network, one problem is whether or not pairs of actors are either unilaterally or mutually reachable. Let x, y, and z be three vertices in a graph. In a directed graph, y could be reachable from x, or x could be reachable from y, but not both (in which case the graph is unilaterally connected), or x and y could be mutually reachable. If the graph is binary, we need to be able to determine if walks (or paths) exist between pairs of vertices, x and y, or not.