Higher-Order Rank Functions on Directed Graphs

• Autorzy: Kashiwabara Kenji , Horie Ikumi , Yamaguchi Kazunori

Identyfikatory

DOI

10.3233/FI-2020-1913

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

directed graphs; websites

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 173, nr 1
• Strony: 1--31
• Opis fizyczny: Bibliogr. 16 poz., rys., tab.

Twórcy

autor

Kashiwabara Kenji

• Department of General Systems Studies, University of Tokyo, 3-8-1, Komaba, Meguro-ku, Tokyo, Japan

autor

Horie Ikumi

• Faculty of Economics, Dokkyo University, 1-1, Gakuen-cho, Soka-shi, Saitama, Japan

autor

Yamaguchi Kazunori

• Department of General Systems Studies, University of Tokyo, 3-8-1, Komaba, Meguro-ku, Tokyo, Japan

Bibliografia

• [1] Milner R. An Algebraic Definition of Simulation Between Programs. In: Proceedings of the 2nd International Joint Conference on Artificial Intelligence. London, UK, September 1-3, 1971. 1971 pp. 481-489. URL http://ijcai.org/Proceedings/71/Papers/044.pdf.
• [2] Aczel P. Non-well-founded Sets. Center for the Study of Language and Information Publication Lecture Notes. Cambridge University Press, 1988. ISBN: 9780937073223. URL https://books.google.co.jp/books?id=9yaRQgAACAAJ.
• [3] Horie I, Yamaguchi K, Kashiwabara K. Higher-order rank analysis for web structure. In: HYPERTEXT 2005, Proceedings of the 16th ACM Conference on Hypertext and Hypermedia, September 6-9, 2005, Salzburg, Austria. 2005 pp. 98-106. doi:10.1145/1083356.1083375.
• [4] Horie I, Yamaguchi K, Kashiwabara K. Pattern detection from web using AFA set theory. In: 9th ACM International Workshop on Web Information and Data Management (WIDM 2007), Lisbon, Portugal, November 9, 2007. 2007 pp. 113-120. doi:10.1145/1316902.1316921.
• [5] Dovier A, Piazza C, Policriti A. An efficient algorithm for computing bisimulation equivalence. Theor. Comput. Sci., 2004. 311(1-3):221-256. doi:10.1016/S0304-3975(03)00361-X.
• [6] Paige R, Tarjan RE. Three Partition Refinement Algorithms. SIAM J. Comput., 1987. 16(6):973-989. doi: 10.1137/0216062. URL https://doi.org/10.1137/0216062.
• [7] Piazza C, Policriti A. Ackermann Encoding, Bisimulations, and OBDDs. TPLP, 2004. 4(5-6):695-718. doi:10.1017/S1471068404002091.
• [8] Gentilini R, Piazza C, Policriti A. From Bisimulation to Simulation: Coarsest Partition Problems. J. Autom. Reasoning, 2003. 31(1):73-103. doi:10.1023/A:1027328830731.
• [9] Gentilini R, Piazza C, Policriti A. Rank and simulation: the well-founded case. J. Log. Comput., 2015. 25(6):1331-1349. doi:10.1093/logcom/ext066.
• [10] Omodeo EG, Policriti A, Tomescu AI. On Sets and Graphs: Perspectives on Logic and Combinatorics. Springer, 2017. ISBN 978-3-319-54981-1. URL https://link.springer.com/book/10.1007%2F978-3-319-54981-1.
• [11] Hopcroft JE. An N Log N Algorithm for Minimizing States in a Finite Automaton. Technical report, Stanford, CA, USA, 1971.
• [12] Kanellakis PC, Smolka SA. CCS Expressions, Finite State Processes, and Three Problems of Equivalence. Inf. Comput., 1990. 86(1):43-68. doi:10.1016/0890-5401(90)90025-D.
• [13] Saha D. An Incremental Bisimulation Algorithm. In: FSTTCS. 2007. doi:10.1007/978-3-540-77050-3_17.
• [14] Krug S. Don’T Make Me Think!: A Common Sense Approach to Web Usability. Que Corp., Indianapolis, IN, USA, 1st edition, 2000. ISBN: 0789723107.
• [15] Nielsen J. Designing Web Usability: The Practice of Simplicity. New Riders Publishing, Thousand Oaks, CA, USA, 1999. ISBN: 156205810X.
• [16] David E, Jon K. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, New York, NY, USA, 2010. ISBN:0521195330, 9780521195331.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).