Connectivity in Random Forests and Credit Networks
Ashish Goel, Sanjeev Khanna, Sharath Raghvendra, Hongyang Zhang · 2015
Recent work has highlighted credit networks as an e↵ective mechanism for modeling trust in a network: agents issue their own currency and trust each other for a certain amount of each other’s currency, allowing two nodes to transact if there is a chain of sucient residual trust between them. Under a natural model of repeated transactions, the probability that two agents can successfully transact in a credit network (i.e. the liquidity between these two agents) is the same as the probability that they are connected to each other in a uniformly random forest of the network. Motivated by this connection, we define the RF-connectivity between a pair of nodes in a graph G as the probability that the two nodes belong to the same connected component in a uniformly random forest of G. Our first re-