Geodesic
A Matrix-Based Measure of Inter-Node Walk Relatedness in a Network
Matematičeskie zametki, Tome 85 (2009) no. 1, pp. 119-130 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

For a pair of nodes in a network, a measure of walk relatedness is introduced. The measure is based on the total weight (number) of $k$-step walks connecting the pair, i.e., the corresponding entry of the $k$th power of the network matrix as $k\to\infty$. The damping factor $r^{-k}$ is used, where $r$ is the largest eigenvalue of the network matrix. The measure turns out to be equal to the product of the pair's coreness values, i.e., the nodes' coordinates in the network matrix's right and left eigenvectors corresponding to $r$. The walk relatedness reduction in a network caused by the removal of a node or link is investigated, namely, the reduction dependence on the structural position (coreness) of the removed element. It is revealed that the “damage” can be measured by the drop in the value of $r$ after the removal; to find this drop, the perturbation method is used. Some possible applications are indicated, and a numerical example with a large real network of 197 nodes and 780 links is considered.
Mots-clés : nonnegative matrix, dominant eigenvalue
Keywords: network walk, network node coreness, walk relatedness measure, bipartite network, node/link removal, eigenvalue drop. 
@article{MZM_2009_85_1_a10,
     author = {V. M. Chelnokov and V. L. Zefirova},
     title = {A {Matrix-Based} {Measure} of {Inter-Node} {Walk} {Relatedness} in a {Network}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {119--130},
     year = {2009},
     volume = {85},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2009_85_1_a10/}
}
TY  - JOUR
AU  - V. M. Chelnokov
AU  - V. L. Zefirova
TI  - A Matrix-Based Measure of Inter-Node Walk Relatedness in a Network
JO  - Matematičeskie zametki
PY  - 2009
SP  - 119
EP  - 130
VL  - 85
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/MZM_2009_85_1_a10/
LA  - ru
ID  - MZM_2009_85_1_a10
ER  - 
%0 Journal Article
%A V. M. Chelnokov
%A V. L. Zefirova
%T A Matrix-Based Measure of Inter-Node Walk Relatedness in a Network
%J Matematičeskie zametki
%D 2009
%P 119-130
%V 85
%N 1
%U http://geodesic.mathdoc.fr/item/MZM_2009_85_1_a10/
%G ru
%F MZM_2009_85_1_a10
V. M. Chelnokov; V. L. Zefirova. A Matrix-Based Measure of Inter-Node Walk Relatedness in a Network. Matematičeskie zametki, Tome 85 (2009) no. 1, pp. 119-130. http://geodesic.mathdoc.fr/item/MZM_2009_85_1_a10/

[1] P. Khorn, Ch. Dzhonson, Matrichnyi analiz, Mir, M., 1989 | MR | Zbl

[2] Dzh. Kh. Golub, Ch. F. Van Loun, Matrichnye vychisleniya, Mir, M., 1999 | MR | Zbl

[3] D. K. Faddeev, V. N. Faddeeva, Vychislitelnye metody lineinoi algebry, Fizmatgiz, M., 1963 | MR | Zbl

[4] Dzh. Kh. Uilkinson, Algebraicheskaya problema sobstvennykh znachenii, Nauka, M., 1970 | MR | Zbl

[5] I. M. Gelfand, Lektsii po lineinoi algebre, Nauka, M., 1966 | MR | Zbl

[6] V. M. Chelnokov, V. L. Zefirova, “Matrichnyi pokazatel stepeni prinadlezhnosti uzla seti serdtsevine seti”, Matem. zametki, 80:6 (2006), 908–919 | MR | Zbl

[7] S. P. Borgatti, M. G. Everett, “Models of core/periphery structures”, Social Networks, 21:4 (2000), 375–395 | DOI

[8] J. M. Kleinberg, “Authoritative sources in a hyperlinked environment”, J. ACM, 46:5 (1999), 604–632 | DOI | MR | Zbl

[9] G. Salton, Automatic text processing, Addison-Wesley, Reading, MA, 1989

[10] W. Kintsch, D. M. Welsch, “The construction-integration model: a framework for studying memory for text”, Relating Theory and Data: Essays on Human Memory, Erlbaum, Hillsdale, NJ, 1991, 367–386

[11] D. Tsvetkovich, M. Dub, Kh. Zakhs, Spektry grafov: Teoriya i primenenie, Naukova dumka, Kiev, 1984 | MR

[12] B. B. Voevodin, Yu. A. Kuznetsov, Matritsy i vychisleniya, Nauka, M., 1984 | MR | Zbl

[13] R. Albert, H. Jeong, A.-L. Barabási, “Error and attack tolerance of complex networks”, Nature, 406 (2000), 378–382 | DOI

[14] R. Albert, A.-L. Barabási, “Statistical mechanics of complex networks”, Rev. Modern Phys., 74:1 (2002), 47–97 | DOI | MR

[15] S. Brin, L. Page, “The anatomy of a large-scale hypertextual Web-search engine”, Proceedings of the 7th World-Wide Web Conference (14–18 april, 1998, Brisbane, Australia), Brisbane, 1998, 107–117