Generic Constraint-based Block Modeling using Constraint Programming
By Alex Mattenet, Ian Davidson, Siegfried Nijssen, and Pierre Schaus
Block Modeling is a problem related to graph clustering where we summarize a large graph in terms of groups of nodes and the interactions between those groups. The general formulation of the problem is often extended with additional constraints on the composition of the groups and the types of interactions allowed.
However, each previous work on those extensions yielded a different type of solver that is only scalable for its specific problem setting.
In this work, we present a new approach based on constraint programming, allowing discrete optimization of block modeling in a manner that is not only scalable, but also allows the easy incorporation of constraints. We introduce a new constraint filtering algorithm that outperforms earlier approaches, in both constrained and unconstrained settings. We show its use in the analysis of real datasets, including novel uses for analysis of human migration.
This article was presented to CP2019 - The 25th International Conference on Principles and Practice of Constraint Programming - Stamford, Connecticut, USA, Sep. 30 to Oct 4, 2019
About authors :
Alex Mattenet is a PhD student at the INGI department at UCLouvain, Belgium. Her current work focuses on the application of machine learning and data mining systems with fairness constraints to graphs and networks.
is a Professor in the computer science department at the University of California at Davis, USA. His research focuses on AI, machine learning and data mining algorithm development. He works with domain expert collaborators on applications to areas with societal impacts such as neuroscience, intelligent tutoring systems and social networks.
is an assistant professor of data mining and artificial intelligence at the Université catholique de Louvain (UCLouvain) in Belgium. His research aims to make data analysis simpler for both end-users and programmers; it studies intersections between pattern mining, exploratory data analysis, and programming paradigms in Artificial Intelligence, such as constraint programming and probabilistic programming. He has developed techniques for analysing a wide range of data types, including graphs, networks and multi-relational data.
Pierre Schaus obtained his Ph.D. from the UCLouvain University in 2009. He spent 5 months at Brown University. Then he joined the Dynadec startup to work on Comet during two years before working two more years at N-SIDE. September 2012, he is Professor of Computer Science, UCLouvain, Department of Computing Science and Engineering of the Institute.