A generalized inverse for graphs with absorption
A generalized inverse for graphs with absorption
复制标题
DOI：
10.1016/j.laa.2017.09.029
复制
发表时间：
2016-11
影响因子：
1.1
通讯作者：
Karly A Jacobsen;J. Tien
中科院分区：
文献类型：
--
作者：
Karly A Jacobsen;J. Tien
我们考虑加权，有向图的顶点吸收的概念，吸收图上的随机游动。我们定义了一个广义逆的图拉普拉斯算子，称为吸收逆，它既反映了图的结构，也反映了顶点上的吸收率。给出了这种广义逆的性质，包括吸收逆与相关图的群逆之间的基本关系，解释吸收逆元素的森林定理，以及吸收逆与吸收随机游动的基本矩阵之间的关系.给出了吸收逆在描述具有吸收的图的结构中的应用，包括有向距离度量、谱划分算法和中心性度量。
We consider weighted, directed graphs with a notion of absorption on the vertices, related to absorbing random walks on graphs. We define a generalized inverse of the graph Laplacian, called the absorption inverse, that reflects both the graph structure as well as the absorption rates on the vertices. Properties of this generalized inverse are presented, including a basic relationship between the absorption inverse and the group inverse of a related graph, a forest theorem for interpreting the entries of the absorption inverse, as well as relationships between the absorption inverse and the fundamental matrix of the absorbing random walk. Applications of the absorption inverse for describing the structure of graphs with absorption are given, including a directed distance metric, spectral partitioning algorithm, and centrality measure.