Table of Contents

In this section we show how we can use the proposed operations with temporal quantities (the addition) for a simple analysis of temporal networks.

Assume that the values in temporal quantities a_{uv} from a temporal network
matrix **A** are positive real numbers measuring the intensity of the
activity of the node u on the node v.
We define the **activity** of a group of nodes V_{1} on a group
V_{2} (using the combinatorial semiring) as

act(V_{1},V_{2}) = ∑{u∈V_{1} : ∑{v∈V_{2} : a_{uv} } } .

To illustrate the notion of activity we applied it on Franzosi's violence temporal network \citep{RF}. Roberto Franzosi collected from the journal news in the period (January 1919 - December 1922) information about the different types of interactions between political parties and other groups of people in Italy. The violence network contains only the data about violent actions and counts the number of interactions per month.

**Intensity of violent activities of police, fascists and all.**

We determined the temporal quantities

pol = act({police}, V) + act(V, {police}),

fas = act({fascists}, V) + act(V, {fascists}), and

all = act(V, V) .

They are presented in Figure~\ref{viol}. Comparing the intensity charts of police and fascists activity with overall activity we see that most of the violent activities in the first two years 1919 and 1920 were related to the police. In the next two years (1921 and 1922) they were taken over by the fascists.

>>> V = TQ.Ianus2Mat('./violence/violence.ten') >>> list(V.keys()) ['met', 'tit', 'til', 'typ', 'tin', 'mat', 'dim', 'nam'] >>> A = V['mat'] >>> TQ.MatSummary(A) (1, 49, 1, 174) >>> n = len(A); All = range(n) >>> names = V['nam']; Times = V['til'] >>> for i,name in enumerate(names): print(i,name) 0 undefined 1 ? 2 people 3 police 4 land owners 5 anarchists 6 fascists 7 communists 8 workers (agricultural) 9 socialists ... 26 prisoners/arrested 27 foreigners 28 liberals >>> # All-All >>> ca = TQ.ActInt(A,All,All) >>> # police - 3 >>> cb = TQ.sum(TQ.ActInt(A,[3],All),TQ.ActInt(A,All,[3])) >>> # fascists - 6 >>> cc = TQ.sum(TQ.ActInt(A,[6],All),TQ.ActInt(A,All,[6])) >>> comp = {} >>> comp['All-All'] = ca >>> comp['Pol-All'] = cb >>> comp['Fas-All'] = cc >>> comp['info'] = TQ.MatSummary(A) >>> comp['lTimes'] = [lab for i,lab in Times] >>> with open('violComp.json',mode='w',encoding='utf-8') as f: json.dump(comp,f,indent=2) >>>

and drawing in R

> V <- fromJSON(file="violComp.json") > names(V) [1] "info" "Fas-All" "All-All" "lTimes" "Pol-All" > V$info [1] 1 49 1 174 > tMin <- V$info[1]; tMax <- V$info[2]; wMax <- 700 > lTimes <- V$lTimes > times <- c(1,7,13,19,25,31,37,43,49) > all <- V[[3]]; fas <- V[[2]]; pol <- V[[5]] > plotTime(all,tMin,tMax,times,lTimes,wMax,h=250,main='All-All',col='orange') > plotTime(pol,tMin,tMax,times,lTimes,wMax,h=250,main='Police',col='yellow') > plotTime(fas,tMin,tMax,times,lTimes,wMax,h=250,main='Fascists',col='blue')

In some applications the product of a temporal matrix with a temporal vector is useful. There are two products - left and right.

Let **A** be a temporal matrix of size n✕m, **v** a vector of size n, and **u** a vector of size m. The
**product from left** of **A** with **v**, denoted by **u** = **v** ● **A**, is defined by

u_{j} = ⊕{i∈1:n : v_{i} ⊙ a_{ij} }, j∈1:m

and the **product from right** of **A** with **u**, denoted by
**v** = **A** ● **u**, is defined by

v_i = ⊕{j∈1:m : a_{ij} ⊙ u_{j}}, i∈1:n .

In the TQ library both products are implemented as functions `MatVecMulL`

(A,v) and
`MatVecMulR`

(A,v).

If a vector **v** of size n is considered as a column vector - an n✕1 matrix - it holds

**v** ● **A** = (**v**^{T} ⊙ **A**)^{T} , and

**A** ● **u** = **A** ⊙ **u** .

T denotes the matrix transposition operation.

For an ordinary graph with a (binary) adjacency matrix **A** we can
compute the corresponding indegree, **i**, and outdegree, **o**, vectors using (over the combinatorial semiring) the relations

**i** = **e** ● **A** and **o** = **A** ● **e**

where **e** is a column vector of size n = |V| with all
its entries equal to 1. The same holds for temporal networks. In this case
the vector **e** contains as values the temporal unit **1** = [(0,∞,1)].

This is the basis of TQ functions `inDeg(A)`

and `outDeg(A)`

.

**First example network** `testConn.net`

. All unlabeled links have a value of [(1,9,1)].

For a temporal network presented in Figure~\ref{graph} the corresponding temporal indegrees and outdegrees are given in following table:

**Temporal indegrees and outdegrees for the first example network.**

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

For example, the node 5 has in the time interval [1,5) outdegree 2. Because the arc (5,7) disappears at the time point 5 the outdegree of the node 5 diminishes to 1 in the interval [5,9).

>>> N = TQ.Ianus2Mat('./ten/testConn.ten') >>> list(N.keys()) ['met', 'tit', 'til', 'typ', 'tin', 'mat', 'dim', 'nam'] >>> A = N['mat'] >>> TQ.MatSummary(A) (1, 9, 1, 1) >>> id = TQ.inDeg(A); od = TQ.outDeg(A) >>> TQ.VecList(id) 1 : [(1, 9, 1)] 2 : [(1, 9, 2)] 3 : [] 4 : [(1, 3, 1), (3, 9, 2)] 5 : [(1, 9, 1)] 6 : [(1, 9, 1)] 7 : [(1, 5, 1), (7, 9, 1)] 8 : [(1, 9, 2)] 9 : [(1, 9, 2)] 10 : [(1, 9, 3)] 11 : [(1, 9, 2)] 12 : [] 13 : [(2, 8, 2)] 14 : [(2, 8, 2)] 15 : [(2, 8, 2)] >>> TQ.VecList(od) 1 : [(1, 9, 1)] 2 : [(1, 3, 1), (3, 9, 2)] 3 : [(1, 9, 1)] 4 : [(1, 9, 1)] 5 : [(1, 5, 2), (5, 9, 1)] 6 : [(1, 9, 1)] 7 : [(1, 9, 3)] 8 : [(1, 9, 2)] 9 : [(1, 9, 2)] 10 : [(1, 9, 1)] 11 : [(1, 7, 1), (7, 9, 2)] 12 : [] 13 : [(2, 8, 2)] 14 : [(2, 8, 2)] 15 : [(2, 8, 2)] >>>

We will use the simple temporal network from this section also for the illustration of some other algorithms because it allows the users to manually check the presented results.

Let us assume that the network **N** is based on a simple directed graph **G** = (V, A)
without loops. From a simple undirected graph we obtain the corresponding simple
directed graph by replacing each edge with a pair of opposite arcs. In such a
graph the **clustering coefficient**, C(v), of the node
v is defined as the proportion between the number of realized arcs among the node's neighbors and the number
of all possible arcs among the node's neighbors N(v), that is

C(v) = |A(N(v))| / ( k∙(k-1) )

where k is the number of neighbors of the node v. For a node v without neighbors or with a single neighbor we set C(v)=0.

The clustering coefficient measures a local density of the node's neighborhood. A problem with its applications
in network analysis is that the identified densest neighborhoods are mostly very small. For this reason
we provided in Pajek the **corrected clustering coefficient**, C'(v),

C'(v) = |A(N(v))| /( Δ∙(k-1) )

where Δ is the maximum number of neighbors in the network.

To count the number of realized arcs among the node's neighbors we use the observation that each arc forms a triangle with links from its end-nodes to the node v; and that the number of triangles in a simple undirected graph can be obtained as the diagonal value in the third power of the graph matrix (over the combinatorial semiring).

For simple directed graphs the counting of triangles is slightly more complicated.
Let us denote **T** = **A**^{T} and **S** = **A**+**T**. Then the number of triangles can
be read from the diagonal of **SAS** .
This gives us a simple way to count the triangles which is used in the TQ function `clusCoef`

