For example, in chess, if we consider a "node" to be a legal position, the average branching factor has been said to be about 35. This means that at each move, on average, a player has about 35 legal moves, and so, for each legal position (or "node") there are, on average, 35 positions that can follow (when a move is made).
An exhaustive brute-force search of the tree (i.e. by following every branch at every node) usually becomes computationally more expensive the higher the branching factor, due to the exponentially increasing number of nodes (combinatorial explosion). For example, if the branching factor is 10, then there will be 10 nodes one level from the current position, 100 nodes two levels down, 1000 three levels down, and so on. The higher the branching factor, the faster this "explosion" occurs.
The branchingfactor of a node in a tree is the number of children it has.
The average branchingfactor for a level in a tree is the ratio of the number of children of that level to the number of nodes in that level and finally the average branchingfactor for a tree is the ratio of the number of nodes to the number of levels.
Of course, then there's the effective branchingfactor of a tree, which is the branchingfactor that a uniform tree of appropriate depth would require for it to contain the same number of nodes as the tree in question.
The crucial parameter describing the underlying network is its "effective branchingfactor." In effect, it's the average number of friends to whom a member of the network passes on a query.
However, if the branchingfactor is less than 2, the amount you have to pay in incentives to get an answer is prohibitive—even though short paths to the answer exist.
"For a large branchingfactor, the propagation of queries is very efficient in its use of reward," Kleinberg and Raghavan conclude in a paper presented at the 46th Annual Symposium on Foundations of Computer Science, held recently in Pittsburgh.
Feeds |
Contact