Orthogonal Expansion of Network Functions
- PDF / 986,541 Bytes
- 22 Pages / 439.642 x 666.49 pts Page_size
- 32 Downloads / 198 Views
Orthogonal Expansion of Network Functions Mohammed Al Mugahwi1 · Omar De la Cruz Cabrera1 · Lothar Reichel1 Received: 16 September 2019 / Accepted: 29 May 2020 / © Vietnam Academy of Science and Technology (VAST) and Springer Nature Singapore Pte Ltd. 2020
Abstract The power series expansion of functions of the adjacency matrix for a network can be interpreted in terms of walks in the network. This makes matrix functions, such as the exponential or resolvent, useful for the analysis of graphs. For instance, these functions shed light on the relative importance of the nodes of the graph and on the overall connectivity. However, the power series expansions may converge slowly, and the coefficients of these expansions typically are not helpful in assessing how important longer walks are in the network. Expansions of matrix functions in terms of orthogonal or bi-orthogonal polynomials make it possible to determine scaling parameters so that a given network has a specified effective diameter (the length after which walks become essentially irrelevant for the connectivity of the network). We describe several approaches for generating orthogonal and bi-orthogonal polynomial expansions, and discuss their relative merits for network analysis. Keywords Networks · Orthogonal polynomials · Matrix functions · Centrality Mathematics Subject Classification (2010) 05C82 · 15A16 · 65F60
1 Introduction Many complex systems that describe the interaction between entities can be modeled by networks. For mathematical and statistical modeling, as well as for analysis, networks are usually represented by a graph G = {V , E}, which consist of a set of vertices V = {vj }nj=1 and a set of edges E = {ek }k=1 , the latter being the links between the vertices. A graph may be undirected, in which case each edge ek represents a “two-way street” between a pair of Dedicated to Volker Mehrmann on the occasion of his 65th birthday. Lothar Reichel
[email protected] Mohammed Al Mugahwi [email protected] Omar De la Cruz Cabrera [email protected] 1
Department of Mathematical Sciences, Kent State University, Kent, OH 44242, USA
M. Al Mugahwi et al.
vertices {vi , vj }, or directed, in which case at least one of the edges is a “one-way street” between a pair of nodes. Examples of networks include: – –
–
Flight networks, with airports represented by vertices and flights by directed edges. Social networking services, such as Facebook, Twitter, and Snapchat, with members or accounts represented by vertices, and interactions between any two accounts by edges, which can be undirected (e.g., a “friendship”) or directed (e.g., “follow” or “like”). Phone networks can be modeled by directed graphs, in which phone numbers are represented by vertices, and text messages or calls that occur in a fixed span of time by edges from the originator to the receiver.
Numerous applications of networks and associated directed or undirected graphs are described in [12, 14, 17, 19, 31]. We consider unweighted graphs G = {V , E} with n vertices vj and edges ek , w
Data Loading...