(**A**,type=1) where the parameter type determines the type of normalization:
type = 1 - standard clustering coefficient; type = 2 - corrected clustering coefficient / temporal Δ; type = 3 - corrected clustering coefficient / overall Δ. The time complexity of the function `clusCoef`

is O(n^{3} ∙ L).

Some useful functions:

`nRows`

(**A**) returns the size (number of rows) of matrix **A**.

`VecConst`

(n,v) constructs a vector of size n filled with the value v.

`MatBin`

(**A**) transforms all values in the triples in the matrix **A** to 1.

`MatSetDiag`

(**A**,c) sets all the diagonal entries of the matrix **A** to the value c.

`MatSym`

(**A**) makes the transformation **S** = **A**⊕**T**.
`VecSum`

(a,b) = [a_{i} ⊕ b_{i}, i∈1:n]

`VecProd`

(a,b) = [a_{i} ⊙ b_{i}, i∈1:n]

`VecInv`

(a) = [invert(a_{i}), i∈1:n] in the combinatorial semiring.

`invert`

(a) = [ (s,f,1/v) for (s,f,v) ∈ a ]

`MatProd`

(**A**,**B**) determines the product **A** ⊙ **B**.
`MatProdDiag`

(**A**,**B**) determines only the diagonal vector of the product **A** ⊙ **B**.

In the following tables the ordinary and the corrected clustering coefficients are presented for the first example network and its undirected skeleton.

**Clustering coefficients for the first example network.**

Clustering coefficient Corrected clustering coefficient 1 : [] 1 : [] 2 : [] 2 : [] 3 : [] 3 : [] 4 : [(1, 3, 0.5), (3, 9, 0.1667)] 4 : [(1, 3, 0.25), (3, 9, 0.125)] 5 : [(1, 5, 0.1667), (5, 9, 0.5)] 5 : [(1, 5, 0.125), (5, 9, 0.25)] 6 : [(1, 9, 0.5)] 6 : [(1, 9, 0.25)] 7 : [(1, 5, 0.25), (5, 9, 0.5)] 7 : [(1, 5, 0.25), (5, 7, 0.375), (7, 9, 0.5)] 8 : [(1, 7, 0.4167), (7, 9, 0.5)] 8 : [(1, 7, 0.4167), (7, 9, 0.5)] 9 : [(1, 7, 0.4167), (7, 9, 0.5)] 9 : [(1, 7, 0.4167), (7, 9, 0.5)] 10 : [(1, 7, 0.4167), (7, 9, 0.5)] 10 : [(1, 7, 0.4167), (7, 9, 0.5)] 11 : [(1, 9, 0.5)] 11 : [(1, 7, 0.375), (7, 9, 0.5)] 12 : [] 12 : [] 13 : [(2, 8, 1.0)] 13 : [(2, 8, 0.5)] 14 : [(2, 8, 1.0)] 14 : [(2, 8, 0.5)] 15 : [(2, 8, 1.0)] 15 : [(2, 8, 0.5)]

**Clustering coefficients for the skeleton of the first example network.**

Clustering coefficient Corrected clustering coefficient 1 : [] 1 : [] 2 : [] 2 : [] 3 : [] 3 : [] 4 : [(1, 3, 1.0), (3, 9, 0.3333)] 4 : [(1, 3, 0.5), (3, 9, 0.25)] 5 : [(1, 5, 0.3333), (5, 9, 1.0)] 5 : [(1, 5, 0.25), (5, 9, 0.5)] 6 : [(1, 9, 1.0)] 6 : [(1, 9, 0.5)] 7 : [(1, 5, 0.5), (5, 9, 1.0)] 7 : [(1, 5, 0.5), (5, 7, 0.75), (7, 9, 1.0)] 8 : [(1, 7, 0.8333), (7, 9, 1.0)] 8 : [(1, 7, 0.8333), (7, 9, 1.0)] 9 : [(1, 7, 0.8333), (7, 9, 1.0)] 9 : [(1, 7, 0.8333), (7, 9, 1.0)] 10 : [(1, 7, 0.8333), (7, 9, 1.0)] 10 : [(1, 7, 0.8333), (7, 9, 1.0)] 11 : [(1, 9, 1.0)] 11 : [(1, 7, 0.75), (7, 9, 1.0)] 12 : [] 12 : [] 13 : [(2, 8, 1.0)] 13 : [(2, 8, 0.5)] 14 : [(2, 8, 1.0)] 14 : [(2, 8, 0.5)] 15 : [(2, 8, 1.0)] 15 : [(2, 8, 0.5)]

