Finding Links and Initiators: A Graph-Reconstruction Problem

Analyzing 0-1 matrices is one of the main themes in data mining. Techniques such as clustering or mixture modelling, matrix decomposition techniques such as PCA, ICA, and NMR, and Bayesian all aim to give an answer to the informal question: "Where does the matrix come from?" These approaches aim at describing a probabilistic generative model that describes the observed matrix well. This paper considers yet another way of answering the question "Where does a 0{1 matrix M come from?" In the model, the matrix M of size n £ m is considered to arise from initiators, certain few entries that are initially 1.