Connectivity

When the basic semiring (A, ⊕, ⊙, 0, 1) is closed - an unary closure operation ★ with the property

a^★ = 1 ⊕ a⊙a^★ = 1 ⊕ a^★⊙a, ∀ a ∈ A

is defined in it. This property can be extended also to the corresponding matrix semiring. When it exists, a standard closure is obtained as

a^★ = ⊕{i∈ℕ : aⁱ}

For a temporal quantity a over a closed semiring it holds T_a^★ = T.

In some semirings different closures can exist. For computing the matrix closure we can apply the Fletcher's algorithm \citep{closure}. The entry c_uv in the matrix C = A^★ is equal to the sum of values of all walks from the node u to the node v.

In most of the semirings, except the combinatorial, for which we are interested in determining the closures, also the absorption law holds

1 ⊕ a = 1, ∀ a ∈ A .

In these semirings a^★ = 1, for all a ∈ A, and therefore the Fletcher's algorithm can be simplified and performed in place as follows

Closure of a temporal matrix over an absorptive semiring.

MatClosure(R, strict=False)
   n ← nRows(R)
   C ← R
   for k ∈ 1:n
      for u ∈ 1:n
         for v ∈ 1:n
            C[u,v] ← sum(C[u,v], prod(C[u,k],C[k,v]))
         endfor
      endfor
      if ¬ strict then C[k,k] ← sum(1,C[k,k])
   endfor
   return C
end      

The time complexity of this algorithm is O(n³ ∙ L).

In the previous sections, the nodes of temporal networks were considered as being present all the time. We can describe the presence of nodes through time using a temporal binary (single valued) node partition T : V → A_⌘(T),

T(u) = ( (s_i, f_i, 1) )_i∈1:k, ∀ u ∈ V

specifying that a node u is present in time intervals [s_i, f_i), i∈1:k.

The node partition T_Min determined from the temporal network links by

T_Min(u) = ⋃{e ∈ L : u ∈ ext(e) : binary(a_e)} , for u ∈ V,

is the smallest temporal partition of nodes that satisfies the consistency condition from Section~\ref{desc}. The term ext(e) denotes the set of end-nodes of the link e, a_e is the temporal quantity assigned to the link e, and the function binary sets all values in a given temporal quantity to 1. In the library TQ the partition T_Min can be computed using the function minTime.

A temporal node partition q can also be used to extract a corresponding subnetwork from the given temporal network described with a matrix A. The subnetwork contains only the nodes active in the partition q and the active links satisfying the consistency condition with respect to q.

To formalize the described procedure we first define the procedure extract(p,a) = b, where p is a binary temporal quantity and a is a temporal quantity, as

b(t) = a(t), for t ∈ T_p ⋂ T_a; and b(t) = ⌘ otherwise.

Let B be a temporal matrix describing the links of the subnetwork determined by the partition q. Its entries for e(u,v) ∈ L are determined by b_e = extract(q(u) ⋂ q(v),a_e) . In TQ this operation is implemented as a procedure MatExtract(q, A).

For a temporal network represented with the corresponding binary matrix A its transitive closure A^★ (over the reachability semirings based on the semiring ({0, 1}, ⋁, ⋀, 0, 1)) determines its reachability relation matrix. We obtain its weak connectivity temporal matrix W as

W = (A ⋃ A^T)^★

and its strong connectivity temporal matrix S as

S = A^★ ⋂ (A^★)^T

The use of the strict transitive closure instead of a transitive closure in these relations preserves the inactivity value 0 on the diagonal for all isolated nodes.

Let R = A⁺ = A ⊙ A^★ be the strict reachability relation of a given network. Then the temporal vectors inReach = inDeg(R) and outReach = outDeg(R) contain temporal quantities counting the number of nodes: from which a given node v is reachable ( inReach[v] ) / which are reachable from the node v ( outReach[v] ). The results for our example network are presented in Table~\ref{ioReach}. For example, 8 nodes { 4,5,6,7,8,9,10,11 } are reachable from node 6 in the time interval [1,5), and 3 nodes { 4,5,6 } are reachable in the time interval [5,9).

Temporal input and output reachability degrees for the first example network.

