Markov Logic: A Rich Modeling Language for Social Networks

Real social networks contain multiple types of actors related in multiple ways, and complex dependencies among these relations. We need a modeling language that makes it easy to express these, learn them from data, perform inference with them, and refine them. We propose Markov logic as such a language. A model in Markov logic is a set of weighted formulas in first-order logic, where each formula is interpreted as a template for features of a Markov random field, with the corresponding weight. Standard models used in social network analysis are easily expressed in Markov logic, as are much more complex ones. We have developed highly efficient algorithms for Markov logic drawing on ideas from satisfiability testing and Markov chain Monte Carlo, and learning algorithms based on the voted perceptron, pseudo-likelihood and inductive logic programming. Markov logic has been successfully applied to a variety of problems in social network modeling, and is the basis of the open-source Alchemy system. (Joint work with Stanley Kok, Daniel Lowd, Hoifung Poon, Matt Richardson and Parag Singla.)