Parallel Correlation Clustering on Big GraphsParallel Correlation Clustering on Big GraphsPan, Xinghao and Papailiopoulos, Dimitris S. and Oymak, Samet and Recht, Benjamin and Ramchandran, Kannan and Jordan, Michael I.2015
Paper summarynipsreviewsThis work addresses an important special case of the correlation clustering problem: Given as input a graph with edges labeled -1 (disagreement) or +1 (agreement), the goal is to decompose the graph so as to maximize agreement within components. Building on recent work \cite{conf/kdd/BonchiGL14} \cite{conf/kdd/ChierichettiDK14}, this paper contributes two concurrent algorithms, a proof of their approximation ratio, a run-time analysis as well as a set of experiments which demonstrate convincingly the advantage of the proposed algorithms over the state of the art.
Parallel Correlation Clustering on Big Graphs
Pan, Xinghao
and
Papailiopoulos, Dimitris S.
and
Oymak, Samet
and
Recht, Benjamin
and
Ramchandran, Kannan
and
Jordan, Michael I.
Neural Information Processing Systems Conference - 2015 via Local Bibsonomy
Keywords:
dblp
This work addresses an important special case of the correlation clustering problem: Given as input a graph with edges labeled -1 (disagreement) or +1 (agreement), the goal is to decompose the graph so as to maximize agreement within components. Building on recent work \cite{conf/kdd/BonchiGL14} \cite{conf/kdd/ChierichettiDK14}, this paper contributes two concurrent algorithms, a proof of their approximation ratio, a run-time analysis as well as a set of experiments which demonstrate convincingly the advantage of the proposed algorithms over the state of the art.