=Paper=
{{Paper
|id=Vol-1975/paper31
|storemode=property
|title=On a Typology of Nodes and Its Applications in Network Analysis
|pdfUrl=https://ceur-ws.org/Vol-1975/paper31.pdf
|volume=Vol-1975
|authors=Vladimir Matveenko
|dblpUrl=https://dblp.org/rec/conf/aist/Matveenko17
}}
==On a Typology of Nodes and Its Applications in Network Analysis==
https://ceur-ws.org/Vol-1975/paper31.pdf
On a Typology of Nodes and Its Applications in
Network Analysis
Vladimir Matveenko
National Research University Higher School of Economics, St. Petersburg, Russia,
vmatveenko@hse.ru,
https://www.hse.ru/en/org/persons/202791
Abstract. Commonly in network analysis a graph (network) is repre-
sented by its adjacency matrix, and the latter may have an enormous
order. We show that in many situations (generalizing the case of regu-
lar graph) a much smaller matrix (referred as type adjacency matrix)
may be used instead. We introduce concepts of the types of nodes and
of the type adjacency matrix, study properties of the latter and demon-
strate some of its applications in social and economic network analysis.
In particular, we consider centrality measures in undirected networks
and dynamic patterns in a development model based on the structure of
optimal paths in directed weighted networks.
Keywords: graph, network analysis, adjacency matrix, types of nodes,
centrality, optimal paths
1 Introduction
Commonly in network analysis and its economic and social applications a graph
(network) is represented by its adjacency matrix. A drawback of the adjacency
matrix is that it can have an enormous size, and this may impede working
with graphs possessing big size but simple structure. This drawback may be
somehow rectified if another kind of matrix, ”type adjacency matrix”, is used.
The type adjacency matrix often has a much smaller size in comparison with the
adjacency matrix and reflects important features of the structure of the graph
in an aggregate form. We will show that in many respects the type adjacency
matrix may serve as a substitute for the adjacency matrix.
The presence of the type adjacency matrix corresponds to the fact that the
set of nodes of undirected graph can be divided into a minimal number of disjoint
subsets (types) in such way that each node of definite type has definite numbers
of neighbors (adjacent nodes) of each type.
We provide definitions of the types of nodes and the type adjacency matrix
and study the properties of the latter and its applications to several centrality
measures. Also we introduce an analogue of the type adjacency matrix for di-
rected weighted network and demonstrate its use in analysis of dynamic patterns
in an economic development model based on the structure of optimal paths in
directed networks.
2 Types of nodes and type adjacency matrix
2.1 Basic concepts
Let G be undirected connected graph with n nodes and A be its adjacency
matrix, i.e. a n × n matrix such that aij = aji = 1 if in G there is an edge
connecting nodes i and j, and aij = aji = 0 otherwise; aii = 0 for all i =
1, 2, . . . , n.
The set of nodes, N = {1, 2, . . . , n} may be decomposed into minimal number
S of disjoint classes Ni (i = 1, 2, . . . , S) in such way that any node belonging
class i has tij neighbors from class j (j = 1, 2, . . . , S). The classes will be referred
as types of nodes. Type i is characterized by vector ti = (ti1 , ti2 , . . . , tiS . We will
consider a S × S-matrix T with rows t1 , . . . , tS , which will be referred as type
adjacency matrix of graph G.
Example 1. The adjacency matrix
01111
1 0 1 1 0
1 1 0 0 1
A=
1 1 0 0 1
10110
describes a graph which has two types: N1 = {1} and N2 = {2, 3, 4, 5}. The types
are characterized by the numbers of neighbors t11 = 0, t12 = 4, t21 = 1, t22 = 2.
The corresponding type adjacency matrix is
04
T= .
12
Evidently, the familiar class of regular (equidegree) graphs is the class of
one-type graphs. The next in the order of the generalized regular graphs are the
classes of 2-types graphs, 3-type graphs, etc.
It is easy to see that there exist graphs of different size but with the same
typology, and that for any (maybe small) number of types there exist graphs of
unlimited size possessing given typology.
In any 2-types graph, the types correspond degrees of nodes. However, as
the following example demonstrates, the distribution of degrees does not define
typology.
Example 2. Consider two graphs with adjacency matrices
01001001 01000001
1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0
0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1
0 0 1 0 1 0 0 0
, A2 = 0 0 1 0 1 0 1 0 .
A1 = 1 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0
0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0
0 0 1 0 0 1 0 1 0 0 0 1 0 1 0 1
10100010 10100010
Each of these graphs has 4 nodes of degree 2 and 4 nodes of degree 3. However,
their typologies are different. The corresponding type adjacency matrices are
02 11
T1 = , T2 = .
21 21
2.2 Relation to other work
Our type adjacency matrix T is kin to a quotient matrix used in spectral graph
theory (e.g. [6, 2]). Our subdivision of the set of nodes of graph into types is a
generalization of the modular aggregation of Allouch [1], where module is defined
as a subset of nodes, such that each node in a module has the same neighbors.
It can be seen that each division into modules is a division into types, but not
the opposite. Estrada [7] (section 2.4) provided examples of extension of the
adjacency relations to links, cliques and other objects; however, his approach is
rather far from our theory.
A polynomial-time algorithm of subdivision of the set of nodes into types is
proposed by Matveenko and Korolev [11].
3 Some applications in network analysis
3.1 Numbers of walks
It is known that each element akij of the k-th power of the adjacency matrix, Ak ,
is equal to the number of all k-step walks between nodes i and j. In a parallel
way, each element tkij of the k-th power of the type adjacency matrix, Tk , is the
number of all k-step walks between any i-th type node and all j-th type nodes.
3.2 Centrality measures
The degree centrality may be calculated in similar ways by use of either the
adjacency matrix, A, or the type adjacency matrix T. The degrees of node i
and of any node of type ĩ are
n
X
di = aij , i = 1, 2, . . . , n,
j=1
S
X
d= tĩj , ĩ = 1, 2, . . . S.
j=1
If i ∈ Nĩ , then di = dĩ .
Remind that the vector of Bonacich centrality measures for nodes [4] is
CB = (I − αA)−1 · 1,
where I is the n × n unit matrix, 1 is the n-vector of all ones; 0M α < 1. The
vector
CK = ((I − αA)−1 − I) · 1,
is often referred as vector of Katz centrality measures [8, 3].
Since only the summary discounted numbers of walks from node i (but not
of walks to particular nodes) are needed in calculation of both Katz-Bonacich
centrality measures, the type adjacency matrix, T, can be used instead of the
adjacency matrix, A. We obtain the vector of Bonacich centrality measures for
types:
C̃B = (Ĩ − αT)−1 · 1̃,
where Ĩ, T are S × S-matrices, and 1̃ is the S-vector of all ones; 0 < α < 1.
Correspondingly, the vector of Katz centrality measures for types is
C̃K = ((Ĩ − αT)−1 − Ĩ)1̃.
It is easy to show that the vector of α-centralities [5],
k = (I + αA)−1 e,
where α is any number and e is any vector, can be calculated for types by use
of the type adjacency matrix, T:
k̃ = (Ĩ + αT)−1 ẽ.
Here k̃ is the S-vector of α centralities for types, Ĩ is the S × S unit matrix, ẽ
is S-vector such that ẽĩ = ei if i ∈ Nĩ .
The following theorem implies that the type adjacency matrix T can be used
instead of the adjacency matrix A for calculation of eigenvalue centralities.
Theorem 1. 1. Let λ be an eigenvalue of the type adjacency matrix T and b̃ be
corresponding eigenvector. Then λ is also an eigenvalue of the adjacency matrix
A, and the corresponding eigenvector is b, where bi = b̃ĩ if i ∈ Nĩ .
2. Let λF be the Frobenius eigenvalue of matrix T. Then λF is also the
Frobenius eigenvalue of matrix A.
Proof. Part 1 follows directly from the definitions. To prove ad absurdum part
2, assume that the Frobenius eigenvalue of matrix A is µ 6= λF . Part 1 implies
µ > λF . Let e be the Frobenius eigenvector of matrix A, and ê be the n-vector
with components
êi = max ej ,
j∈Nĩ
where i ∈ Nĩ . Evidently,
Aê ≥ µê.
Let f̂ be the S-vector corresponding to ê (i.e. fˆĩ = êi if i ∈ Nĩ ). Then
Tf̂ ≥ µf̂ . (1)
But, according to the Perron-Frobenius theorem, since λF is the Frobenius eigen-
value, (1) implies λF ≥ µ. Contradiction! t
u
3.3 Coincidence of the orders generated by different centrality
measures
An open question in network analysis is existence of graph classes for which
different centrality measures do order the nodes in the same way. One of such
classes (trees with ”monotone hierarchies”) is found by Bloch et al. [3]. We find
that our class of 2-types graphs is another such class.
Notice that it can be shown that the Bonacich centrality exists iff 0 < α < λF .
We assume that this condition is satisfied.
Theorem 2. For nodes i = 1, 2, . . . , n let di , Cie , CiB be, correspondingly, degree,
the eigenvalue centrality and the Bonacich centrality. For any 2-types graph, the
following statements for a pair of nodes i, j are equivalent:
1) di > dj ,
2) Cie > Cje ,
3) CiB > CjB .
Proof. 1-2). Vector (1, x)T , where x = C2e /C1e , is the Frobenius eigenvector of
matrix T; hence, t11 + t12 x = λF . Thus, x > 1 iff λF > d1 . On the other
hand, λF ∈ (min{d1 , d2 }, max{d1 , d2 }), which implies equivalence of inequalities
λF > d1 and d2 > d1 . Hence, C2e > C1e iff d2 > d1 .
1-3). The definition of the Bonacich centrality implies that the vector of
centralities for types is
1 T
CB = (1 + α(t12 − t22 ), 1 + α(t21 − t11 )) ,
∆
where ∆ = 1 − αT rT + α2 DetT. It follows that
1
C1B − C2B = (d1 − d2 ).
∆
This implies
1 1
(C1B − C2B )α − λF − λ2 = d1 − d2 ,
α α
where λ2 is the smallest eigenvalue of matrix T. The existence condition implies
1
> λF > λ2 .
α
Hence, the differences C1B − C2B and d1 − d2 , have the same sign. t
u
The list of the centrality measures in Theorem 2 may be enlarged, but in this
short paper we limit ourselves only by the three measures.
4 Typology of directed graphs
Let G be a strongly connected directed weighted graph with n nodes, and A be
its n × n weights matrix. If there is no arc going from node i to node j, then
it is taken aij = +∞. Types 1, 2, . . . S can be defined as components of disjoint
division of the set of nodes {1,2,. . . , n} such that there is a S × S-matrix of
weights, T, where tĩj̃ = aij if nodes i, j are of types ĩ, j̃ correspondingly. Matrix
T, referred further as type weights matrix, defines a types graph, H, with S nodes.
4.1 Application to a model of economic development
Let G be a network of economic agents (e.g. firms, authorities, groups of workers
of different qualification types, etc.) Time is discrete, t = 0, 1, . . . Each agent i
(i = 1, 2, . . . , n) at period t is characterized by a positive number xti referred
as value (e.g. profit, income, welfare). The agent’s current value depends on the
values of herself and her neighbors in the previous time period. Following [10],
we assume that the development of each agent i (i = 1, 2, . . .) is limited:
1) by her own potential possibilities described by coefficient aij > 0:
xt+1
i ≤ aii xti , t = 0, 1, . . . ;
2) by the sizes of externalities created by her neighbors, described by coeffi-
cients aij > 0:
xt+1
i ≤ aij xtj , j = 1, 2, . . . , n; j 6= i; t = 0, 1, . . . .
We build matrix A of the coefficients, assuming that aij = +∞ if there is no
arc going from node i to node j, or if agent j does not limit anyway the agent
i’s development.
Each agent maximizes her value; this leads to the following equations char-
acterizing the equilibrium path given initial values x0i :
xt+1
i = min aij xtj , i = 1, 2, . . . , n
j=1,2,...,n
The dynamic system can be written as
xt+1 = Axt = At x0 , (2)
where xt is n-vector with positive components xti , and the matrix-vector multi-
plication and the matrix power are in sense of tropical/idempotent mathematics
with operation + = min and usual multiplication.
The dynamic system (2) may demonstrate various patterns (e.g. entrance to
a steady state, to a ray of stable growth or decline, to a limit cycle, etc). The
pattern is totally defined by the structure of matrix A and, correspondingly, of
network G (see [9, 10]) .
Let us consider the set Σ of (oriented) cycles in graph G. To each cycle
σ = (i1 , i2 , . . . , ik ) an average weight corresponds: aσ = (ai1 i2 ai2 i3 . . . aik i1 )1/k .
A cycle σ ∗ is called optimal if
aσ∗ = a∗ = min aσ .
σ∈Σ
In a similar way we can define optimal cycle in the types graph H and the
corresponding minimal average weight, t∗ .
Theorem 3. a∗ = t∗ .
Proof. Evidently, to each cycle in graph G a unique cycle in the types graph H
corresponds. Vice versa, to each cycle in the types graph H at least one cycle
in graph G corresponds. It is easily checked that the average weights of these
cycles do coincide. Hence, the minimal average weights also do coincide. t
u
It is shown in [9, 10] that a∗ is the long-run growth factor of the dynamic
system (2). Hence, by Theorem 3, the growth factor is defined by the type weights
matrix T.
Example 3. In case of 2 × 2 type weights matrix T, the long-run growth factor
is √
a∗ = t∗ = min{t11 , t22 , t12 t21 }.
If t∗ > (<)1, there is a long-run growth (decline) in system (2).
Acknowledgements. The research is supported by the Russian Foundation
for Basic Research (project 17-06-00618).
References
1. Allouch, N.: Aggregation in networks. Queen Mary University of London. School of
Economics and Finance. (2016)
2. Atik, F., Panigrahi, P.: Graphs with few distinct distance eigenvalues irrespective
of the diameters. Electr. J. Lin. Alg. 29, 194–205 (2015)
3. Bloch, F., Jackson, M.O., Tebaldi, P.: Centrality measures in networks. arXiv:
1608.05845 (2017)
4. Bonacich, P.: Factoring and weighting approaches to status scores and clique iden-
tification. J. of Math. Sociology 2, 113–120 (1972)
5. Bonacich, P., Lloyd, P.: Eigenvector-like measures of centrality for asymmetric re-
lations. Soc. Networks 23, 191–201 (2001)
6. Brouwer, A.E., Haemers W.H.: Spectra of graphs. Springer, New York (2012)
7. Estrada, E. The structure of complex networks. Theory and applications. Oxford
University Press, Oxford (2011)
8. Goyal, S.: Connections: an introduction to the economics of networks. Princeton
University Press, Princeton (2009)
9. Matveenko, V.: Optimal trajectories of a dynamic programming scheme and ex-
tremal degrees of nonnegative matrices (In Russian). Diskretnaya Matematika 2,
59–71 (1990)
10. Matveenko, V.: Development with positive externalities: the case of the Russian
economy. J. Pol. Modeling 17, 207–221 (1995)
11. Matveenko, V., Korolev, A.: Equilibria in networks with production and knowledge
externalities. Springer Proc. Math. Stat. 156, 291–331 (2016)