The size and complexity of actual networked systems hinders the access to a global knowledge of their structure. This fact pushes the problem of navigation to suboptimal solutions, one of them being the extraction of a coherent map of the topology on which navigation takes place. In this paper, we present a Markov chain based algorithm to tag networked terms according only to their topological features. The resulting tagging is used to compute similarity between terms, providing a map of the networked information. This map supports local-based navigation techniques driven by similarity. We compare the efficiency of the resulting paths according to their length compared to that of the shortest path. Additionally we claim that the path steps towards the destination are semantically coherent. To illustrate the algorithm performance we provide some results from the Simple English Wikipedia, which amounts to several thousand of pages. The simplest greedy strategy yields over an 80% of average success rate. Furthermore, the resulting content-coherent paths most often have a cost between one- and threefold compared to shortest-path lengths.
Description
Local-Based Semantic Navigation on a Networked Representation of Information
%0 Journal Article
%1 capitan2012localbased
%A Capitán, José A.
%A Borge-Holthoefer, Javier
%A Gómez, Sergio
%A Martinez-Romo, Juan
%A Araujo, Lourdes
%A Cuesta, José A.
%A Arenas, Alex
%D 2012
%I Public Library of Science
%J PLOS ONE
%K local navigation semantic
%N 8
%P 1-10
%R 10.1371/journal.pone.0043694
%T Local-Based Semantic Navigation on a Networked Representation of Information
%U https://doi.org/10.1371/journal.pone.0043694
%V 7
%X The size and complexity of actual networked systems hinders the access to a global knowledge of their structure. This fact pushes the problem of navigation to suboptimal solutions, one of them being the extraction of a coherent map of the topology on which navigation takes place. In this paper, we present a Markov chain based algorithm to tag networked terms according only to their topological features. The resulting tagging is used to compute similarity between terms, providing a map of the networked information. This map supports local-based navigation techniques driven by similarity. We compare the efficiency of the resulting paths according to their length compared to that of the shortest path. Additionally we claim that the path steps towards the destination are semantically coherent. To illustrate the algorithm performance we provide some results from the Simple English Wikipedia, which amounts to several thousand of pages. The simplest greedy strategy yields over an 80% of average success rate. Furthermore, the resulting content-coherent paths most often have a cost between one- and threefold compared to shortest-path lengths.
@article{capitan2012localbased,
abstract = {The size and complexity of actual networked systems hinders the access to a global knowledge of their structure. This fact pushes the problem of navigation to suboptimal solutions, one of them being the extraction of a coherent map of the topology on which navigation takes place. In this paper, we present a Markov chain based algorithm to tag networked terms according only to their topological features. The resulting tagging is used to compute similarity between terms, providing a map of the networked information. This map supports local-based navigation techniques driven by similarity. We compare the efficiency of the resulting paths according to their length compared to that of the shortest path. Additionally we claim that the path steps towards the destination are semantically coherent. To illustrate the algorithm performance we provide some results from the Simple English Wikipedia, which amounts to several thousand of pages. The simplest greedy strategy yields over an 80% of average success rate. Furthermore, the resulting content-coherent paths most often have a cost between one- and threefold compared to shortest-path lengths.},
added-at = {2017-07-16T12:44:13.000+0200},
author = {Capitán, José A. and Borge-Holthoefer, Javier and Gómez, Sergio and Martinez-Romo, Juan and Araujo, Lourdes and Cuesta, José A. and Arenas, Alex},
biburl = {https://www.bibsonomy.org/bibtex/2ff5b3083eeb990ec6cbeb5def69d34e4/thoni},
description = {Local-Based Semantic Navigation on a Networked Representation of Information},
doi = {10.1371/journal.pone.0043694},
interhash = {607f70076cd384c4c438eb9aed2ef60b},
intrahash = {ff5b3083eeb990ec6cbeb5def69d34e4},
journal = {PLOS ONE},
keywords = {local navigation semantic},
month = {08},
number = 8,
pages = {1-10},
publisher = {Public Library of Science},
timestamp = {2017-07-16T12:44:13.000+0200},
title = {Local-Based Semantic Navigation on a Networked Representation of Information},
url = {https://doi.org/10.1371/journal.pone.0043694},
volume = 7,
year = 2012
}