Community detection by modularity maximization using GRASP with path relinking

Community detection by modularity maximization using GRASP with path relinking

Author Nascimento, Maria C. V. Autor UNIFESP Google Scholar
Pitsoulis, Leonidas Google Scholar
Institution Universidade Federal de São Paulo (UNIFESP)
Aristotle Univ Thessaloniki
Abstract Complex systems in diverse areas such as biology, sociology and physics are frequently being modelled as graphs, that provide the mathematical framework upon which small scale dynamics between the fundamental elements of the system can reveal large scale system behavior. Community structure in a graph is an important large scale characteristic, and can be described as a natural division of the vertices into densely connected groups, or clusters. Detection of community structure remains up to this date a computationally challenging problem despite the efforts of many researchers from various scientific fields in the past few years. the modularity value of a set of vertex clusters in a graph is a widely used quality measure for community structure, and the relating problem of finding a partition of the vertices into clusters such that the corresponding modularity is maximized is an NP-Hard problem.In this paper we present a Greedy Randomized Adaptive Search Procedure (GRASP) with path relinking, for solving the modularity maximization problem in weighted graphs.A class of (0,1) matrices is introduced that characterizes the family of clusterings in a graph, and a distance function is given that enables us to define an I-neighborhood local search, which generalizes most of the related local search methods that have appeared in the literature. Computational experiments comparing the proposed algorithm with other heuristics from the literature in a set of artificially generated graphs and some well known benchmark instances, indicate that our implementation of GRASP with path relinking consistently produces better quality solutions. (C) 2013 Elsevier B.V. All rights reserved.
Keywords Complex systems
Community structure
Graph clustering
Modularity
RASP Path relinking
Language English
Sponsor European Union (European Social Fund ESF)
Operational Program Education and Lifelong Learning of the National Strategic Reference Framework (NSRF)
European Social Fund
Date 2013-12-01
Published in Computers & Operations Research. Oxford: Pergamon-Elsevier B.V., v. 40, n. 12, p. 3121-3131, 2013.
ISSN 0305-0548 (Sherpa/Romeo, impact factor)
Publisher Elsevier B.V.
Extent 3121-3131
Origin http://dx.doi.org/10.1016/j.cor.2013.03.002
Access rights Closed access
Type Article
Web of Science ID WOS:000326610000030
URI http://repositorio.unifesp.br/handle/11600/37036

Show full item record




File

File Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Search


Browse

Statistics

My Account