[[tq:ug:conn]]

Table of Contents

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^{i}}

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^{3} ∙ 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^{3} ∙ 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^{3} ∙ 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** ( (ℕ^{*})^{2}, ⊕, ⊙, (∞,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^{3} ∙ 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)]

TQ User guide <<< >>>

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 3.0 Unported