Input reachability                        Output reachability
 1 : [(1, 9, 3)]                           1 : [(1, 3, 2), (3, 5, 10), (5, 9, 5)]
 2 : [(1, 9, 3)]                           2 : [(1, 3, 2), (3, 5, 10), (5, 9, 5)]
 3 : []                                    3 : [(1, 3, 2), (3, 5, 10), (5, 9, 5)]
 4 : [(1, 3, 3), (3, 9, 6)]                4 : [(1, 5, 8), (5, 9, 3)]
 5 : [(1, 3, 3), (3, 9, 6)]                5 : [(1, 5, 8), (5, 9, 3)]
 6 : [(1, 3, 3), (3, 9, 6)]                6 : [(1, 5, 8), (5, 9, 3)]
 7 : [(1, 3, 3), (3, 5, 6), (7, 9, 5)]     7 : [(1, 7, 4), (7, 9, 5)]
 8 : [(1, 3, 8), (3, 5, 11), (5, 9, 5)]    8 : [(1, 7, 4), (7, 9, 5)]
 9 : [(1, 3, 8), (3, 5, 11), (5, 9, 5)]    9 : [(1, 7, 4), (7, 9, 5)]
10 : [(1, 3, 8), (3, 5, 11), (5, 9, 5)]   10 : [(1, 7, 4), (7, 9, 5)]
11 : [(1, 3, 8), (3, 5, 11), (5, 9, 5)]   11 : [(1, 7, 4), (7, 9, 5)]
12 : []                                   12 : []
13 : [(2, 8, 3)]                          13 : [(2, 8, 3)]
14 : [(2, 8, 3)]                          14 : [(2, 8, 3)]
15 : [(2, 8, 3)]                          15 : [(2, 8, 3)]

The function weakConnMat(A) for a given temporal network matrix A determines the corresponding temporal weak connectivity matrix W. Every time slice N(t), t ∈ T, of the matrix W is an equivalence relation that can be compactly described with the corresponding partition.

To transform the temporal equivalence matrix E into the corresponding temporal partition p we use the fact that on a given time interval equivalent (in our case weakly connected) nodes get the same value on this interval in the product of the matrix E with a vector computed over the combinatorial semiring (ℕ,+,∙,0,1). We take for the vector values randomly shuffled integers from the interval 1:n. With a very high probability the values belonging to different equivalence classes are different. This is implemented as a procedure eqMat2Part(E). Maybe in the future implementations we shall add a loop with the check of the injectivity of this mapping. The classes of the obtained temporal partition are finally renumbered with consecutive numbers using the function renumPart(p).

For our first example network we obtain the temporal weak partition presented on the left hand side of the following table:

Temporal weak and strong connectivity partitions for the first example network.

Weak partition                             Strong partition
 1 : [(1, 3, 1), (3, 5, 2), (5, 9, 3)]      1 : [(1, 9, 1)]
 2 : [(1, 3, 1), (3, 5, 2), (5, 9, 3)]      2 : [(1, 9, 1)]
 3 : [(1, 3, 1), (3, 5, 2), (5, 9, 3)]      3 : []
 4 : [(1, 3, 4), (3, 5, 2), (5, 9, 3)]      4 : [(1, 9, 2)]
 5 : [(1, 3, 4), (3, 5, 2), (5, 9, 3)]      5 : [(1, 9, 2)]
 6 : [(1, 3, 4), (3, 5, 2), (5, 9, 3)]      6 : [(1, 9, 2)]
 7 : [(1, 3, 4), (3, 5, 2), (5, 9, 5)]      7 : [(7, 9, 3)]
 8 : [(1, 3, 4), (3, 5, 2), (5, 9, 5)]      8 : [(1, 7, 4), (7, 9, 3)]
 9 : [(1, 3, 4), (3, 5, 2), (5, 9, 5)]      9 : [(1, 7, 4), (7, 9, 3)]
10 : [(1, 3, 4), (3, 5, 2), (5, 9, 5)]     10 : [(1, 7, 4), (7, 9, 3)]
11 : [(1, 3, 4), (3, 5, 2), (5, 9, 5)]     11 : [(1, 7, 4), (7, 9, 3)]
12 : []                                    12 : []
13 : [(2, 8, 6)]                           13 : [(2, 8, 5)]
14 : [(2, 8, 6)]                           14 : [(2, 8, 5)]
15 : [(2, 8, 6)]                           15 : [(2, 8, 5)]

