A Critical Survey of the Multilevel Method in Complex Networks

Author(s)

Valejo, Alan ^[1] ; Ferreira, Vinicius ^[1] ; Fabbri, Renato ^[1] ; Ferreira de Oliveira, Maria Cristina ^[1] ; Lopes, Alneu de Andrade ^[1]

Affiliation

^[1] Univ Sao Paulo, Inst Math & Comp Sci ICMC, POB 668, BR-14560970 Sao Carlos, SP - Brazil

• Document type: Journal article
• Source: ACM COMPUTING SURVEYS; v. 53, n. 2 APR 2020.
• Web of Science Citations: 0

Abstract

Multilevel optimization aims at reducing the cost of executing a target network-based algorithm by exploiting coarsened, i.e., reduced or simplified, versions of the network. There is a growing interest in multilevel algorithms in networked systems, mostly motivated by the urge for solutions capable of handling large-scale networks. Notwithstanding the success of multilevel optimization in a multitude of application problems, we were unable to find a representative survey of the state-of-the-art, or consistent descriptions of the method as a general theoretical framework independent of a specific application domain. In this article, we strive to fill this gap, presenting an extensive survey of the literature that contemplates a systematic overview of the state-of-the-art, a panorama of the historical evolution and current challenges, and a formal theoretical framework of the multilevel optimization method in complex networks. We believe our survey provides a useful resource to individuals interested in learning about multilevel strategies, as well as to those engaged in advancing theoretical and practical aspects of the method or in developing solutions in novel application domains. (AU)

• FAPESP's process: 15/14228-9 - Social Network Analysis and Mining
• Grantee: Alneu de Andrade Lopes
• Support Opportunities: Regular Research Grants
• FAPESP's process: 17/05838-3 - Visual analytics: applications and a conceptual investigation
• Grantee: Maria Cristina Ferreira de Oliveira
• Support Opportunities: Regular Research Grants