[[:TQ|TQ]] [[tq:ug|User guide]]
====== Simple analyses ======
===== Node activities =====
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 auv 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 V1 on a group
V2 (using the combinatorial semiring) as
act(V1,V2) = ∑{u∈V1 : ∑{v∈V2 : auv } } .
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.
{{tq:pics:violpol2.png?400}}
{{tq:pics:violfas2.png?400}}
{{tq:pics:violall2.png?400}}
**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')
===== Products of a temporal matrix and a temporal vector =====
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
uj = ⊕{i∈1:n : vi ⊙ aij }, 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 : aij ⊙ uj}, 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.
===== Temporal degrees =====
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)''.
{{tq:pics:g2.png?400}}
**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.
===== Clustering coefficients =====
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(n3 ∙ 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) = [ai ⊕ bi, i∈1:n] \\
''VecProd''(a,b) = [ai ⊙ bi, i∈1:n] \\
''VecInv''(a) = [invert(ai), 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)]
>>>