A Distributed GPU-based Correlation Clustering Algorithm for Large-scale Signed Social Networks
| Autor: | Mario Levorato, Rosa Figueiredo, Yuri Frota, Lúcia Maria de A. Drummond |
|---|---|
| Přispěvatelé: | Instituto de Computação [Niteroi-Rio de Janeiro] (IC-UFF), Universidade Federal Fluminense [Rio de Janeiro] (UFF) |
| Rok vydání: | 2017 |
| Předmět: |
Scale (ratio)
Computer science Correlation clustering [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] Data mining [INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] computer.software_genre computer [INFO.INFO-SI]Computer Science [cs]/Social and Information Networks [cs.SI] |
| Zdroj: | Brazilian Symposium on High Performance Computing Systems Brazilian Symposium on High Performance Computing Systems, Oct 2017, Campinas, Brazil |
| DOI: | 10.5753/wscad.2017.256 |
| Popis: | International audience; When applied to signed networks, the Correlation Clustering (CC) problem consists of an important tool to study how balanced a social group behaves and if this group might evolve to a possible balanced state. Solving such combinatorial optimization problem is a challenging task, which heavily relies on heuristic procedures, one of the few solution methods capable of analyzing large network instances. In this work, we present a scalable method to solve Correlation Clustering (CC) problems on large-scale signed networks. A distributed GPU-powered version of the ILS metaheuristic, which benefits from data parallelism, has been developed. This approach is horizontally scalable and efficient, as it provides good quality clustering results when compared to non-distributed methods. Experiments were conducted on both synthetic and real datasets. The proposed algorithm achieved improved solution values when compared to the existing parallel solution method. In particular, one of the largest graphs we have considered in our experiments contains 1 million nodes and 8 million edges-such graph can be clustered in two hours using our algorithm. The proposed method can process networks for which there is no efficient solution using the existing algorithms found in the literature. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|