A Graph Theoretic Approach to Automated Consensus Building
by
Kari Chopra
Rensselaer Polytechnic Institute
Coauthors: Mark Goldberg (Rensselaer Polytechnic Institute), William A. Wallace (Rensselaer Polytechnic Institute)

We present an application of graph theory to the problem of automated consensus building. Suppose we consult a group of experts for their knowledge on a particular topic, and each expert's knowledge may be modeled as a graph. Our goal is to compute a consensus graph that pools the knowledge contained in the experts' individual graphs. We construct a metagraph, a graph whose vertices are graphs themselves, that contains the possible candidates for the consensus graph. We then find a consensus graph by computing the center, median, or betweenness center of the metagraph. A description of the model, heuristic algorithms for large metagraphs, experimental results, and a set of open questions for graph theory research will be presented.

Date received: April 20, 2001