The procedure strongConnMat(A) for a given temporal network matrix A determines the corresponding temporal strong connectivity matrix S. To determine the intersection of temporal network binary matrices A and B we use the function MatInter(A,B). Again, to get the strong connectivity partition we have to apply the function eqMat2Part to the strong connectivity matrix.

In the library TQ both matrices and partitions are based on the strict transitive closure. The time complexity of algorithms for temporal weak and strong connectivity partitions is O(n³ ∙ L).

For our first example network we obtain the temporal strong partition presented on the right hand side of the table.

Closeness and betweenness are among the traditional social network analysis indices measuring the importance of nodes \citep{cent}. They are somehow problematic when applied to non (strongly) connected graphs. In this section we will not consider these questions. We will only show how to compute them for non-problematic temporal graphs.

The output closeness of the node v is defined as

ocl(v) = ∑_{u ∈ V\{v}} d_vu /(n-1) .

To determine the closeness we first need to compute the matrix D = [d_vu] of geodetic distances d_vu between the nodes u and v. It can be obtained as a closure of the network matrix A over the shortest paths semiring (ℝ^*, min, +, ∞, 0). Note that the values in the matrix A can be any nonnegative real numbers.

In the following figure we present our second example temporal network which is an extended version of the example given in Figure~3 from \cite{semi}.

Second example network . All unlabeled arcs have the value [(1,9,1)]

Because a complete strict closure matrix D is too large to be listed we present only some of its selected entries:

D[3,1] = [(3, 7, 3), (7, 9, 5)]
D[4,6] = [(1, 4, 1), (4, 6, 5), (6, 9, 1)]
D[6,3] = [(3, 5, 6), (5, 9, 4)]
D[7,6] = [(1, 9, 4)]

To compute the vector of closeness coefficients of nodes we have to sum the temporal distances to other nodes over the combinatorial semiring. While summing we replace gaps (inactivity intervals inside T) with time intervals with the value infinity, using the procedure fillGaps. The time complexity of the algorithm is O(n³ ∙ L).

The temporal closeness coefficients for our second example network are given in the following table:

Output closeness for the second example network.

1 : [(1, 9, 0.4375)]
2 : [(1, 3, 0.0000), (3, 5, 0.4375), (5, 9, 0.5833)]
3 : [(1, 3, 0.0000), (3, 7, 0.4375), (7, 9, 0.3889)]
4 : [(1, 3, 0.0000), (3, 4, 0.4375), (4, 6, 0.3500), 
     (6, 7, 0.4375), (7, 9, 0.3500)]
5 : [(1, 3, 0.0000), (3, 7, 0.4375), (7, 9, 0.3500)]
6 : [(1, 3, 0.0000), (3, 5, 0.2917), (5, 9, 0.3500)]
7 : [(1, 3, 0.0000), (3, 7, 0.4375), (7, 9, 0.3500)]
8 : [(1, 3, 0.0000), (3, 5, 0.3500), (5, 9, 0.4375)]

The betweenness of a node v is defined as

b(v) = ( ∑_{u,w ∈ V ⋀ |{v,u,w}|=3} n_u,w(v) / n_u,w ) / ( (n-1)(n-2) )

where n_u,w is the number of u-w geodesics (shortest paths) and n_u,w(v) is the number of u-w geodesics passing through the node v.

Suppose that we know the matrix C = [( d_u,v, n_u,v ) ] where d_u,v is the length of u-v geodesics. Then it is also easy to determine the quantity n_u,w(v):

n_u,w(v) = n_u,v ∙ n_v,w if d_u,v + d_v,w = d_u,w; and 0 otherwise

This gives the following scheme of procedure for computing the nontemporal betweenness coefficients b

  compute C
  for v ∈ V :
     r ← 0
     for u ∈ V, w ∈ V :
        if n[u,w]≠0 ⋀ |{v,u,w}| = 3 ⋀ d[u,w]=d[u,v]+d[v,w] :
           r ← r + n[u,v]∙n[v,w]/n[u,w]
        endif
     endfor
     b[v] ← r / ((n-1)(n-2))
  endfor

