Please use this identifier to cite or link to this item: http://repositorio.inesctec.pt/handle/123456789/5326
Title: Dynamic community detection in evolving networks using locality modularity optimization
Authors: Mário Miguel Cordeiro
Rui Portocarrero Sarmento
João Gama
Issue Date: 2016
Abstract: The amount and the variety of data generated by today's online social and telecommunication network services are changing the way researchers analyze social networks. Facing fast evolving networks with millions of nodes and edges are, among other factors, its main challenge. Community detection algorithms in these conditions have also to be updated or improved. Previous state-of-the-art algorithms based on the modularity optimization (i.e. Louvain algorithm), provide fast, efficient and robust community detection on large static networks. Nonetheless, due to the high computing complexity of these algorithms, the use of batch techniques in dynamic networks requires to perform network community detection for the whole network in each one of the evolution steps. This fact reveals to be computationally expensive and unstable in terms of tracking of communities. Our contribution is a novel technique that maintains the community structure always up-to-date following the addition or removal of nodes and edges. The proposed algorithm performs a local modularity optimization that maximizes the modularity gain function only for those communities where the editing of nodes and edges was performed, keeping the rest of the network unchanged. The effectiveness of our algorithm is demonstrated with the comparison to other state-of-the-art community detection algorithms with respect to Newman's Modularity, Modularity with Split Penalty, Modularity Density, number of detected communities and running time.
URI: http://repositorio.inesctec.pt/handle/123456789/5326
http://dx.doi.org/10.1007/s13278-016-0325-1
metadata.dc.type: article
Publication
Appears in Collections:LIAAD - Indexed Articles in Journals

Files in This Item:
File Description SizeFormat 
P-00K-AN7.pdf1.73 MBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.