The eﬀect of the Katz parameter on node ranking with a medical application Hunter RehmID1 Mona MatarID2 Puck RombachID1 and

2025-04-26 1 0 515.23KB 12 页 10玖币

侵权投诉

The eﬀect of the Katz parameter on node ranking, with

a medical application

Hunter Rehm ID 1,*, Mona Matar ID 2, Puck Rombach ID 1, and

Lauren McIntyre2

1Department of Mathematics and Statistics, University of Vermont,

Burlington, VT, USA

2NASA Glenn Research Center, Cleveland, OH, USA

*Corresponding author: Hunter.Rehm@uvm.edu

October 13, 2022

Abstract

Katz centrality is a popular network centrality measure. It takes a (weighted) count

of all walks starting at each node, with an additional damping factor of αthat tunes

the inﬂuence of walks as lengths increase. We introduce a tool to compare diﬀerent

centrality measures in terms of their node rankings, which takes into account that a

relative ranking of two nodes by a centrality measure is unreliable if their scores are

within a margin of error of one another. We employ this tool to understand the eﬀect of

the α-parameter on the lengths of walks that signiﬁcantly aﬀect the ranking of nodes.

In particular, we ﬁnd an upper bound on the lengths of the walks that determine the

node ranking up to this margin of error. If an application imposes a realistic bound

on possible walk lengths, this set of tools may be helpful to determine a suitable value

for α. We show the eﬀect of αon rankings when applied to the Susceptibility Infer-

ence Network, which contains subject matter expert informed data that represents the

probabilities of medical conditions progressing from one to another. This network is

part of the Medical Extensible Dynamic Probabilistic Risk Assessment Tool, developed

by NASA, an event-based risk modeling tool that assesses human health and medical

risk during space exploration missions.

Keywords – network, centrality, Katz parameter, ranking.

MSC – 68R10, 65F60.

1 Introduction

Networks are structures that naturally appear in every aspect of life and are studied in a

wide range of disciplines from sociology, to biology, and engineering [12, 14, 21, 23]. One

common question asked in network theory is how to rank the nodes according to importance,

where importance can have many meanings depending on the application [7]. Many ranking

algorithms are based on a, possibly weighted, count of walks that a node is contained in.

arXiv:2210.06392v1 [physics.soc-ph] 12 Oct 2022

Examples of such centrality measures are degree, betweenness [13], closeness [2, 3, 11],

eigenvector [5, 6], PageRank [22], and Katz centrality [15]. The latter is the focus of this

paper.

Katz centrality, developed by Leo Katz in 1953 [15], has been used in numerous applica-

tions [10, 24]. The Katz centrality of a node is a weighted count of all walks of any length

starting at the node. Each walk of length kis weighted by αk, where αis called the Katz

parameter. We give a formal deﬁnition of Katz centrality in Section 1.1. Since the Katz

parameter has a decaying eﬀect, we can approximate the Katz centrality by ignoring the

contribution of walks past a given length L. In [19] and [20], the authors numerically explore

this type of approximation. In Section 2, we give a lower bound on this value L(in terms of

α) that guarantees a desired level of accuracy in terms of the Katz centrality and its node

ranking.

As an application, we look at a model developed by the National Aeronautics and Space

Administration (NASA) called the Susceptibility Inference Network (SIN). This network

models a set of medical conditions that may progress from one to another with some prob-

ability. The application of Katz centrality in this setting estimates the eﬀect of a medical

condition and its consequent progressions on astronaut productivity. NASA wishes to use

the progression risk to identify a condition (or group of conditions) that highly inﬂuences

the risk of the crew members.

This paper is organized as follows. Section 1.1 reviews useful graph theory concepts,

deﬁnitions and basic results. Section 1.2 introduces a network of medical conditions created

by subject matter experts, which we will later use as a case study. In Section 2, we bound

the error generated from approximating the Katz centrality by restricting the number of

steps allowed in a walk, and develop a relationship between that number and the Katz

parameter α. An example of the relationship between αand the α-Katz centrality node

ranking is in Section 2 and our medical application in Section 3. Additionally, we assess

the upper bound given in Section 2 to the true length in Section 4. Finally, the results and

future work are addressed in Section 5.

1.1 Deﬁnitions

In this section, we provide basic deﬁnitions for the graph theoretical structures and tools

used for the results in Section 2.

