Community detection by local influence

Abstract

We present a new algorithm to discover overlapping communities in networks with a scale free structure. This algorithm is based on a node evaluation function that scores the local influence of a node based on its degree and neighbourhood, allowing for the identification of hubs within a network. Using this function we are able to identify communities, and also to attribute meaningful titles to the communities that are discovered. Our novel methodology is assessed using LFR benchmark for networks with overlapping community structure and the generalized normalized mutual information (NMI) measure. We show that the evaluation function described is able to detect influential nodes in a network, and also that it is possible to build a well performing community detection algorithm based on this function. © 2013 Springer-Verlag.