SIMULATION OF BIPARTITE OR DIRECTED GRAPHS WITH PRESCRIBED DEGREE SEQUENCES USING MAXIMUM ENTROPY PROBABILITIES

摘要

We propose an algorithm for simulating bipartite or directed graphs with given degree sequences, motivated by the study of financial networks with partial information. Our algorithm sequentially computes certain "maximum entropy" matrices, and uses the entries of these matrices to assign probabilities to edges between nodes. We prove the correctness of the algorithm, showing that it always returns a valid graph and that it generates all valid graphs with positive probability. We illustrate the algorithm in an example of an inter-bank network.