Abstract
Dense subgraph detection is one of the most important topics in graph analysis. Most previous work on this issue assume an adjacency list or a stream of edges for the target graph. In most real applications however, the underlying graphs only allow navigational access by following links from one node to another. In this paper, we propose a dense subgraph detection technique under the navigational access model. We use neighborhood density to measure dense components in a graph and develop an efficient dense subgraph finding algorithm. Preliminary experiments are carried out to evaluate the proposed scheme.