I have a graph (and it is a graph because one node might have many parents) that has contains nodes with the following data:
The relevance is rated with a number starting from 1.
The relevance of a child node is determained by the distance from the parent node the child node minus the depth of the keyword's promotion.
The display order of of child nodes from the same depth is determained by the number of pervious searches.
Is there an algorithm that is able to search such a data structure?
Do I have an efficiency issue if I need to transverse all nodes, cache the generated result and display them by pages considering that this should scale well for a large amount of users? If I do have an issue, how can this be resolved?
What kind of database do I need to use? A NoSQL, a relational one or a graph database?
How the scheme would look like?
Can this be done using django-haystack?
It seems you're trying to compute a top-k query over a graph. There is a variety of algorithms fit to solve this problem, the simplest one I believe will help you to solve your problem is the Threshold Algorithm (TA), when the traversal over the graph is done in a BFS fashion. Some other top-k algorithms are Lawler-Murty Procedure, and other TA variations exist.
Regarding efficiency - the problem of computing the query itself might have an exponential time, simply due to exponential number of results to be returned, but when using a TA the time between outputting results should be relatively short. As far as caching & scale involved, the usual considerations apply - you'll probably want to use a distributed system when the scale gets and the appropriate TA version (such as Threshold Join Algorithm). Of course you'll need to consider the scaling & caching issues when choosing which database solution to use as well.
As far as the database goes you should definitely use one that supports graphs as first class citizens (those tend to be known as Graph Databases), and I believe it doesn't matter if the storage engine behind the graph database is relative or NoSQL. One point to note is that you'd probably will want to make sure the database you choose can scale to the scale you require (so for large scale, perhaps, you'll want to look into more distributed solutions). The schema will depend on the database you'll choose (assuming it won't be a schema-less database).
Last but not least - Haystack. As haystack will work with everything that the search engine you choose to use will work with, there should be at least one possible way to do it (combining Apache Solr for search and Neo4j or GoldenOrb for the database), and maybe more (as I'm not really familiar with Haystack or the search engines it supports other than Solr).