Random and Longest Paths: Unnoticed Motifs of Complex Networks

Simple item page
dc.creatorCosta, Luciano da Fontoura
dc.date2007-12-04
dc.date.accessioned2026-07-07T08:47:08Z
dc.date.available2026-07-07T08:47:08Z
dc.descriptionPaths are important structural elements in complex networks because they are finite (unlike walks), related to effective node coverage (minimum spanning trees), and can be understood as being dual to star connectivity. This article introduces the concept of random path applies it for the investigation of structural properties of complex networks and as the means to estimate the longest path. Random paths are obtained by selecting one of the network nodes at random and performing a random self-avoiding walk (here called path-walk) until its termination. It is shown that the distribution of random paths are markedly different for diverse complex network models (i.e. Erdos-Renyi, Barabasi-Albert, Watts-Strogatz, a geographical model, as well as two recently introduced path-based network types), with the BA structures yielding the shortest random walks, while the longest paths are produced by WS networks. Random paths are also explored as the means to estimate the longest paths (i.e. several random paths are obtained and the longest taken). The convergence to the longest path and its properties ire characterized with respect to several networks models. Several results are reported and discussed, including the markedly distinct lengths of the longest paths obtained for the different network models.
dc.description13 pages, 8 figures. A working manuscript: comments welcomed
dc.identifierhttps://arxiv.org/abs/0712.0415
dc.identifierhttp://arxiv.org/abs/0712.0415
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/143492
dc.subjectPhysics and Society
dc.subjectDisordered Systems and Neural Networks
dc.subjectComputational Physics
dc.titleRandom and Longest Paths: Unnoticed Motifs of Complex Networks
dc.typetext

Files

Collections

arXiv