And the corresponding Python code:

>>> N = TQ.Ianus2Mat('./ten/testConn.ten') >>> list(N.keys()) ['met', 'tit', 'til', 'typ', 'tin', 'mat', 'dim', 'nam'] >>> A = N['mat'] >>> cc1 = TQ.clusCoef(A) >>> print("Clustering coefficient 1"); TQ.VecList(cc1) Clustering coefficient 1 1 : [] 2 : [] 3 : [] 4 : [(1, 3, 0.5), (3, 9, 0.16666666666666666)] 5 : [(1, 5, 0.16666666666666666), (5, 9, 0.5)] 6 : [(1, 9, 0.5)] 7 : [(1, 5, 0.25), (5, 9, 0.5)] 8 : [(1, 7, 0.41666666666666663), (7, 9, 0.5)] 9 : [(1, 7, 0.41666666666666663), (7, 9, 0.5)] 10 : [(1, 7, 0.41666666666666663), (7, 9, 0.5)] 11 : [(1, 9, 0.5)] 12 : [] 13 : [(2, 8, 1.0)] 14 : [(2, 8, 1.0)] 15 : [(2, 8, 1.0)] >>> cc2 = TQ.clusCoef(A,type=2) >>> print("Clustering coefficient 2"); TQ.VecList(cc2) Clustering coefficient 2 1 : [] 2 : [] 3 : [] 4 : [(1, 3, 0.25), (3, 9, 0.125)] 5 : [(1, 5, 0.125), (5, 9, 0.25)] 6 : [(1, 9, 0.25)] 7 : [(1, 5, 0.25), (5, 7, 0.375), (7, 9, 0.5)] 8 : [(1, 7, 0.41666666666666663), (7, 9, 0.5)] 9 : [(1, 7, 0.41666666666666663), (7, 9, 0.5)] 10 : [(1, 7, 0.41666666666666663), (7, 9, 0.5)] 11 : [(1, 7, 0.375), (7, 9, 0.5)] 12 : [] 13 : [(2, 8, 0.5)] 14 : [(2, 8, 0.5)] 15 : [(2, 8, 0.5)] >>> S = TQ.MatSym(A) >>> ccs1 = TQ.clusCoef(S) >>> print("Clustering coefficient 1 / skeleton"); TQ.VecList(ccs1) Clustering coefficient 1 / skeleton 1 : [] 2 : [] 3 : [] 4 : [(1, 3, 1.0), (3, 9, 0.3333333333333333)] 5 : [(1, 5, 0.3333333333333333), (5, 9, 1.0)] 6 : [(1, 9, 1.0)] 7 : [(1, 5, 0.5), (5, 9, 1.0)] 8 : [(1, 7, 0.8333333333333333), (7, 9, 1.0)] 9 : [(1, 7, 0.8333333333333333), (7, 9, 1.0)] 10 : [(1, 7, 0.8333333333333333), (7, 9, 1.0)] 11 : [(1, 9, 1.0)] 12 : [] 13 : [(2, 8, 1.0)] 14 : [(2, 8, 1.0)] 15 : [(2, 8, 1.0)] >>> ccs2 = TQ.clusCoef(S,type=2) >>> print("Clustering coefficient 2 / skeleton"); TQ.VecList(ccs2) Clustering coefficient 2 / skeleton 1 : [] 2 : [] 3 : [] 4 : [(1, 3, 0.5), (3, 9, 0.25)] 5 : [(1, 5, 0.25), (5, 9, 0.5)] 6 : [(1, 9, 0.5)] 7 : [(1, 5, 0.5), (5, 7, 0.75), (7, 9, 1.0)] 8 : [(1, 7, 0.8333333333333333), (7, 9, 1.0)] 9 : [(1, 7, 0.8333333333333333), (7, 9, 1.0)] 10 : [(1, 7, 0.8333333333333333), (7, 9, 1.0)] 11 : [(1, 7, 0.75), (7, 9, 1.0)] 12 : [] 13 : [(2, 8, 0.5)] 14 : [(2, 8, 0.5)] 15 : [(2, 8, 0.5)] >>>

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