In \cite{semi} it is shown that the matrix C can be obtained by computing the closure of the network matrix over the geodetic semiring ( (ℕ^*)², ⊕, ⊙, (∞,0), (0,1) ), where ℕ^* = ℕ ⋃ {∞} and we define addition ⊕ with

(a,i) ⊕ (b,j) = ( min(a,b), i if a < b ; i+j if a = b ; j if a > b )

and multiplication ⊙ with:

(a,i) ⊙ (b,j) = (a+b,i∙j) .

To compute the geodetic closure we first transform the network temporal adjacency matrix A to a matrix G = [ (d,n)_u,v ] which has for entries pairs defined by

(d,n)_u,v(t) = (1,1) if ∃ e ∈ L : (e(u,v) ⋀ t ∈ T(e) ) ; and ⌘ otherwise

where d is the length of a geodesic and n is the number of geodesics from u to v. In temporal networks the distance d and the counter n are temporal quantities.

Following the presented scheme of computing the betweenness vector and adapting it to temporal quantities (see Algorithm~\ref{betwTQ}) in the function betweenness we first transform the network matrix A into a matrix G with values (1,1) on arcs and compute its strict geodetic closure C over the geodetic semiring.

We present only some selected entries of the strict geodetic closure matrix C for our second example network:

   
C[1,7] = [(1, 9, (3, 4))]
C[2,2] = [(1, 3, (4, 4)), (3, 4, (4, 6)), (4, 5, (4, 5)), (5, 9, (2, 1))]
C[4,6] = [(1, 4, (1, 1)), (4, 6, (5, 3)), (6, 9, (1, 1))]
C[5,5] = [(1, 9, (1, 1))]
C[6,3] = [(3, 5, (6, 2)), (5, 9, (4, 1))]
C[7,6] = [(1, 3, (4, 2)), (3, 4, (4, 6)), (4, 6, (4, 3)), (6, 7, (4, 6)),
          (7, 9, (4, 2))]

For example, the value C[4,6] reflects the facts that an arc exists from node 4 to node 6 in time intervals [1,4) and [6,9); and in the time interval [4,6) they are connected with 3 geodesics of length 5: (4,7,8,2,5,6), (4,7,1,3,5,6), (4,7,1,2,5,6).

We continue and using the combinatorial semiring we compute the temporal betweenness vector b. The specificity of temporal quantities d[u,v] and n[u,v] is considered in the function between (see Algorithm~\ref{btwTQ}) that implements the temporal version of the statement

if d[u,w]=d[u,v]+d[v,w] then r ← r + n[u,v]∙n[v,w]/n[u,w]

from the basic betweenness algorithm. Again we have to apply the merging scheme. The time complexity of Algorithm~\ref{betwTQ} is O(n³ ∙ L).

The temporal betweenness coefficients for our second example network are presented in Table~\ref{betwC}.

Betweenness for the second example network.

1 : [(3, 4, 0.2500), (4, 6, 0.2754), (6, 7, 0.2500), (7, 9, 0.1429)]
2 : [(1, 3, 0.3452), (3, 4, 0.4048), (4, 6, 0.4187), (6, 7, 0.4048), (7, 9, 0.6071)]
3 : [(1, 3, 0.0595), (3, 4, 0.0952), (4, 6, 0.1052), (6, 7, 0.0952), (7, 9, 0.0595)]
4 : [(1, 3, 0.1667), (3, 4, 0.2500), (4, 5, 0.1762), (5, 6, 0.1048), (6, 9, 0.1786)]
5 : [(1, 3, 0.1667), (3, 4, 0.2500), (4, 5, 0.3476), (5, 6, 0.2762), (6, 9, 0.1786)]
6 : [(1, 3, 0.1190), (3, 4, 0.0952), (4, 6, 0.0544), (6, 7, 0.0952), (7, 9, 0.1786)]
7 : [(1, 3, 0.1190), (3, 4, 0.4048), (4, 5, 0.4694), (5, 6, 0.3266), (6, 7, 0.2619),
     (7, 9, 0.1786)]
8 : [(1, 3, 0.3095), (3, 4, 0.2500), (4, 6, 0.2484), (6, 7, 0.2500), (7, 9, 0.5238)]