Deﬁnition 1. (Weighted, directed network) Let N= (V, E, w)be an edge-weighted,

directed network consisting of V, the set of n nodes,E⊆V×V, the set of edges, and a

weight function w:E→R+.

We represent such a network by an adjacency matrix A=A(N), where the entry Aij

is the weight of the edge from node ito node j, or Aij = 0 if there is no edge from ito j

in N. Let Wbe an n-dimensional vector of non-negative node weights. In a setting where

edges and/or nodes are unweighted, weights in Aand Ware all set to 1.

For example, in our application in Section 3, our weighted, directed network has nodes

that represent medical conditions and the node weights represent their severity, while edge

weights represent the probability of one medical condition progressing to another.

The spectral radius ρof N(or A) is the maximum modulus of the eigenvalues of A. A

walk of length kfrom node uto vis a sequence of kedges (vi, vi+1)∈E,i∈[1, k]such that

v1=uand vk+1 =w. The distance from uto vis the length of a shortest walk from uto

v. The k-hop neighborhood of a node v∈Vis the set of nodes at a distance less than or

equal to kfrom v. A centrality measure is a function that assigns a real number to each

node, in order to evaluate its relative importance to other nodes. Each centrality measure

gives a (partial) ranking of the nodes, which reﬂects their relative importance.

Deﬁnition 2. (Katz centrality) Let Nbe an edge-weighted, directed network with node

weights W. Let A=A(N)with spectral radius ρ, and let α∈(0,1/ρ). The α-Katz

centrality vector [8, 9, 15], is deﬁned as

C(α) = ∞

i=1

αkAk!·W=(I−αA)−1−I·W.

The α-Katz score of a particular node ican then be expressed as

C(α)i=

∞

k=1

j=1

WjαkAkij .

The (α, `)-Katz centrality vector [1, 4, 16] is

C(α, `) = `

i=1

αkAk!·W

and for a particular node i, the (α, `)-Katz score can be written as

C(α, `)i=

k=1

j=1

WjαkAkij .

Both C(α)and C(α, `)measure the downstream inﬂuence of nodes, since they are

weighted sums over outgoing walks. Replacing the matrix Aby its transpose ATreverses

edge directions, which results in taking weighted sums over incoming walks instead, and

measuring the upstream inﬂuence [8, 21].

Deﬁnition 3 provides a tool to compare centrality measures purely in terms of their

relative node rankings. Intuitively, we may set a threshold for a centrality measure C,

such that |Ci−Cj| ≥ implies that Cprovides a relative ranking of nodes iand j. If

|Ci−Cj|< , we cannot reliably recover a ranking from C. For two centrality measures C

and C0, we compare their rankings and conclude that they agree on a ranking if they agree

for every node pair where both of their rankings are reliable.

Deﬁnition 3. (-agreement) Let Nbe a weighted, directed network, , 0>0, and Cand

C0be centrality measures. The nodes i, j ∈V(N)are (, 0)-properly ranked with respect to

Cand C0if the following holds:

1. |Ci−Cj|<  or |C0

i−C0

j|< 0,

2. otherwise, Ci−Cjand C0

i−C0

jhave the same sign.

We say that Cand C0(, 0)-agree on Nif every pair of nodes in Nis (, 0)-properly ranked

with respect to Cand C0. If =0, we simply say -proper ranking and -agreement.

Proposition 1. Let Cand C0be two centrality measures on a network N. If

kC−C0k∞< ,

then Cand C0-agree.

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

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

10 玖币 0人已下载

立即下载

摘要：

TheeectoftheKatzparameteronnoderanking,withamedicalapplicationHunterRehmID1,*,MonaMatarID2,PuckRombachID1,andLaurenMcIntyre21DepartmentofMathematicsandStatistics,UniversityofVermont,Burlington,VT,USA2NASAGlennResearchCenter,Cleveland,OH,USA*Correspondingauthor:Hunter.Rehm@uvm.eduOctober13,2022Abstr...

展开>> 收起<<

The eﬀect of the Katz parameter on node ranking with a medical application Hunter RehmID1 Mona MatarID2 Puck RombachID1 and.pdf

共12页,预览3页

还剩页未读，继续阅读

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

The eﬀect of the Katz parameter on node ranking with a medical application Hunter RehmID1 Mona MatarID2 Puck RombachID1 and

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: