1
$\begingroup$

I am right now searching and saving the graph structure of english wiktionary, saving each page as a vertex and its hyperlinked pages as another nodes that are connected with unweighted edges.

So I had coded an traversing algorithm and implemented it with Python, so the traverser first visit a page then crawls every hyperlinks on that arbitrarily given page then decides randomly which page to visit next.

This algorithm become exponentially inefficient after it crawls 20,000 nodes(out of 1,000,000) since it keep visiting already visited nodes.

So I had added another function that before visit, check whether the node has been visited or not.

However, still, it is too slow. It crawls 200 pages only during an hour on average.

Now, let's mathematically formulate the problem I want to solve.

Suppose there $\exists G(V,E)$ such that $|V|, |E| \in \Bbb N$ which are finite. Then with each algorithm a traverser can reveal the structure of $G(V,E) $ most efficiently where the 'efficient' defined by smallest number of steps from $V_i \ \text{to} \ V_j$ where $i,j \in V$ ? The traverser already knows the set $V$ but doesn't know $E$ at all. The $G$ is directed and unweighted.

The traverser keep increasing its partial information about Graph. Then I roughly guess the optimal traversing strategy might keep changing. I'd like to discuss about that. Simply speaking,

How would the algorithm be affected while the traverser keep increasing its knowledge over the graph?

$\endgroup$
  • 1
    $\begingroup$ You probably need to narrow down what you want to do with this question, this is quite a broad topic. For instance, you might be interested in the literature on PageRank, random walks on graphs, and fingerprinting. What precisely are you trying to find out about the structure of the graph: are you trying to estimate its edge density, find the vertices of highest degree, estimate the diameter, something else? $\endgroup$ – András Salamon Mar 13 '18 at 11:20
  • $\begingroup$ No I only need to find most efficient visiting algorithm when I only knows which Vertex I have but don't know the edge relationship of those. That's it. I am not interested in node ranking or node centrality at this stage. $\endgroup$ – delinco Mar 13 '18 at 11:24
  • 1
    $\begingroup$ Are you then perhaps looking for a universal traversal sequence or a universal exploration sequence? These aren't the most efficient (roughly cubic in the number of vertices) but do have strong guarantees. $\endgroup$ – András Salamon Mar 13 '18 at 11:41
  • $\begingroup$ Could you give me reference of those algorithm? Which are reprented in mathematical notation would be even better $\endgroup$ – delinco Mar 13 '18 at 11:43
  • $\begingroup$ Koucky's report on UTS/UXS might be of use: iuuk.mff.cuni.cz/~koucky/papers/t2x.ps $\endgroup$ – András Salamon Mar 13 '18 at 11:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.