You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

Higher-Order Rank Functions on Directed Graphs

Article type: Research Article

Authors: Kashiwabara, Kenjia; * | Horie, Ikumib | Yamaguchi, Kazunoric

Affiliations: [a] Department of General Systems Studies, University of Tokyo, 3-8-1, Komaba, Meguro-ku, Tokyo, Japan. kashiwa@idea.c.u-tokyo.ac.jp | [b] Faculty of Economics, Dokkyo University, 1-1, Gakuen-cho, Soka-shi, Saitama, Japan. horie@dokkyo.ac.jp | [c] Department of General Systems Studies, University of Tokyo, 3-8-1, Komaba, Meguro-ku, Tokyo, Japan. yamaguch@graco.c.u-tokyo.ac.jp

Correspondence: [*] Address for correspondence: Department of General Systems Studies, the University of Tokyo, 3-8-1, Komaba, Meguro-ku, Tokyo, Japan.

DOI: 10.3233/FI-2020-1913

Journal: Fundamenta Informaticae, vol. 173, no. 1, pp. 1-31, 2020

Received June 2017
|
October 2019
|
Published: 10 February 2020
Get PDF open access

Abstract

We introduce a new higher-order rank function with the capability to completely discriminate non-equivalent nodes. We review the partition lattice and rank functions and situate the existing rank functions and higher-order rank functions within the formalization. We propose a new refining operator and a new rank function that are better than the existing ones in some applications. We also show that the entire topology (graph) can be reconstructed from only our higher-order ranks making it possible to compare nodes in different graphs and to update the equivalence of nodes when an edge is added. Finally, we briefly describe the use of our higher-order rank function in analyzing web pages as a possible application in different domains.

Show more