Beyond the shortest path the path length index as a distribution

2025-04-22 0 0 483KB 13 页 10玖币

侵权投诉

Beyond the shortest path: the path length index as a

distribution

Leonardo B. L. Santosa, Luiz Max Carvalhob, Giovanni G. Soaresc,

Leonardo N. Ferreirad, Igor M. Sokolove

aNational Center for Monitoring and Early Warning of Natural Disasters (Cemaden),

Brazil

bSchool of Applied Mathematics (EMAp), Getulio Vargas Foundation (FGV), Brazil

cNational Institute of Space Research (INPE), Brazil

dCenter for Humans and Machines, Max Planck Institute for Human Development,

Germany

eHumboldt University of Berlin, Germany

1. Motivation

Traversing graphs is a fundamental question in Graph Theory and an im-

portant consideration when dealing with complex networks. The traditional

complex network approach considers only the shortest paths from one node

to another [1], and does not take into account several other possible paths.

This limitation is signiﬁcant, for example, in urban mobility studies [2, 3],

where it important to consider alternative routes between locations.

As mentioned by Lima et al. (2016), in urban mobility settings users

choose multiple routes over origin-destination pairs, and those choices often

deviate from the shortest time path. Galbrun et al. (2016) highlight that

chosen routes may be associated with diverse factors, for instance public

safety. Tomas et al. (2022) further support these claims by showing that

exceptional events, such as urban ﬂoods, may lead users to deviate from

routes previously deﬁned to risk-less (and potentially longer) ones.

Estrada and Hatano (2008) proposed the Communicability Index, a num-

ber (scalar) that takes into account not only the shortest paths but also all

the walks from one node to another. Their approach was based on walks. In

Email address: santoslbl@gmail.com (Leonardo B. L. Santos)

Preprint submitted to Journal Name October 10, 2022

arXiv:2210.03216v1 [cs.DM] 6 Oct 2022

contrast, here we are interested in paths due to the urban mobility motivation

context.

On one hand, the number of walks between each pair of nodes in a simple

graph is known analytically [6]. On the other hand, the analogous problem

for paths is NP-hard [7]. Roberts and Kroese (2007) presented an stochas-

tic algorithm to estimate the solution of that problem using a sequential

importance sampling.

In this short report, as the ﬁrst steps, we present an exhaustive approach

to address the problem of ﬁnding all paths between two nodes. We show one

can go beyond the shortest path but we do not need to go so far: we present

an interactive procedure and an early stop possibility. We apply our ideas

to the well-known Zachary’s karate club graph [8]. We do not collapse the

distribution of path lengths between a pair of nodes into a scalar number;

instead we look at the distribution itself - taking all paths up to a pre-deﬁned

path length (considering a truncated distribution), and show the impact of

that approach on the most straightforward distance-based graph index: the

walk/path length.

2. Preliminaries: deﬁnitions and notation

In this section, we give a few deﬁnitions and results from elementary graph

theory to facilitate the understanding of the new results presented herein.

Most of the following discussion is standard and can be found in [1, 6].

We start by deﬁning a graph (Deﬁnition 2.1) and then a simple graph

(Deﬁnition 2.2), which will be the main objects of interest in this paper.

Deﬁnition 2.1 (Graph).A graph G= (V, E)is a set of nodes and edges,

where Vis the set of |V|=Nnodes and Eis the set of |E|=Medges.

An edge (also called link or connection) (i, j), i, j ∈Vconnects two nodes

iand j. A self-connection or a loop is a link (i, i) that connects node ito

itself. Multiple edges are two or more edges that connect the same two

vertices.

A link can be undirected or directed. In an undirected graph, all edges

(i, j) connect ito jand vice-versa. A directed graph has directed edges (also

called arcs) (i, j), that connect ito j, but not jto i, i.e., (i, j)6= (j, i). A

link can also have an associated weight, which is a numeric value.

Deﬁnition 2.2 (Simple Graph).A graph G= (V, E)is a simple graph if,

and only if, it is undirected, there are no self-connections in G, no multiple

edges or weights.

A helpful object for characterizing a graph is its adjacency matrix, whose

deﬁnition is given in Deﬁnition 2.3.

Deﬁnition 2.3 (Adjacency matrix).The adjacency matrix Aof a graph

G= (V, E)is the N×Nmatrix whose entries Aij are given by

Aij =(1,if i, j ∈Vshare an edge;

0,otherwise.

In this paper, we are concerned with traversing the graph, i.e., starting

from a source node i∈V, visiting a collection of nodes, and arrive a target

node j∈V, where i=jis a possibility. Here we distinguish between

trajectories that allow multiple visits to the same node (and associated)

edges, called walks (Deﬁnition 2.4); and trajectories where each node and

vertex can only be visited once, called paths, presented in Deﬁnition 2.5.

We start our discussion with trajectories that can visit the same node

multiple times, called walks:

Deﬁnition 2.4 (Walk).Consider a simple graph G= (V, E)and a pair of

nodes i, j in V. A walk win Gfrom ito jis an alternating sequence of edges

and nodes from i(node of origin/source) to j(node of destination/target).

With this deﬁnition in hand, we are prepared to state Theorem 2.1, which

tells us that the number of walks of a given (ﬁnite) length is ﬁnite so long as

|V|is ﬁnite.

Theorem 2.1 (Finite number of walks).Consider a simple graph G=

(V, E). Take i, j ∈V, the number of walks of length lbetween iand jis

given by

fij

W(l) = Alij ,

where Aij is the corresponding entry in the adjacency matrix of G– see

Deﬁnition 2.3.

Proof. This is a well-known result. See Lemma 2.5 in [6].

Now, consider trajectories in a graph without ever visiting any node twice.

Such a trajectory is called a path:

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

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

10 玖币 0人已下载

立即下载

摘要：

Beyondtheshortestpath:thepathlengthindexasadistributionLeonardoB.L.Santosa,LuizMaxCarvalhob,GiovanniG.Soaresc,LeonardoN.Ferreirad,IgorM.SokoloveaNationalCenterforMonitoringandEarlyWarningofNaturalDisasters(Cemaden),BrazilbSchoolofAppliedMathematics(EMAp),GetulioVargasFoundation(FGV),BrazilcNationalI...

展开>> 收起<<

Beyond the shortest path the path length index as a distribution.pdf

共13页,预览3页

还剩页未读，继续阅读

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

Beyond the shortest path the path length index as a distribution

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: