Multilevel refinement based on neighborhood similarity

Author(s)

Valejo, Alan ; Valverde-Rebaza, Jorge ; Drury, Brett ; Lopes, Alneu de Andrade ; Almeida, A ; Bernardino, J ; Gomes, EF

• Document type: Journal article
• Source: PROCEEDINGS OF THE 18TH INTERNATIONAL DATABASE ENGINEERING AND APPLICATIONS SYMPOSIUM (IDEAS14); v. N/A, p. 10-pg., 2014-01-01.

Abstract

The multilevel graph partitioning strategy aims to reduce the computational cost of the partitioning algorithm by applying it on a coarsened version of the original graph. This strategy is very useful when large-scale networks are analyzed. To improve the multilevel solution, refinement algorithms have been used in the uncorsening phase. Typical refinement algorithms exploit network properties, for example minimum cut or modularity, but they do not exploit features from domain specific networks. For instance, in social networks partitions with high clustering coefficient or similarity between vertices indicate a better solution. In this paper, we propose a refinement algorithm (RSim) which is based on neighborhood similarity. We compare RSim with: 1. two algorithms from the literature and 2. one baseline strategy, on twelve real networks. Results indicate that RSim is competitive with methods evaluated for general domains, but for social networks it surpasses the competing refinement algorithms. (AU)

• FAPESP's process: 11/20451-1 - Induction of Topic-Based Bayesian Networks from Text for the Prediction of Sugar Cane Yields
• Grantee: Brett Mylo Drury
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• FAPESP's process: 11/22749-8 - Challenges in exploratory visualization of multidimensional data: paradigms, scalability and applications
• Grantee: Luis Gustavo Nonato
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 13/12191-5 - Mining User Behavior in Location-Based Social Networks
• Grantee: Jorge Carlos Valverde Rebaza
• Support Opportunities: Scholarships in Brazil - Doctorate