A tensor formalism for multilayer network centrality measures using the Einstein product

2025-04-29 0 0 794.01KB 28 页 10玖币

侵权投诉

A tensor formalism for multilayer network centrality

measures using the Einstein product

Smahane El-Halouya, Silvia Noscheseb, Lothar Reichelc

aDepartment of Mathematical Sciences, Kent State University, Kent, OH 44242, USA, and

Laboratory LAMAI, Faculty of Sciences and Technologies, Cadi Ayyad University,

Marrakech, Morocco.

bDipartimento di Matematica “Guido Castelnuovo”, SAPIENZA Universit`a di Roma, P.le

A. Moro, 2, I-00185 Roma, Italy.

cDepartment of Mathematical Sciences, Kent State University, Kent, OH 44242, USA.

Abstract

Complex systems that consist of diverse kinds of entities that interact in diﬀer-

ent ways can be modeled by multilayer networks. This paper uses the tensor

formalism with the Einstein product to model this type of networks. Several

centrality measures, that are well known for single-layer networks, are extended

to multilayer networks using tensors and their properties are investigated. In

particular, subgraph centrality based on the exponential and resolvent of a ten-

sor are considered. Krylov subspace methods based on the tensor format are

introduced for computing approximations of diﬀerent measures for large multi-

layer networks.

Keywords: multilayer networks, centrality measures, adjacency tensor, tensor

functions, Einstein product, Krylov subspace method

2010 MSC: 05C50, 15A18, 65F15

1. Introduction

A network is a set of objects that are connected to each other in some fashion.

Mathematically, a single-layer network is represented by a graph G={V, E},

where the elements of the set V={vi}n

i=1, referred to as vertices or nodes,

represent the objects, and the elements of the set E⊆V×V, designated as

edges, represent the connections between the nodes. We denote an edge from

node vito node vjby vi→vj.

Some real world examples require the modeling of more than one kind of

nodes or of more than one type of edges. This holds, for instance, for the trans-

portation network in a country when considering diﬀerent means of transporta-

tion. The train and bus routes are diﬀerent types of connections and should in

Email addresses: elhalouysmahane@gmail.com (Smahane El-Halouy),

noschese@mat.uniroma1.it (Silvia Noschese), reichel@math.kent.edu (Lothar Reichel)

Preprint submitted to Elsevier August 3, 2023

arXiv:2210.09355v2 [math.NA] 2 Aug 2023

some models be represented by diﬀerent kinds of edges. Moreover, train and

bus stations may make up nodes with diverse properties. The connections be-

tween a train station and an adjacent bus station give rise to yet another kind of

edges connecting diﬀerent kinds of nodes, along which travelers typically walk.

This kind of objects and connections can be modeled by multilayer networks,

which emphasize diﬀerent kinds or connections, known as layers, between pos-

sibly diﬀerent kinds of elements of a network. Each layer is represented by a

single graph that contains the elements, or some of the elements, of the network

and the connections between them in this layer. Edges connecting nodes from

diﬀerent layers model the interactions between diﬀerent layers. Therefore, the

nodes in a multilayer network require two indices, e.g., vℓ

i, where the superscript

ℓdenotes the layer, and the subscript idetermines the node in this layer. The

set VL=V×Lrepresents all possible combinations of node-layers, where the

set Vis made up of all nodes of the network considered. Each layer may be

made up of Vor some elements of V, and Lis the set of layers. The set of

edges E⊆VL×VLrepresents all edges of the network. The special case when

the set of nodes is the same in all layers, and edges that connect nodes in dif-

ferent layers are only allowed between a node and its copy in another layer, is

known as a multiplex network. A nice recent paper by Bergermann and Stoll

[7] studies multiplex networks and generalized matrix function-based centrality

measures to this kind of networks. The authors use supra-adjacency matrices to

represent multiplex networks. Recently, a global measure of communicability in

a multiplex network, computed by means of the Perron root, and the right and

left Perron vectors of the supra-adjacency matrix associated with this kind of

network was introduced in [16]. We are interested in using tensors for network

analysis, because they arise naturally when modeling multilayer networks.

The model mentioned above can be generalized to represent not only net-

works with multiple layers but also diﬀerent aspects. To allow for the modeling

of more than one aspect, we deﬁne a sequence {Lj}d

j=1 of sets of elementary

layers with dbeing the number of aspects that we would like to model; Ljis the

set of layers for aspect j. Then the total number of layers is |L1|×|L2|×. . .×|Ld|

and we have VL=V×L1×. . . ×Ld. The nodes now are identiﬁed by using

d+1 indices vℓ1,...,ℓd

i, where the subscript iindicates the number of the node and

the superscript ℓ1, . . . , ℓdshows the speciﬁc layer. For more details on this kind

of generalization, we refer to [12, 30] and the references therein, where general

frameworks for multilayer network are discussed together with their mathemati-

cal formulation. Figure 1 illustrates a simple multilayer network with 2 aspects;

this ﬁgure can also be found in [9]. An example of a real multilayer network

with multiple aspects in biology is provided in [32], where the ﬁrst aspect is

the type of data (genomic, metabolomic, or proteomic), and the second aspect

models diﬀerent biological pathways; see Figure 2 in [32].

Single-layer networks are often represented by an adjacency matrix, which

is helpful for extracting information about the network, e.g, by evaluating func-

tions of the the adjacency matrix or by computing certain eigenvectors of this

matrix. For instance, Estrada and Higham [20] describe how the matrix ex-

ponential and resolvent can be used to determine how easy it is to communi-

Figure 1: An example of a multilayer network with a set of four nodes V={1,2,3,4}and two

aspects, the corresponding elementary layer sets L1={A, B}and L2={X, Y }. The total

number of layers is four and they are (A, X), (A, Y ), (B, X) and (B, Y ). Each layer includes

some of the elements of V.

cate between nodes in a single-layer network, and which nodes are the most

important ones; see also Estrada [18] and references therein. For multilayer

networks, we use tensors, i.e., a multidimensional generalization of matrices,

and represent the network by a 2(d+ 1)-order adjacency tensor Aof size

(|V|×|L1| × . . . × |Ld|)×(|V|×|L1| × . . . × |Ld|), where |V|denotes the total

number of nodes, and |Lj|designates the number of layers for property j, for

j= 1,2, . . . , d. The entry A(i, ℓ1, . . . , ℓd, j, k1, . . . , kd) of the tensor Afor an

unweighted multilayer network with sets of layers Lj,j= 1,2, . . . , d, is one if

there is an edge vℓ1,...,ℓd

i→vk1,...,kd

j; otherwise the tensor entry is zero. For a

weighted network a tensor entry 1 may be replaced by a real, generally positive,

number. In a directed network some of the edges represent “one-way streets”.

Note that some nodes may not be present in all layers. Therefore, considering

empty nodes is necessary to allow the tensorial representation. For instance,

the network illustrated in Figure 1 can be represented by a 6th order tensor of

size 4 ×2×2×4×2×2 by adding empty nodes so that every layer is made up

of 4 nodes.

Adjacency tensors allow us to capture the structure and complexity of rela-

tionships between the nodes of a multilayer network. We are interested in in-

vestigating and generalizing some centrality measures that are well established

for single-layer networks to multilayer networks by using the tensor formalism

and applying tensor tools, such as the Einstein product and tensor functions.

Several centrality measures have been studied for multilayer networks using the

tensor formalism in [13]. Eigenvector multicentrality has been investigated for

multilayer networks via a tensor-based framework in [35]; see also [11]. In addi-

tion to generalizing centrality measures that are commonly used for single-layer

networks to multilayer networks, we describe practical and eﬃcient ways to

compute these measures by using Krylov subspace methods based on the tensor

format.

This paper is organized as follows. Tensor notation, deﬁnitions, and proper-

ties used throughout this paper are described in Section 2. Section 3 discusses

the extension of matrix functions to tensor functions using the Einstein tensor

product. We deﬁne centrality measures for multilayer networks based on the

tensor representation and tensor functions. Section 4 describes Krylov subspace

methods based on the tensor format using the Einstein product, and discusses

their application to the approximation of tensor functions. Section 5 presents a

few computed examples and Section 6 contains concluding remarks.

2. Preliminaries

This section presents notation and properties of tensors that will be used

throughout this paper. We start with a generalization of the matrix-matrix

product to tensors that is referred to as the Einstein product.

Deﬁnition 1 (Einstein Product). Let A ∈ RI1×...×IN×J1×...×JMand B ∈

RJ1×...×JM×K1×...×KLbe tensors of orders N+Mand M+L, respectively. The

product C=A ∗MB ∈ RI1×...×IN×K1×...×KLof the tensors Aand Bis a tensor

of order N+Lwith entries

Ci1,...,iN,k1,...,kL=X

j1,...,jM

Ai1,...,iN,j1,...,jMBj1,...,jM,k1,...,kL.

It is commonly referred to as the Einstein product; see [8, 10, 15]. The subscript

Min ∗Mindicates the last and ﬁrst Mdimensions of Aand B, respectively,

over which the sum is evaluated.

The identity tensor I= [Ii1,...,iN,j1,...,jN]∈RI1×...×IN×I1×...×INunder the

Einstein product has the entries

Ii1,...,iN,j1,...,jN=1,if ik=jk,for k= 1,2, . . . , N,

0,otherwise.

Remark 1. A tensor of even order A ∈ RI1×···×IN×J1×···×JNis said to be

square if the ﬁrst set of dimensions equals the second set, i.e., if Ik=Jkfor

k= 1,2, . . . , N; see, e.g., [33]. The adjacency tensor of a multilayer network is

of even order and square, however, for some computations tensors of diﬀerent

orders are required. This is possible when using the Einstein product by choosing

a suitable number of dimensions over which we carry out the summation.

Remark 2. The transpose of a tensor A ∈ RI1×...×IN×J1×...×JMis a tensor

B ∈ RJ1×...×JM×I1×...×INsuch that Ai1,...,iN,j1,...,jM=Bj1,...,jM,i1,...,iN; see,

e.g., [33].

The n-mode product is a well-known tensor-matrix product; see [29]. For

an Nth order tensor A ∈ RI1×...×INand a matrix A∈RIn×J, their n-mode

product is an Nth order tensor A ×nA∈RI1×...In−1×J×In+1 ×...IN.

If A ∈ RI1×...×IN×Jis an (N+ 1)th order tensor and A∈RJ×I, then the

n-mode product of Aand Aover mode N+1 is the same as the Einstein product

when summing over the last mode of the tensor. In other words, we have

A ∗1A=A ×N+1 AT.

We can reorganize the entries of a tensor in diﬀerent ways to obtain a 2D

array, i.e., a matrix. This transformation is known as matricization or ﬂattening.

We ﬂatten a tensor by using lexicographical ordering of the indices.

Deﬁnition 2 (Tensor ﬂattening). Let A ∈ RI1×...×IN×J1×...×JMbe a tensor

of order N+M. The elements of the matrix A∈RI1...IN×J1...JMobtained by

ﬂattening the tensor Aare given by

Ai,j =Ai1,...,iN,j1,...,jM,

where

i=i1+

p=2

(ip−1)

p−1

q=1

Iq,

j=j1+

p=2

(jp−1)

p−1

q=1

Jq.

Here and below the indices ipand jplive in their domains, i.e., 1≤ip≤Ip

for 1≤p≤N, and 1≤jq≤Jpfor 1≤q≤M. We deﬁne A= mat(A)and

A= mat−1(A).

Remark 3. For a multiplex network, mat(A)is the supra-adjacency matrix

deﬁned in [7].

Proposition 1. Let A ∈ RI1×...×IN×J1×...×JMand B ∈ RJ1×...×JM×K1×...×KL

be tensors of orders N+Mand M+L, respectively. Then

mat(A ∗MB) = mat(A)·mat(B),

where ·denotes the usual matrix product.

Proof: The result follows by direct computations; see [10] for details. □

Deﬁnition 3. The following deﬁnitions can be found in, e.g., [10, 28, 33].

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

AtensorformalismformultilayernetworkcentralitymeasuresusingtheEinsteinproductSmahaneEl-Halouya,SilviaNoscheseb,LotharReichelcaDepartmentofMathematicalSciences,KentStateUniversity,Kent,OH44242,USA,andLaboratoryLAMAI,FacultyofSciencesandTechnologies,CadiAyyadUniversity,Marrakech,Morocco.bDipartimentod...

展开>> 收起<<

A tensor formalism for multilayer network centrality measures using the Einstein product.pdf

共28页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

A tensor formalism for multilayer network centrality measures using the Einstein product

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: