3,363 research outputs found
Entrevista: Prof. Dr. Nelson De Luca Pretto (por Alan Queiroz da Costa)
No full textInterview given by Nelson De Luca Pretto a Alan Queiroz da Costa, in September 2024, for the thematic section "Brazilian Physical Education and contemporary challenges: responsibilities, commitments and dialogues with media, technologies and digital culture" of Motrivivência Magazine (LaboMidia-UFSC), in an edition associated with GTT 2 - Communication and Media/CBCE.Entrevista concedida por Nelson De Luca Pretto a Alan Queiroz da Costa, en agosto de 2024, para la sección temática "Educación Física brasileña y desafíos contemporáneos: responsabilidades, compromisos y diálogos con los medios, tecnologías y cultura digital" de la Revista Motrivivência (LaboMidia-UFSC), en edición asociada con el GTT 2 - Comunicación y Medios/CBCE.Entrevista concedida por Nelson De Luca Pretto a Alan Queiroz da Costa, em setembro de 2024, para a seção temática “Educação Física brasileira e desafios contemporâneos: responsabilidades, compromissos e diálogos com as mídias, tecnologias e cultura digital” da Revista Motrivivência (LaboMidia-UFSC), em edição associada com o GTT 2 – Comunicação e Mídia/CBCE
Educación, conocimiento libre y tecnologías digitales: desafíos contemporáneos
No full textPresentación de la conferencia sobre Educación, Conocimiento Libre y Tecnologías Digitales: Desafíos Contemporáneos a cargo de Nelson De Luca Pretto (Facultad de Educación, Universidad Federal de Bahía, Brasil).Facultad de Educación (Universidad Federal de Bahía
Local Computation of PageRank: the Ranking Side
No full textImagine you are a social network user who wants to search, in a list of potential candidates, for the best candidate for a job on the basis of their PageRank-induced importance ranking. Is it possible to compute this ranking for a low cost, by visiting only small subnetworks around the nodes that represent each candidate? The fundamental problem underpinning this question, i.e. computing locally the PageRank ranking of k nodes in an -node graph, was first raised by Chen et al. (CIKM 2004) and then restated by Bar-Yossef and Mashiach (CIKM 2008). In this paper we formalize and provide the first analysis of the problem, proving that any local algorithm that computes a correct ranking must take into consideration Ω(√(kn)) nodes -- even when ranking the top nodes of the graph, even if their PageRank scores are "well separated", and even if the algorithm is randomized (and we prove a stronger Ω(n) bound for deterministic algorithms). Experiments carried out on large, publicly available crawls of the web and of a social network show that also in practice the fraction of the graph to be visited to compute the ranking may be considerable, both for algorithms that are always correct and for algorithms that employ (efficient) local score approximations
A Theoretical Study of a Generalized Version of Kleinberg's HITS Algorithm
No full textKleinberg's HITS algorithm (Kleinberg 1999), which was originally developed in a Web context, tries to infer the authoritativeness of a Web page in relation to a specific query using the structure of a subgraph of the Web graph, which is obtained considering this specific query. Recent applications of this algorithm in contexts far removed from that of Web searching (Bacchin, Ferro and Melucci 2002, Ng et al. 2001) inspired us to study the algorithm in the abstract, independently of its particular applications, trying to mathematically illuminate its behaviour. In the present paper we detail this theoretical analysis. The original work starts from the definition of a revised and more general version of the algorithm, which includes the classic one as a particular case. We perform an analysis of the structure of two particular matrices, essential to studying the behaviour of the algorithm, and we prove the convergence of the algorithm in the most general case, finding the analytic expression of the vectors to which it converges. Then we study the symmetry of the algorithm and prove the equivalence between the existence of symmetry and the independence from the order of execution of some basic operations on initial vectors. Finally, we expound some interesting consequences of our theoretical results
Organismo
No full textOrganism is the word through which the tradition express the way of being of living beings. This article is a reconstruction of the development of the word 'organism' in its peculiar relationship with the notion of 'machine
Brief announcement: On approximating pageRank locally with sublinear query complexity
No full textCan one compute the pageRank score of a single, arbitrary node in a graph, exploring only a vanishing fraction of the graph? We provide a positive answer to this extensively researched open question. We develop the first algorithm that, for any n-node graph, returns a multiplicative (1±ε)-approximation of the score of any given node with probability (1−δ), using at most On2/3ln(n)1/3ln(1/δ)2/3ε−2/3= Õ(n2/3) queries which return either a node chosen uniformly at random, or the list of neighbours of a given node. Alternatively, we show that the same guarantees can be attained by fetching at most OE4/5d−3/5ln(n)1/5ln(1/δ)3/5ε−6/5= Õ(E4/5) arcs, where E is the total number of arcs in the graph and d is its average degree
Sublinear algorithms for local graph centrality estimation
No full textWe study the complexity of local graph centrality estimation, with the goal of approximating the centrality score of a given target node while exploring only a sublinear number of nodes/arcs of the graph and performing a sublinear number of elementary operations. We develop a technique, that we apply to the PageRank and Heat Kernel centralities, for building a low-variance score estimator through a local exploration of the graph. We obtain an algorithm that, given any node in any graph of m arcs, with probability (1-δ) computes a multiplicative (1±ε)-approximation of its score by examining only Õ(min(m^2/3 Δ^1/3 d^-2/3 , m 4/5 d -3/5 )) nodes/arcs, where Δ and d are respectively the maximum and average outdegree of the graph (omitting for readability poly(ε^ -1 ) and polylog(δ ^-1 ) factors). A similar bound holds for computational cost. We also prove a lower bound of Ω(min (m^1/2 Δ^1/2 d^-1/2 , m^2/3 d^-1/3 )) for both query complexity and computational complexity. Moreover, our technique yields a Õ(n^2/3 )-queries algorithm for an n-node graph in the access model of [Brautbar et al., 2010], widely used in social network mining; we show this algorithm is optimal up to a sublogarithmic factor. These are the first algorithms yielding worst-case sublinear bounds for general directed graphs and any choice of the target node
Sublinear Algorithms for Local Graph-Centrality Estimation
No full textWe study the complexity of local graph-centrality estimation, with the goal of approximating the centrality score of a given target node while exploring only a sublinear number of nodes/arcs of the graph and performing a sublinear number of elementary operations.
We develop a technique, that we apply to PageRank and Heat Kernel, for constructing a low-variance score estimator through a local exploration of the graph.
We obtain an algorithm that, given any node in any graph of nodes and arcs, with probability computes a multiplicative -approximation of its score by examining only \tilde{O}(\min(n^{1/2} \dmax^{1/2}, n^{1/2} m^{1/4})) nodes/arcs, where \dmax is the maximum outdegree of the graph (omitting for readability \poly(\epsilon^{-1}) and \polylog(\delta^{-1}) factors).
A similar bound holds for computational cost.
We also prove a lower bound of \Omega(\min(n^{1/2} \dmax^{1/2}, \, n^{1/3} m^{1/3})) for both query complexity and computational complexity.
Moreover, in the jump-and-crawl graph-access model, our technique yields a \tilde{O}(\min(n^{1/2}\dmax^{1/2}, n^{2/3}))-queries algorithm; we show this algorithm is optimal up to a logarithmic factor -- in fact, sublogarithmic in the case of PageRank. These are the first algorithms with sublinear worst-case bounds for general directed graphs and any choice of the target node
On Approximating the Stationary Distribution of Time-reversible Markov Chains
No full textApproximating the stationary probability of a state in a Markov chain through Markov chain Monte Carlo techniques is, in general, inefficient. Standard random walk approaches require tilde{O}(tau/pi(v)) operations to approximate the probability pi(v) of a state v in a chain with mixing time tau, and even the best available techniques still have complexity tilde{O}(tau^1.5 / pi(v)^0.5); and since these complexities depend inversely on pi(v), they can grow beyond any bound in the size of the chain or in its mixing time.
In this paper we show that, for time-reversible Markov chains, there exists a simple randomized approximation algorithm that breaks this "small-pi(v) barrier"
PRETTO, Nelson De Luca. Uma dobra no tempo: um memorial (quase) acadêmico, Editus, 2015.
No full textResenha do livro "Uma dobra no tempo", de Nelson Pretto.</jats:p
- …
