Commonly in network analysis a graph (network) is represented by its adjacency matrix, and the latter may have an enormous order. We show that in many situations (generalizing the case of regular 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 demonstrate 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.
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 recti ed 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 re ects 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 de nite type has de nite numbers of neighbors (adjacent nodes) of each type.
We provide de nitions 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 directed 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.
Types of nodes and type adjacency matrix
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 = f1; 2; : : : ; ng 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.
T = describes a graph which has two types: N1 = f1g and N2 = f2; 3; 4; 5g. The types are characterized by the numbers of neighbors t11 = 0; t12 = 4; t21 = 1; t22 = 2: The corresponding type adjacency matrix is
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 di erent 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 de ne typology.
Example 2. Consider two graphs with adjacency matrices
A1 = BBBB01 00 10 01 10 01 00 00 CCCC ; A2 = BBBB00 00 10 01 10 01 10 00 CCCC :
00 1 0 0 1 0 0 1 1
B1 0 1 0 0 0 0 0 C
BB0 1 0 1 0 0 1 0 CC
Each of these graphs has 4 nodes of degree 2 and 4 nodes of degree 3. However,
their typologies are di erent. The corresponding type adjacency matrices are
Our type adjacency matrix T is kin to a quotient matrix used in spectral graph
theory (e.g. [
A polynomial-time algorithm of subdivision of the set of nodes into types is proposed by Matveenko and Korolev [11].
Some applications in network analysis
It is known that each element aikj 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 tikj 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
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 ~i are
n di = X aij; i = 1; 2; : : : ; n; j=1
S d = X t~ij; ~i = 1; 2; : : : S:
j=1 CB = (I n unit matrix, 1 is the n-vector of all ones; 0M CK = ((I
A) 1
I) 1;
is often referred as vector of Katz centrality measures [
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 = (~I
T) 1 ~1; where ~I; T are S S-matrices, and 1~ is the S-vector of all ones; 0 < Correspondingly, the vector of Katz centrality measures for types is < 1.
C~ K = ((~I
T) 1
~I)1~:
It is easy to show that the vector of -centralities [
A) 1e; k~ = (~I +
T) 1~e: where is any number and e is any vector, can be calculated for types by use of the type adjacency matrix, T: Here k~ is the S-vector of centralities for types, ~I is the S S unit matrix, ~e is S-vector such that e~~i = ei if i 2 N~.
i
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~i if i 2 N~. i 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 de nitions. 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 ^e be the n-vector with components where i 2 N~i. Evidently, Let ^f be the S-vector corresponding to ^e (i.e. f^~i = e^i if i 2 N~i). Then e^i = max ej ;
j2N~i A^e T^f ^e: ^ f : But, according to the Perron-Frobenius theorem, since F is the Frobenius eigenvalue, (1) implies F . Contradiction! (1)
An open question in network analysis is existence of graph classes for which
di erent centrality measures do order the nodes in the same way. One of such
classes (trees with "monotone hierarchies") is found by Bloch et al. [
Notice that it can be shown that the Bonacich centrality exists i 0 < < F : We assume that this condition is satis ed.
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 > Ce,
j 3) CiB > CjB: Proof. 1-2). Vector (1; x)T , where x = C2e=C1e, is the Frobenius eigenvector of matrix T; hence, t11 + t12x = F . Thus, x > 1 i F > d1: On the other hand, F 2 (minfd1; d2g; maxfd1; d2g), which implies equivalence of inequalities F > d1 and d2 > d1. Hence, C2e > C1e i d2 > d1.
1-3). The de nition of the Bonacich centrality implies that the vector of centralities for types is
CB = 1 (1 + (t12 t22); 1 + (t21 t11))T ; where = 1
T rT + 2DetT: It follows that
C1B
C2B = 1 (d1 d2):
(C1B
C2B)
F 1 2 = d1
d2; 1 1 >
F > 2: where 2 is the smallest eigenvalue of matrix T: The existence condition implies Hence, the di erences C1B
C2B and d1 d2; have the same sign.
tu
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.
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 = +1: Types 1; 2; : : : S can be de ned as components of disjoint division of the set of nodes f1,2,. . . , ng such that there is a S S-matrix of weights, T, where t~i~j = aij if nodes i; j are of types ~i; ~j correspondingly. Matrix T, referred further as type weights matrix, de nes a types graph, H, with S nodes. 4.1
Let G be a network of economic agents (e.g. rms, authorities, groups of workers of di erent quali cation types, etc.) Time is discrete, t = 0; 1; : : : Each agent i (i = 1; 2; : : : ; n) at period t is characterized by a positive number xit referred as value (e.g. pro t, 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 coe cient aij > 0: xt+1 i
aiixit; t = 0; 1; : : : ; 2) by the sizes of externalities created by her neighbors, described by coe cients aij > 0: xt+1 i
aij xtj ; j = 1; 2; : : : ; n; j 6= i; t = 0; 1; : : : : We build matrix A of the coe cients, assuming that aij = +1 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 char0 acterizing the equilibrium path given initial values xi :
xit+1 = j=1m;2i;n:::;n aij xtj ; i = 1; 2; : : : ; n The dynamic system can be written as xt+1 = Axt = A x ; t 0 (2) where xt is n-vector with positive components xit, and the matrix-vector multiplication 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 de ned by the structure of matrix A and, correspondingly, of
network G (see [
Example 3. In case of 2 is
Let us consider the set of (oriented) cycles in graph G. To each cycle = (i1; i2; : : : ; ik) an average weight corresponds: a = (ai1i2 ai2i3 : : : aiki1 )1=k. A cycle is called optimal if a = a = min a : 2 In a similar way we can de ne 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. tu
It is shown in [
2 type weights matrix T, the long-run growth factor
Acknowledgements. The research is supported by the Russian Foundation for Basic Research (project 17-06-00618). 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)