cGraph: A fast graph-based method for link analysis and queries

Many techniques in the social sciences and graph theory deal with the problem of examining and analyzing patterns found in the underlying struc-ture and associations of a group of entities. How-ever, much of this work assumes that this under-lying structure is known or can easily be inferred from data, which may often be an unrealistic as-sumption for many real-world problems. Below we consider the problem of learning and querying a graph-based model of this underlying structure. The model is learned from noisy observations link-ing sets of entities. We explicitly allow different types of links (representing different types of rela-tions) and temporal information indicating when a link was observed. We quantitatively compare this representation and learning method against other algorithms on the task of predicting future links and new “friendships ” in a variety of real world data sets.